Théorie des graphes

Notification de cookies

Nous utilisons des cookies pour améliorer votre expérience. En poursuivant votre navigation sur ce site, vous acceptez l'utilisation de cookies. Plus d'informations

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
            
                    # 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

  1. 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.
  2. 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.
  3. 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.
  4. 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".
  5. 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é.
  6. Diffusion en réseau: dans les réseaux, un paquet diffusé suit le parcours en largeur pour atteindre tous les noeuds.
  7. 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é.
  8. 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
            
                    # 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

  1. 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.
  2. Détection de cycle dans un graphe
  3. 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
  4. 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.
  5. 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

Partager ce cours avec tes amis :

Rédigé par M. ESSADDOUKI

Learning a new programming language is an easy thing, but the most difficult thing is how to design efficient algorithms for real-world problems, so don't be a programmer, be a problems solver.

Cours Similaires :