Algorithmique et structures de données

sdefelice(at)up8.edu

• Gestion des données
• 2 devoirs sur table :
  • max(D2, moyenne(D1, D2))
• TP à rendre (au moins 4) -> + de TPs rendu = meilleur notes
• 1 projet perso à rendre (+ peut-être une présentation) faisable de 1 à 3 personnes.
• Le projet à un gros coef mais tout compte
• DST 1 => mardi 26 octobre
  • 1h15~20 sur papier (écrire des petits programmes, calculs de complexité [dans le pire des cas?], question de cours [comparaison de suites], montrer pour un algo fonctionne, est ce que il se termine, pourquoi est ce que il est correct, donner la complexité de la meilleur méthode sans explication ? [pour un tri dans tableau trié c’est pas n])
• DST 2 => mardi 14 décembre
  • 13h40 -> 15h40 (2h) en J001

1. Rappels de C

Pointeurs

Un pointeur sur un type a de taille n octet est une variable qui contient l’adresse d’une variable de type a (adresse sur a).

Arithmétique du pointeur

Si a est un type de taille m et b est une valeur de type a*, alors, en mémoire, b+i pointe sur le i^{ème} groupe de n octet à “droite”.

Les zones mémoires d’un processus

Un processus a accès à 3 “zones de mémoire”.

• partie où sont écrite les instructions du programme
• “pile d’exécution” (géré automatiquement par le compilateur)
• “réservoir à octet” que le système donne au processus (malloc/free)

Les fonctions

• Les paramètres de la fonction appelée sont transmis par recopie
• On peut utiliser une fonction qui s’appelle elle-même (récursivité)

Structures

/

2. Domination de suite

Cf. TD1reponses

Le nombre d’opérations d’un algorithme pour résoudre un problème dépend des données du problème. Afin de caractériser l’efficacité d’un algorithme, on étudie la suite qui lie la taille des données du problème avec le nombre d’opérations de l’algorithme.

Définition (suite numérique)

Une suite numérique est une application de \N dans \R.

Exemple

• 1, 2, 3, 4, 5, 6, 7, 8, 9, ...
• 3, 3, 3, 3, 3, 3, 3, 3, 3, ...
• 1, 2, 4, 8, 16, 32, 64, ...
• 2, 4, 6, 8, 10, 12, 14, ...

Vocabulaire

On peut décrire la suite avec une formule explicite ou avec une formule récursive.

Exemple

Formules explicite :
\ u : n \mapsto\ \ 3 : 3, 3, 3, 3
\ v : n \mapsto\ \ n : 0, 1, 2, 3
w : n \mapsto 2n : 0, 2, 4, 6, 8
\ r : n \mapsto 2^n\ : 1, 2, 4, 8, 16, 32

V_{n} = \begin{cases} & 0 \text{ si } n = 0 \\\\ & V_{n-1} \text{ si } n \neq 0 \end{cases}

W_n = \begin{cases} & 0 \text{ si } n = 0 \\\\ & W_{n-1}+2 \text{ si } n \neq 0 \end{cases}

R_n = \begin{cases} & \text{ si } n = 0 \\\\ & R_{n-1} \text{ si } n \neq 0 \end{cases}

Définition (Domination)

Soient U et R deux suites numérique, on dit que U domine R si :
\exists\ M > 0, M \in \R, \exists\ n \in \N, \forall_n > n_0, |R_n| \leq M.|U_n|

On note R = O(u) ou R \ll U (celle qui domine est celle qui croît le plus vite)
On note \Omega(U) l’ensemble des suites qui domine U.
U \in O(D)

Propriété

Si U, V, W sont des suites et m, w des nombres réels, alors :

• Si U \ll V et V \ll W alors U \ll W
• Si U, V \ll W alors m.U + V \ll w
• Si \forall n \in \N, w.V \leq m.|W_n| alors V \leq W
• L’ensemble O(1) est l’ensemble des suites bornées
• L’ensemble O(V) est égale à l’ensemble |V|.O(1) (=(V_n.U_n)_{n\in\N} avec U suite bornée).

Remarque

Si U, F, W sont des suites, alors :

• U \ll U (dominé par elle-même)
• O(U).O(F) = O(F.U)
• Si U\ll W, alors U\times V\ll W\times V

Notation

Si U et V sont des suites et que on a U\ll V et V\ll U on note U = \Theta(U) (ou V =\Theta(U)) -> c’est une relation d’équivalence.

Exemple

• 1 = O(n) mais n \neq O(1)
• 4n^5+3n^4+10n+20=\Theta(n^5)
• log(n) = \Theta(ln(n))
• n.ln(n)\neq\Theta(ln(n)) | ln(n) = \Theta(n.ln(n))

3. Terminaison, correction et complexité d’un algorithme

Cf. TD1reponses

• Terminaison de l’algorithme : L’algorithme se termine t’il ? (oui/non)
• Correction : les données en sortie de l’algorithme sont-elles conforme au problème à résoudre (oui/non)
• Complexité : Combien d’opérations élémentaires l’algorithme effectue t’il ? Quelle place en mémoire occupe t’il ? (Suite numérique en fonction de “taille” de données)
  • Dans le pire des cas : On cherche un objet sur lequel l’algorithme effectuera le plus grand nombre d’opérations parmi tout les objets de taille n.
  • En moyenne : Une moyenne de nombre d’opérations selon une distribution de probabilités sur les objets de taille n. Souvent une distribution uniforme.

Exemple de tri “à bulle”

Entrée : Tableau d’entiers T de taille m
Sortie : Tableau d’entiers G triés selon l’ordre croissant. Il faut que G contienne les “mêmes” entiers que T.

void trie_a_bulle(int * T, int m) {
    int bool1 = 0;
    for(int i = 0; i < m; i++) {
        if (T[i] > T[i + 1]) {
            bool1 = 1;
            int tmp = T[i + 1];
            T[i + 1] = T[i];
            T[i] = tmp;
        }
    }
    if (bool1 != 0) return trie_a_bulle(T, m--);
}

4. Techniques de structuration de la mémoire

Exemple de données

• Arborescence des fichiers
• Dictionnaire
• Expressions formelles
• Nombre entier sur 4 octets
• Variables de fonction

Les données doivent être organisées dans la mémoire machine qui n’est qu’un grand tableau contenant des cases de 8 bits associées à des adresses.

Illustration

Afin de structurer ses données dans la mémoire on utilise deux techniques (souvent simultanément).

• Arithmétique des adresses
  • Par exemple :
    • tableau, nombre sur plusieurs octets aux adresses contiguës, structure
    • Sudoku (tableau/matrice de 9x9) :

Donne :

case(i, j) = tableau[i + (9 * j)]
tableau[k] = case(k % 9, k / 9)

• Mémoriser des adresses
  • Par exemple les pointeurs mémorise des adresses.

5. Liste chaînée

Une liste chaînée est composée de cellule avec deux champs.

• une valeur (par exemple un nombre entier)
• un pointeur sur une autre cellule

Illustrations

#define <stdlib.h>

typedef struct cel {
    int valeur;
    struct cel * suivant;
} Cellule;

typedef Cellule * Liste; // liste est synonyme de cellule*


Cellule * creerCellule(int a) {
    cellule * p = malloc(sizeof(cellule));
    if(p == NULL) return exit(1);
    (*p).valeur = a; // p -> suivant = a est équivalent
    (*p).suivant = NULL; // ne pointe sur rien

    return p; // on retourne l'adresse
}

Ajouter une liste

void ajouterListe(Liste * l, int a) {
    cellule * c = creerCellule(a);
    c -> suivant = *l;
    *l = c;
}

Supprimer une liste

Pour cela on prend le premier élément de la liste et on le supprime et on le rend NULL jusqu’à mettre le dernier élément = NULL.

void suppListe(Liste * l) { // version récursive - sans boucle
    if(*l == NULL) return;
    suppListe(l(*l) -> suivant);
    free(*l);
    *l = NULL;
}

Rechercher dans une liste

int chercheListe(Liste l, int val) {
    if(l == NULL) return 0; // cas où la liste est vide
    if(l -> valeur == val) return 1;
    chercheListe(l -> suivant, val);
}

6. Arbres : parcours en profondeurs

Cf. TD2

Un arbre enraciné (ou arborescence) est une structure formelle que l’on rencontre dans de nombreuse situations. Les arbres sont souvent représenté avec la racine en haut et les feuilles en bas.

Illustrations

graph TD;
/-->home & proc & dev & foot;
home-->login1 & login2 & key;
login1-->docs & vinte;

Arbre binaire étiqueté par des nombre :

graph TD;
3-->2 & 5;
2-->1;
5-->6 & 20;
20-->7;

Arbre binaire non étiqueté :

On peut caractériser un arbre par une définition récursive :

Définition (arbre binaire non étiqueté, ABNE)

Un ABNE est :

• Soit l’arbre vide.
• Soit l’assemblage de deux arbres (un à gauche et un à droite).

Exemple

Définition (plus symbolique et équivalente) :

Arbre BNE := arbreVide | ArbreBNE * ArbreBNE

Définition (Arbre Binaire étiqueté par des entiers)

Arbre BE := arbreVide | ArbreBE * ArbreBE * ℤ

Exemple

En C

typedef struct noeud {
    int etiquette;
    struct noeud * arbreGauche;
    struct noeud * arbreDroit;
} Noeud;


typedef Noeud * Arbre;

Arbre: a = NULL; // a est l'arbre vide

Parcours d’arbre

Pour représenter un arbre par une liste de mots (ou de nombres).

Parcours en préfixé

• Nommer l’étiquette de la racine de l’arbre ou indiquer si l’arbre est vide.

• Parcourir le sous-arbre de gauche en préfixé

• Parcourir le sous-arbre de droite en préfixe

  • Exemple :
    
    Un parcours préfixé de cet arbre donne : 1\ 3\ 1\perp\perp2\perp\perp7\perp8\perp\perp

  /* On utilise les stuct définit plus haut */
  void parcoursPre(Arbre a) {
      if (a == NULL) {
          printf("Vide");
          return;
      }
      printf("%d ", a -> etiquette);
      parcoursPre((*a).arbreGauche); // même chose, notation différente
      parcoursPre(a -> arbreDroit);
  }
  

On peut *(re)*fabriquer un arbre à partir de son parcours en préfixé.

Parcours en infixé :

• Si l’arbre n’est pas vide :

  • On parcours en infixé le sous-arbre de gauche
  • On écrit l’étiquette de la racine
  • On parcours le sous-arbre de droite

• Sinon :

  • On écrit “vide”

Exemple

Un parcours infixé de cet arbre donne : \perp 2 \perp 1 \perp

Un parcours infixé de cet arbre donne : \perp 2 \perp 1 \perp
==> Deux arbre différents peuvent donner le même parcours infixé.

Parcours suffixe

• Sous-arbre de gauche
• Sous-arbre de droite
• Afficher l’étiquette de la racine

7. Pile, File, Liste chainée circulaire, Parcours en largeur d’arbres

Cf. TD3

Une pile (ou une file) est un conteneur d’objet qui mémorise l’ordre dans lequel les objets ont été déposés.

Lorsque l’on retire un objet d’une pile on retire le dernier objet qui a été déposé

Exemple en C

void empiler(Pile * p, int i); // ajoute i à la pile
int depiler(Pile * p); // renvoie le dernier élément de la pile
int estVideP(Pile p); // renvoie 1 si la liste est vide
/*
    Aussi probablement une fonction qui initialise
    une pile et une autre qui libère la pile.
*/

Pile p:
  // TODO: instructions initialisation de p
  int a;
  // ici -> état 0
  empiler(&p, 1); // -> état 1
  empiler(&p, 2); // -> état 2
  a = depiler(&p); // -> état 3 | a = 2
  a = depiler(&p); // -> état 4 | a = 1 et la pile est vide
  // TODO: instructions détruire la pile

Lorsque l’on retire un objet d’une file on retire le premier objet qui a été déposé

Exemple en C

void enfile(File * f, int i); // ajoute i à la file
int defile(File * f); // renvoie la tête de liste
int estVideF(file f); // renvoie 1 si la liste est vide
/*
    Aussi probablement une fonction qui initialise
    une file et une autre qui libère la file.
*/

File f:
  // TODO: instructions initialisation de p
  int a;
  // ici -> état 0
  enfiler(&p, 1); // -> état 1
  enfiler(&p, 2); // -> état 2
  a = defiler(&p); // -> état 3 | a = 1
  a = defiler(&p); // -> état 4 | a = 2
  // TODO: instructions détruire la pile

Exemple d’un arbre

flowchart TD
1([1])---2([1]) & 3([3])
2---4([1])---7([4])
3---5([2]) & 6([7])
6---8([1])---9([2])

Parcours en largeur : 7, 1, 3, 1, 2, 7, 4, 1, 2

Exemple en C pour l’utilisation d’une file dans un arbre

// définition de Arbre précédemment dans le cours
void parcours_en_largeur(Arbre a) {
    File_Arbre f; // instanciation de la file
    initialiser(&f); // initialisation de la file
    enfiler(&f, a); // enfiler(File_Arbre * f, Arbre a); | on enfile des arbres
    while(!estVideF(f)) { // tant que la file n'est pas vide
        a = defiler(&f);
        if(a != NULL) {
            printf("%d ", a); // affichage de l'étiquette a
            enfiler(&f, a -> arbreGauche); // on enfile le fils gauche
            enfiler(&f, a -> arbreDroit); // on enfile le fils droit
        }
    }
    detruireFile(&f); // on détruit la file
}

Implantation en C

Manière 1

• Avec realloc (pas optimale)
• Utilisation de marqueurs/curseur :
  • Grand tableau (exemple 100)
  • Curseur début et curseur fin au début
  • Quand on rajoute un élément on décale le curseur début vers la droite
  • Quand on retire un élément on regarde la valeur qu’il y a au curseur fin, on extraie l’élément et on décale le curseur fin vers la droite
  • On sait si la file est vide si les deux marqueurs sont au même endroit
  • Si notre liste prédéfinie est remplie et qu’on veut toujours rajouter un élément, on fait : (début + 1) % 100 avec 100 la taille de la liste prédéfinie. Ca permet au marqueur début de revenir au début de la liste
  • Problème de ce système : le marqueur début peut rattraper le marqueur fin -> il faut penser à vérifier qu’on dépasse pas la taille de la file (création d’un nouveau tableau plus grand ? (realloc? nouveau malloc?)) A cause de ce problème parfois on doit faire plus d’opérations pour ajouter un élément

Manière 2

• Liste chaînée circulaire
  Illustration :
  

typedef struct cela {
    Arbre a;
    struct cel * suivant;
} CelluleA;


typedef struct cela * ListeA;
ListeA a = NULL;

int estVideF(FileA f) {
    return f == NULL;
}

void enfiler(FileA * f, Arbre a) {
    CelluleA * c = (celluleA*)malloc(sizeof(CelluleA));
    c -> a = a; // ici la cellule pointe sur elle-même
    if(*f == NULL) {
        c -> suivant = c;
        *f = c;
        return;
    }
    temp = (*f) -> suivant;
    (*f) -> suivant = c;
    c -> suivant = temp;
    (*f) = c;
}

int defiler(FileA * f);

File_arbre.c :

#include<stdlib.h>

// on suppose que le type Arbre est défini

typedef struct cellulA {
   Arbre a;
   struct cellulA* suivant;
} CelluleA;

typedef CelluleA* FileA;

int estVideFA(FileA f) {
   return NULL == f;
}
void enfiler(FileA* f,Arbre a) {
   CelluleA * c = malloc(sizeof(CelluleA));
   c -> a = a;
   if(c == NULL) exit(EXIT_FAILURE);
   if(*f == NULL) {
      c - >suivant=  c;
      *f = c;
   } else {
      c -> suivant = (*f) -> suivant;
      (*f) -> suivant = c;
      *f = c;
   }
}

int main() {
    return 0;
}

8. Ensemble et dictionnaire

Valeur ou objet

Une valeur est quelque chose de théorique, alors qu’un objet existe en mémoire.
Plusieurs objets différents peuvent avoir une même valeure.

Exemple

int a;
// ...
a = 3; // a ici est l'objet
c = a * 2; // a ici est la valeure

Arbre a = ass(anul(), anul(), 3);
Arbre b = ass (a, a, 4);

Ensemble

Un ensemble est un conteneur qui mémorise des valeurs.

Exemple (ensemble d’entiers)

Ensemble * e = initialiser();
ajouter(e, 4);
ajouter(e, 3);
estDans(e, 3); // doit renvoyer 1
estDans(e, 5); // doit renvoyer 0
supprimer(e, 3);
estDans(e, 3); // doit renvoyer 0
detuire(e);

Implémentation (d’ensemble)

• Liste chaînée
  • Ajout : \Theta(1)
  • Recherche : \Theta(n)
• Tableau
• Arbre binaire de recherche
  • Ajout : \Theta(log(n))
  • Recherche : \Theta(log(n))
• Table de hachage

“Dictionnaire”

En plus d’un ensemble, chaque valeure mémorisée est associée à un objet.

9. ABR (Arbre binaire de recherche)

Cf. TD4

Définition (ABR)

Soit un arbre binaire étiqueté par des valeurs qui peuvent être toujours comparées entre elles (i.e les valeurs sont donc des éléments d’un ensemble totalement ordonnés, par exemple les entiers).

On dit que c’est un arbre binaire de recherche si il vérifie :

• Soit c’est un arbre vide
• Soit :
  • Ses sous-arbre (gauche et droite) sont des ABR
  • Toutes les étiquettes du sous-arbre de gauche sont strictement inférieur à l’étiquette de la racine et toutes les étiquettes du sous-arbre de droite sont strictement supérieur à l’étiquette de la racine.

Exemple

8 3 16 17 23 2 5 3 1 9 7
En partant d’un arbre vide, on veut ajouter la liste de nombres.
On commence par 8, on l’ajoute (ass(anul(), anul(), 8)
Ensuite on ajoute 3, on l’ajoute en suivant la définition de l’ABR, donc on l’ajoute sur la gauche.
Ensuite pour le 16, en comparant 8 et 16 on se rend compe que 16 est plus grand que 8 donc on va a droite et on le met sur la case vide.
Pour 17, on va a droite car 8 < 17 et 16 < 17.
Etc, on procède récursivement jusqu’à atteindre cet arbre :

Remarque

Selon l’ordre d’ajout des éléments on peut obtenir des arbres différents, par exemple des arbres “file de fer”

Définition (profondeur d’un nœud)

Dans un arbre, la profondeur d’un noeud est le nombre de branche parcourues par un chemin entre la racine et ce nœud.

Définition (hauteur d’un arbre)

La hauteur d’un arbre est le maximum des profondeurs de ses nœuds.

Le nombre maximale de nœuds d’un arbre de hauteur h est : 2^{h+1}-1

Implantation en C

typedef struct noeudABR {
    int entier;
    struct noeudABR * g;
    struct noeudABR * d;
    void * objet; // utile pour les dictionnaires
    int hauteur; // utile pour équilibrer les arbres (voir chapitre 10)
} NoeudABR;
typedef NoeudABR * ABR;

void ajouter(ABR * arbre; int val) {
    if (*arbre == NULL) {
        *arbre = (NoeudABR*)malloc(sizeof(NoeudABR));
        if (*arbre == NULL) exit(1);
        (*arbre) -> entier = val;
        (*arbre) -> g = NULL;
        (*arbre) -> d = NULL;
    } else {
        if ((*arbre) -> entier < val) {
            ajouter(&(*arbre) -> d, val);
        }
        if ((*arbre) -> entier > val) {
            ajouter(&(*arbre) -> g, val);
        }
        /*
            Dans cet exemple, on ne fait rien si on a une égalité
            entre `(*arbre) -> entier` et `val`.
        */
    }
}

Pour retirer une racine, on doit mettre à la place de l’arbre qu’on retire quelque chose :

• Qui existe
• Qui respecte la cohérence de la définition d’un ABR

-> On récupère la valeur maximale de l’arbre et on met cette dernière à la place de la racine (dans ce cas là)

NoeudABR * ExtraireMax(ABR * a);
void       retirer(ABR * a, int val);

10. AVL (ABR équilibré)

Cf. TD5

On souhaite améliorer nos ABR et éviter d’avoir des arbres trop “allongés” (genre file de fer) -> on veut des arbres avec une hauteur pas trop grande pour une taille donnée.

Définition

Taille d’un arbre

La taille d’un arbre est le nombre de noeud

Arbre binaire équilibré

On dit qu’un arbre binaire équilibré si :

• c’est l’arbre vide
• le sous-arbre de gauche et le sous-arbre de droite soit équilibré
  • La différence de hauteur entre le sous-arbre de gauche et le sous-arbre de droite est strictement inférieure à deux en valeur absolue.
    Exemple :
    

Théorème

La hauteur d’un arbre équilibré de taille n est inférieure à 2\times log_e(n).

On souhaite utiliser et maintenir des ABR équilibrés. Pour cela on conserve dans chaque noeud A la hauteur du sous-arbre dont la racine est le noeud A. À chaque ajout ou suppression d’un noeud, s’il provoque un déséquilibre, on effectuera une “rotation d’arbre” pour le rendre équilibré.

Définition

AVL

Un AVL (nom des concepteurs) est un ABR (Arbre Binaire de Recherche) équilibré.

Après un ajout simple ou une suppression simple dans un AVL, s’il y a déséquilibre la différence de hauteur ne peut-être plus de 2.

Rotation

Remarques

Une rotation conserves :

• les étiquettes des noeuds
• la structure ABR
  Une rotation réduit une des hauteurs

Sur la hauteur

Remarques

Chaque ajout ou suppression entraînera soit :

• 0 rotation
• 1 rotation simple
• 1 rotation double

Amélioration

La hauteur mémorisé peut-être remplacé par la différence de hauteur entre le sous-arbre droit et celui de gauche. (-1, 0, -1, soit 2 bits).

Preuves

Arbre complet

Définition

Un arbre complet de hauteur h est un arbre qui contient le maximum de noeud pour sa hauteur.

Propriété

La taille d’un arbre complet de hauteur h est 2^{h+1}-1

Hauteur complète

Définition

Soit un arbre A sa hauteur complète la hauteur de son plus grand sous-arbre :

• ayant la même racine que A
• complet

Exemple

Lemme

La hauteur complète d’un arbre équilibré de hauteur h est supérieur à \dfrac{h}{2}

Preuve du théorème

Soit A un arbre équilibré de taille n et de hauteur h, alors selon le lemme :
2^{\frac{h}{2}+1} \leq n \leq 2^{h+1}
\frac{h}{2}+1\leq log_2(n) \leq h+1
h+2 \leq 2log_2(n) \leq 2h+2
=> Donc la hauteur de A est inférieure à 2\times log_2(n)

Preuve du lemme

Par réccurence sur la hauteur
Si h = 1, on suppose la propriété vrai jusqu’à h \leq n

Soit C un hauteur n+1 :

• Si n pair : n = 2k
  • Les hauteurs complète A et B sont k
  • La hauteur complète de C est k+1, or k+1 = 2k+1 = n+1
• Si n est impair : n = 2k+1
  • …

11. Graphe

graph LR;
1-->2 & 3 & 5 & 8;
2-->9;
3-->5;
4-->3;
5-->6 & 7 & 8;
6-->4 & 7;
7-->6 & 7;
8-->1 & 7 & 9;
9-->7 & 9;

En mémoire, on peut représenter un graphe par une matrice d’adjacence :

En C :

#define MAX 100
typedef struct gra {
    int graphe[MAX][MAX];
    int nbSommets;
} Graphe;

On peut représenter en mémoire un graphe par des listes d’adjacences :
1: 2, 3, 5, 8
2: 9
3: 5
Utile lorsque le nombre d’arcs du graphe est \ll n^2 (n le nombre de sommets).

Remarques

Le schéma précédent illustre un graphe orienté (arc avec un sens). On rencontre aussi des graphes non-orientés (arrêtes).

Vocabulaire

Chemin dans un graphe : Longueur d’un chemin.
Circuit : Dans le graphe ci-dessous, 2 et 3 forment un circuit (je crois?).

graph LR
1-->2
2-->3
3-->2 & 5

Parcours en profondeur dans un Graphe

graph LR;
1-->2 & 7;
2-->9;
3-->1 & 5;
4-->3;
5-->6 & 7;
6-->4 & 7;
7-->8;
8-->1 & 7 & 9;
9-->7 & 9;

// On suppose la structure en C précédente

void estAccessible(Graphe * g, int s, int * tab);

/*
`sd` Sommet de Départ et `sa` Sommet d'Arrivé
On prend *g et pas g pour éviter de recopié le graphe (car il est grand)
donc on prend son adresse.
*/
int chemin(Graphe * g, int sd, int sa) {
    int T[g->nbSommets]; // indique les sommets visités
    for(int i = 0; i < g->nbSommets; i++)
        T[i] = 0;
    estAccessible(g, sd, T);

    return T[sa];
}

/*
`tab` est un tableau contenant au départ que des cases vides à 0
et la fonction met à 1 les cases dont les indices sont les sommets
accessibles par un chemin partant du sommet `s`.
*/
void estAccessible(Graphe * g, int s, int * tab) {
    if(tab[s] == 1) // Si `tab[s]` à déjà été visité
        return;
    tab[s] = 1;
    // Ensuite on parcours tout les successeurs possibles
    for(int i = 0; i < g->nbSommets; i++)
        if(g->graphe[s][i] == 1)
            return estAccessible(g, i, tab); // on continue le parcours à partir de `i`
}

Remarque

On pourrait améliorer la fonction en la quittant lorsque le sommet d’arrivé sa est atteint.

Trouver les circuits

graph TD
A[ ]-->B & C;
B[ ]-->D & E;
C[ ]-->E;
D[ ]-->F;
E[ ]-->D & F;
F[ ]

graph TD
A[ ]-->B & C;
B[ ]-->C & D;
C[ ]-->E;
D[ ]-->C & F;
E[ ]-->D & F;
F[ ]

Définition de pré-visite, post-visité et revisité

Lors d’un parcours en profondeur, chaque sommet peut-être soit :

• jamais visité
• pré-visité puis post-visité (visité une première fois) et éventuellement être revisité (soit visité une nouvelle fois soit au court d’un autre parcours soit pendant le même)
  

Graphe (étiqueté)

Un graphe étiqueté est un graphe où chaque arc possède une étiquette (un nombre, une lettre…)

Vocabulaire (longueur d’un chemin d’un graphe étiqueté)

Par convention, la longueur d’un chemin dans un graphe étiqueté par des nombres est la somme des étiquettes des arcs empruntés par le chemin. La longueur du chemin vide est nulle.

Exemple

graph LR
1==2==>2
1--1-->3
2==3==>4
3--6-->2
4==2==>5

La longueur de 1, 2\rightarrow 2, 2, 2\rightarrow4, 4, 4\rightarrow5, 4, 4\rightarrow5, 5 est 2+3+2=7

Définition (plus court chemin et distance)

Soit un graphe étiqueté par des nombres et deux sommets d et a du graphe.
S’il existe un chemin allant de d à a qui possède la plus petite longueur parmis les chemins allant de d à a alors ce chemin est appelé le plus “court” chemin allant de d à a et sa longueur est appelée la distance de d à a.

Exemple

graph LR
1==1==>2
1--9-->3
2==1==>3

Ici la distance de 1 à 3 vaut 2 et le plus court chemin est 1, 2, 3

Contre-Exemple

graph LR
1--1-->2
1-- -1 -->1

graph TD
3
4

Dans ces 2 cas il n’y a pas de plus court chemin.
On pourrait dire que :

• pour le cas 1, la distance de 1 à 2 est -\infty
• pour le cas 2, la distance de 3 à 4 est +\infty

Problème algorithmique

Entrée: graphe `g`, `d`, `a` deux sommets de `g`
Sortie: plus court chemin (s'il existe) allant de `d` vers `a`

Illustration

Propriété

Soit un graphe G étiqueté par des nombres positifs ou nuls et d’un sommet
Si pour un sommet a on appelle C_a le plus court chemin allant de d vers a, alors :
C_{a} = C_{p} \circ p\rightarrow a
avec p une puissance de a et C_p le plus court chemin allant de d vers p
b(C_{p)} + l(p\rightarrow a) = \min(l(C_{s)} + l(s\rightarrow a),\ t_{q})\ \text{$s$ prédésseur de $a$}
avec l(C_{p}) longueur du chemin C_{p} et l(p\rightarrow a) étiquette de l’arc allant de p\rightarrow a. Si de plus d = a il faut prendre en compte le chemin vide.

Dorénavant les étiquettes seront positives ou nulles.

Algorithme de Dijkstra

Entrée: graphe `g` étiquetté, `d` sommet
Sortie: Pour chaque sommet accessible à partir de `d` : le plus court chemin allant de `d` à `i` et la distance de `d` à `i`

Illustration

Comment traité un sommet pas encore traité ?

Exemple