Chapitre 18 : Les graphes non orientés.

1. Définition:

Un graphe est une structure de données qui comporte des objets appelés "sommets".

Les graphes non-orientés :

Les sommets sont reliés entre eux par des arêtes n'ayant pas de sens.

Les arêtes forment des relations entre les sommets.

Un graphe est une structure de données relationnelles.

Les sommets peuvent aussi être appelés des noeuds.

2. Définitions:

Dans un graphe non-orienté :

• deux sommets sont adjacents si une arête les relie.
• deux arêtes sont adjacentes si elles ont un sommet en commun.
• Soit A et B deux sommets, on note A-B ou (A,B) une arête qui le relie.
• une chaîne reliant deux sommets est la succession d'arêtes adjacentes reliant ces deux points.
• un graphe est dit connexe si pour n'importe quelle paire de sommets, il existe une chaîne qui les relie.
• un graphe est dit complet si chaque sommet est adjacent à tous les autres.
• le degré d'un sommet correspond au nombre d'arêtes dont il est une extrémité.
• un cycle est une chaîne ayant pour extrémités un unique sommet.
• une boucle correspond à une arête ayant pour extrémités le même sommet.
• un graphe simple est un graphe ne comportant pas de boucles et que chaque paire de sommets n'est reliée que par une arête au maximum.

4. Stockage du type G = [V, E]:

Il existe plusieurs façons de stocker un graphe non-orienté dans Python, l'une d'elle est la création d'une liste de deux éléments :

• Le premier élément est une liste contenant les strings associés aux sommets.
• Le deuxième élément est une liste de tuples contenant deux valeurs. Chaque valeur est un string associé à un sommet. Le tuple représente une arête.

6. Matrice d'adjacence:

Il existe plusieurs façons de stocker un graphe non-orienté dans Python, l'une d'elle est la création d'une matrice d'adjacence.

S'il y a \(n\) sommets, on associe à chaque sommet un unique nombre entier de \([0;n-1]\).

On créait alors la matrice de taille \(n \times n\) contenant les valeurs \(a_{i,j}\) avec \(i\) et \(j\) deux nombres entiers appartenant à \([0;n-1]\).

\(a_{i,j}\) correspond au nombre d'arêtes reliant les sommets associés à \(i\) et \(j\).

8. Implémentation d’un graphe non orienté

Une manière simple de représenter un graphe non orienté en Python est d’utiliser un dictionnaire d’adjacence :

• les clés représentent les sommets,
• les valeurs sont des listes des sommets adjacents.

class GrapheNonOriente:
    def __init__(self):
        self.aretes = {}

    def ajouter_sommet(self, sommet):
        if sommet not in self.aretes:
            self.aretes[sommet] = []

    def ajouter_arete(self, sommet1, sommet2):
        self.ajouter_sommet(sommet1)
        self.ajouter_sommet(sommet2)
        self.aretes[sommet1].append(sommet2)
        self.aretes[sommet2].append(sommet1)

Dans cette implémentation :

• aretes est un dictionnaire contenant les listes d’adjacence,
• une arête entre sommet1 et sommet2 est ajoutée dans les deux sens,
• cela garantit que le graphe est bien non orienté.

12. Parcours en largeur d'un graphe (BFS - Breadth-First Search)

Le parcours en largeur est un algorithme utilisé pour explorer de manière systématique un graphe. Il commence à partir d'un noeud source donné, explore tous les noeuds voisins de ce noeud, puis passe aux voisins de ces voisins, et ainsi de suite. Cette méthode garantit que les noeuds sont visités dans l'ordre de leur distance par rapport au noeud source. L'algorithme BFS est particulièrement utile pour résoudre des problèmes de connectivité, la recherche du chemin le plus court et d'autres problèmes liés aux graphes.

Exemple :

Prenons un exemple simple pour illustrer le fonctionnement de BFS. Imaginons le graphe suivant :

Si nous utilisons BFS à partir du noeud source A, l'ordre de visite des noeuds sera : A, B, C, D. L'algorithme commence par le noeud source A, visite ensuite les noeuds B et C (qui sont les voisins directs de A), puis visite le noeud D, voisin de B.

Applications :

• La recherche du chemin le plus court entre deux noeuds.
• La détection de cycles dans un graphe.
• La modélisation des réseaux sociaux et des relations.
• La résolution de jeux de logique et de casse-tête.

Implémentation :

L'implémentation de l'algorithme BFS nécessite généralement l'utilisation d'une file (queue). Voici un exemple en pseudo-code :

BFS(graphe, noeud_de_départ):
    file = File()
    file.enfiler(noeud_de_départ)
    Marquer noeud_de_départ comme visité
    Tant que la file n est pas vide:
        noeud_actuel = file.defiler()
        Traiter noeud_actuel
        Pour chaque voisin du noeud_actuel dans le graphe:
            Si il est non visité:
                file.enfiler(voisin)
                Marquer voisin comme visité

Point important à retenir : il faut marquer quand on enfile et non quand on défile.

15. Parcours en profondeur d'un graphe (DFS - Depth-First Search)

Le parcours en profondeur est un algorithme utilisé pour explorer de manière systématique un graphe en suivant une branche jusqu'à ce qu'il atteigne un noeud terminal, puis il revient en arrière pour explorer d'autres branches. L'algorithme DFS est largement utilisé pour la recherche de chemins, la détection de cycles et d'autres problèmes liés aux graphes.

Exemple :

Prenons un exemple simple pour illustrer le fonctionnement de DFS. Imaginons le graphe suivant :

Si nous utilisons DFS à partir du noeud source A, l'ordre de visite des noeuds pourrait être : A, B, D, C. L'algorithme commence par le noeud source A, explore le noeud B, puis explore le noeud D, avant de revenir au noeud C.

Applications :

• La recherche de chemins dans un graphe.
• La détection de cycles dans un graphe.
• La génération de l'arbre couvrant minimal.

Implémentation :

Il y a deux implémentations possibles : une récursive et l'autre itérative.

• Récursive :

  Voici comment cela pourrait être implémenté en pseudo-code :

  DFS(graphe, noeud_actuel, liste_noeud_visite):
      marquer noeud_actuel comme visité en l'ajoutant à la liste
      Traiter noeud_actuel
      Pour chaque voisin du noeud_actuel dans le graphe:
          Si noeud_actuel n est pas visite:
              DFS(graphe, voisin, liste_noeud_visite)

• Itérative :

  Voici comment cela pourrait être implémenté en pseudo-code :

  DFS(graphe, noeud_de_départ):
      pile = Pile()
      pile.empiler(noeud_de_départ)
      On marque le noeud de départ comme étant visité
      Tant que la pile n est pas vide:
          noeud_actuel = pile.depiler()
          Traiter noeud_actuel
          Pour chaque voisin du noeud_actuel dans le graphe:
              Si voisin est non visité:
                  pile.empiler(voisin)
                  On marque voisin comme étant visité