algorithmes de parcours d'un graphe

Parcours en largeur

Le parcours en largeur d'un graphe est similaire au parcours en largeur d'un arbre. À la différence des arbres, les graphes peuvent contenir des cycles, ce qui nous permet de revenir au même nœud. Pour éviter de traiter un nœud plusieurs fois, nous utilisons un tableau booléen visited.

Dans un parcours en largeur, tous les noeuds à une profondeur i doivent avoir été visités avant que le premier noeud à la profondeur i+1 ne soit visité. Un tel parcours nécessite l’utilisation d’une file d’attente pour se souvenir des branches qui restent à visiter.

Algorithme PL(G, s)
    F : File d’attente
    pour chaque sommet u de G faire 
        visite[u] = False
    FinPour 
    visite[s]=True
    F .enfiler(s)
    Tantque F != Vide faire
        u=F.defiler()
        pour chaque voisin v de u faire
            Si visite(v) = False ALORS 
                visite(v)= True
                F.enfiler(v) 
            FinSI
        FinPour
    FinTantque
FinAlgoritme

class Graphe:

    def __init__(self, noeuds):
        self.matriceAdj = noeuds.copy()

    def ParcoursLargeur(self, debut):
        file = []
        visites = [False] * (len(self.matriceAdj))
        file.append(debut)
        while file:
            courant = file.pop(0)
            visites[courant] = True
            print(courant+1, end=' ,')
            for i in range(len(self.matriceAdj[courant])):
                if self.matriceAdj[courant][i] > 0 and visites[i] == False:
                    file.append(i)
                    visites[i] = True

# test
matriceAdj = [[0, 0, 1, 1, 1, 1],
              [0, 0, 1, 0, 0, 0],
              [1, 1, 0, 0, 0, 0],
              [1, 0, 0, 0, 1, 0],
              [1, 0, 0, 1, 0, 0],
              [1, 0, 0, 0, 0, 0],
              ]
g = Graphe(matriceAdj)
print("Parcours en largeur ")
g.ParcoursLargeur(0)

# représentation d'un graphe à l'aide de liste d'adjacence
class Graphe:
 
    def __init__(self):
        # créer un dictionnaire pour stocker la liste d'adjacence
        self.Liste = {}
 
    # Ajouter une arête entre deux sommets
    def addArete(self, u, v):
        if v not in self.Liste:
            self.Liste[v] = []
 
        if u not in self.Liste:
            self.Liste[u] = []
 
        self.Liste[u].append(v)
 
    # Parcours en largeur
    def Parcours_Largeur(self, s):
        visited = [False] * (len(self.Liste))
 
        # File d'attente
        file = []
        file.append(s)
 
        while file:
            # defiler et afficher le sommet en tete de la file
            s = file.pop(0)
            if visited[s-1] == False:
                print(s, end=" ")
                visited[s-1] = True
 
            # pour chaque voisin i de s faire
            for i in self.Liste[s]:
 
                if visited[i-1] == False:
                    print(i, end=" ")
                    file.append(i)
                    visited[i-1] = True
 
 
g = Graphe()
g.addArete(1, 3)
g.addArete(1, 4)
g.addArete(1, 5)
g.addArete(1, 6)
g.addArete(2, 3)
g.addArete(3, 1)
g.addArete(3, 2)
g.addArete(4, 1)
g.addArete(4, 5)
g.addArete(5, 1)
g.addArete(5, 4)
g.addArete(6, 1)
 
print("Parcours en largeur à partir du sommet 1")
g.Parcours_Largeur(1)

Parcours en largeur à partir du sommet 1
1 3 4 5 6 2

Applications

Le chemin le plus court et l'arbre couvrant minimum pour le graphe non pondéré,
le chemin le plus court est le chemin avec le plus petit nombre d'arêtes. Avec le parcours en largeur, nous atteignons toujours un sommet d'une source donnée en utilisant le nombre minimum d'arêtes. De plus, dans le cas de graphe non pondérés, tout arbre couvrant est un arbre couvrant minimum.
nous pouvons utiliser le parcours en profondeur pour trouver l'arbre couvrant minimum.
Réseaux peer-to-peer. Dans les réseaux peer-to-peer, comme BitTorrent, le parcours en largeur est utilisé pour rechercher tous les nœuds voisins.
Robots d'indexation dans les Moteurs de Recherche: les Robots construisent des index à l'aide de parcours en largeur.
L'idée est de commencer à partir de la page source et de suivre tous les liens à partir de la source et de continuer à faire la même chose.
parcours en profondeur peut également être utilisé pour les Robots d'indexation, mais l'avantage avec le parcours en largeur est, la profondeur ou les niveaux de l'arbre Construit peuvent être limités.
Sites de réseaux sociaux: dans les réseaux sociaux, nous pouvons trouver des personnes à une distance donnée "k" d'une personne en utilisant le parcours en largeur étendue jusqu'à au niveau "k".
Détection de cycle dans un graphe non orienté: Dans les graphes non orienté, vous pouvez utiliser le parcours en largeur ou le parcours en profondeur pour détecter le cycle. Dans le graphique orienté, seule le parcours en profondeur peut être utilisé.
Diffusion en réseau: dans les réseaux, un paquet diffusé suit le parcours en largeur pour atteindre tous les noeuds.
Trouver tous les noeuds dans un seul composant connecté : Nous pouvons soit utiliser le parcours en largeur ou le parcours en profondeur pour trouver tous les noeuds accessibles à partir d'un noeud donné.
Recherche de chemin : Nous pouvons soit utiliser le parcours en largeur ou le parcours en profondeur pour déterminer s'il existe un chemin entre deux sommets.

De nombreux algorithmes tels que Prim et Dijkstra utilisent une structure similaire au parcours en largeur.

Parcours en profondeur

Le parcours en profondeur d’un graphe est similaire au parcours en profondeur d’un arbre. À la différence des arbres, les graphes peuvent contenir des cycles, ce qui nous permet de revenir au même nœud. Pour éviter de traiter un nœud plusieurs fois, nous utilisons un tableau booléen visited.

Algorithme parcours_profondeur(G, s, visited)
    visited[v]=True
    Ecrire(v)
    pour chaque voisin v de u faire
        SI visited[v]=False ALORS
            parcours_profondeur(G, v, visited)
        FinSi
    FinPour
FinAlgorithme

class Graphe:

    def __init__(self, noeuds):
        self.matriceAdj = noeuds.copy()

    def ParcoursProfondeur(self, debut):
        global visites
        visites[debut] = True
        print(debut+1, end=' ,')
        for i in range(len(self.matriceAdj[debut])):
            if self.matriceAdj[debut][i] > 0 and visites[i] == False:
                self.ParcoursProfondeur(i)


matriceAdj = [[0, 0, 1, 1, 1, 1],
              [0, 0, 1, 0, 0, 0],
              [1, 1, 0, 0, 0, 0],
              [1, 0, 0, 0, 1, 0],
              [1, 0, 0, 1, 0, 0],
              [1, 0, 0, 0, 0, 0],
              ]
visites = [False] * (len(matriceAdj))
g = Graphe(matriceAdj)
print("Parcours en profondeur à partir du sommet 1")
g.ParcoursProfondeur(0)

# représentation d'un graphe à l'aide de liste d'adjacence
class Graphe:
    def __init__(self):
        # créer un dictionnaire pour stocker la liste d'adjacence
        self.Liste = {}
 
    # Ajouter une arête entre deux sommets
    def addArete(self, u, v):
        if v not in self.Liste:
            self.Liste[v] = []
 
        if u not in self.Liste:
            self.Liste[u] = []
 
        self.Liste[u].append(v)
 
    # Parcours en profondeur
    def Parcours_profondeur(self, s, visited):
 
        # Marquer le noeud courant comme visité et l'afficher
        visited[s-1] = True
        print(s, end=" ")
 
        # recommencer avec tous les noeuds voisins
        for i in self.Liste[s]:
            if visited[i-1] == False:
                self.Parcours_profondeur(i, visited)
 
 
g = Graphe()
g.addArete(1, 3)
g.addArete(1, 4)
g.addArete(1, 5)
g.addArete(1, 6)
g.addArete(2, 3)
g.addArete(3, 1)
g.addArete(3, 2)
g.addArete(4, 1)
g.addArete(4, 5)
g.addArete(5, 1)
g.addArete(5, 4)
g.addArete(6, 1)
 
visited = [False] * (len(g.Liste))
print("Parcours en profondeur à partir du sommet 1")
g.Parcours_profondeur(1, visited)

Parcours en profondeur à partir du sommet 1
1 3 2 4 5 6

Applications

Pour un graphe non pondéré, le parcours en profondeur produit l'arbre couvrant minimum et l'arbre de chemin le plus court de tous les couples.
Détection de cycle dans un graphe
Tri topologique : Le tri topologique est principalement utilisé pour planifier des travaux à partir des dépendances indiquées entre les travaux. En informatique, les applications de ce type se situent dans la planification des instructions, l'ordre de l'évaluation des cellules de formule lors de la recalcul des valeurs de formule dans les tableurs, la détermination de l'ordre des tâches de compilation à exécuter dans les makefiles, la sérialisation des données et la résolution des dépendances de symboles dans les éditeurs de liens
Trouver des composants fortement connectés d'un graphe. un graphe orienté est appelé fortement connecté s'il y a un chemin de chaque sommet dans le graphe à chaque autre sommet.
Pour tester si un graphe est biparti: lorsque nous découvrons un nouveau sommet, colorez-le avec une couleur opposée à celle de ses parents, et pour chaque arc, vérifiez qu'il ne lie pas deux sommets de la même couleur. Le premier sommet d'un composant connecté peut être rouge ou noir

algorithmes de parcours d'un graphe

Théorie des graphes

Sommaire