Menu

Programme C ++ Depth First Search (DFS) pour parcourir un graphique ou une arborescence

  • Principal
  • Autre
  • Programme C ++ Depth First Search (DFS) pour parcourir un graphique ou une arborescence

depth first search c program traverse graph

Essayez Notre Instrument Pour Éliminer Les Problèmes

Ce didacticiel couvre la première recherche en profondeur (DFS) en C ++ dans laquelle un graphique ou un arbre est parcouru en profondeur. Vous apprendrez également l'algorithme et l'implémentation DFS:

La recherche en profondeur d'abord (DFS) est une autre technique utilisée pour parcourir un arbre ou un graphique.

DFS commence par un nœud racine ou un nœud de départ, puis explore les nœuds adjacents du nœud actuel en approfondissant le graphique ou une arborescence. Cela signifie que dans DFS, les nœuds sont explorés en profondeur jusqu'à ce qu'un nœud sans enfant soit rencontré.

Une fois le nœud feuille atteint, DFS fait marche arrière et commence à explorer d'autres nœuds de la même manière.

=> Regardez le guide de formation C ++ pour débutants ici.

Recherche en profondeur d

Ce que vous apprendrez:

Première recherche en profondeur (DFS) en C ++

Contrairement à BFS dans lequel nous explorons les nœuds dans le sens de la largeur, dans DFS, nous explorons les nœuds en profondeur. Dans DFS, nous utilisons une structure de données de pile pour stocker les nœuds explorés. Les arêtes qui nous mènent à des nœuds inexplorés sont appelées «arêtes de découverte» tandis que les arêtes menant aux nœuds déjà visités sont appelées «arêtes de bloc».

Ensuite, nous verrons l'algorithme et le pseudo-code de la technique DFS.

Algorithme DFS

  • Étape 1: Insérez le nœud racine ou le nœud de départ d'une arborescence ou d'un graphique dans la pile.
  • Étape 2: Pop l'élément supérieur de la pile et l'ajouter à la liste visitée.
  • Étape 3: Trouvez tous les nœuds adjacents du nœud marqué visité et ajoutez ceux qui ne sont pas encore visités, à la pile.
  • Étape 4 : Répétez les étapes 2 et 3 jusqu'à ce que la pile soit vide.

Pseudocode

Le pseudo-code pour DFS est donné ci-dessous.

Le pseudo-code pour DFS

A partir du pseudo-code ci-dessus, nous remarquons que l'algorithme DFS est appelé récursivement sur chaque sommet pour s'assurer que tous les sommets sont visités.

Traversées avec illustrations

Illustrons maintenant le parcours DFS d'un graphe. Pour plus de clarté, nous utiliserons le même graphique que celui que nous avons utilisé dans l'illustration BFS.

Illustrations DFS avec traversées

Soit 0 le nœud de départ ou le nœud source. Tout d'abord, nous le marquons comme visité et l'ajoutons à la liste visitée. Ensuite, nous poussons tous ses nœuds adjacents dans la pile.

Poussez tous les nœuds adjacents dans la pile

Ensuite, nous prenons l'un des nœuds adjacents à traiter, c'est-à-dire le haut de la pile qui est 1. Nous le marquons comme visité en l'ajoutant à la liste visitée. Cherchez maintenant les nœuds adjacents de 1. Comme 0 est déjà dans la liste visitée, nous l'ignorons et nous visitons 2 qui est le haut de la pile.

Illustration DFS - Étape 3

Ensuite, nous marquons le nœud 2 comme visité. Son nœud adjacent 4 est ajouté à la pile.

Illustration DFS Étape 4

Ensuite, nous marquons 4 qui est le haut de la pile comme visité. Le nœud 4 n'a que le nœud 2 comme son adjacent qui est déjà visité, donc nous l'ignorons.

Illustration DFS Étape 5

A ce stade, seul le nœud 3 est présent dans la pile. Son nœud adjacent 0 est déjà visité, donc nous l'ignorons. Maintenant, nous marquons 3 comme visité.

Illustration DFS Étape 6

Maintenant, la pile est vide et la liste visitée montre la séquence du parcours en profondeur d'abord du graphe donné.

Si nous observons le graphe donné et la séquence de parcours, nous remarquons que pour l'algorithme DFS, nous parcourons en effet le graphe en profondeur, puis nous le retraçons à nouveau pour explorer de nouveaux nœuds.

Implémentation de la recherche en profondeur d'abord

Implémentons la technique de traversée DFS en utilisant C ++.

#include #include using namespace std; //graph class for DFS travesal class DFSGraph { int V; // No. of vertices list *adjList; // adjacency list void DFS_util(int v, bool visited()); // A function used by DFS public: // class Constructor DFSGraph(int V) { this->V = V; adjList = new list(V); } // function to add an edge to graph void addEdge(int v, int w){ adjList(v).push_back(w); // Add w to v’s list. } void DFS(); // DFS traversal function }; void DFSGraph::DFS_util(int v, bool visited()) { // current node v is visited visited(v) = true; cout << v << ' '; // recursively process all the adjacent vertices of the node list::iterator i; for(i = adjList(v).begin(); i != adjList(v).end(); ++i) if(!visited(*i)) DFS_util(*i, visited); } // DFS traversal void DFSGraph::DFS() { // initially none of the vertices are visited bool *visited = new bool(V); for (int i = 0; i < V; i++) visited(i) = false; // explore the vertices one by one by recursively calling DFS_util for (int i = 0; i < V; i++) if (visited(i) == false) DFS_util(i, visited); } int main() { // Create a graph DFSGraph gdfs(5); gdfs.addEdge(0, 1); gdfs.addEdge(0, 2); gdfs.addEdge(0, 3); gdfs.addEdge(1, 2); gdfs.addEdge(2, 4); gdfs.addEdge(3, 3); gdfs.addEdge(4, 4); cout << 'Depth-first traversal for the given graph:'<

Production:

Traversée en profondeur pour le graphe donné:

0 1 2 4 3

Nous avons à nouveau utilisé le graphique dans le programme que nous avons utilisé à des fins d'illustration. On voit que l'algorithme DFS (séparé en deux fonctions) est appelé récursivement sur chaque sommet du graphe afin de s'assurer que tous les sommets sont visités.

Analyse d'exécution

La complexité temporelle de DFS est la même que celle de BFS, c'est-à-dire O (| V | + | E |) où V est le nombre de sommets et E est le nombre d'arêtes dans un graphe donné.

Comme pour BFS, selon que le graphe est peu peuplé ou densément peuplé, le facteur dominant sera respectivement les sommets ou les arêtes dans le calcul de la complexité temporelle.

DFS itératif

L'implémentation illustrée ci-dessus pour la technique DFS est de nature récursive et utilise une pile d'appels de fonction. Nous avons une autre variante pour implémenter DFS, à savoir ' Recherche itérative en profondeur d'abord ». En cela, nous utilisons la pile explicite pour contenir les sommets visités.

Nous avons montré ci-dessous l'implémentation pour DFS itératif. Notez que l'implémentation est la même que BFS à l'exception du facteur que nous utilisons la structure de données de la pile au lieu d'une file d'attente.

#include using namespace std; // graph class class Graph { int V; // No. of vertices list *adjList; // adjacency lists public: Graph(int V) //graph Constructor { this->V = V; adjList = new list(V); } void addEdge(int v, int w) // add an edge to graph { adjList(v).push_back(w); // Add w to v’s list. } void DFS(); // DFS traversal // utility function called by DFS void DFSUtil(int s, vector &visited); }; //traverses all not visited vertices reachable from start node s void Graph::DFSUtil(int s, vector &visited) { // stack for DFS stack dfsstack; // current source node inside stack dfsstack.push(s); while (!dfsstack.empty()) { // Pop a vertex s = dfsstack.top(); dfsstack.pop(); // display the item or node only if its not visited if (!visited(s)) { cout << s << ' '; visited(s) = true; } // explore all adjacent vertices of popped vertex. //Push the vertex to the stack if still not visited for (auto i = adjList(s).begin(); i != adjList(s).end(); ++i) if (!visited(*i)) dfsstack.push(*i); } } // DFS void Graph::DFS() { // initially all vertices are not visited vector visited(V, false); for (int i = 0; i < V; i++) if (!visited(i)) DFSUtil(i, visited); } //main program int main() { Graph gidfs(5); //create graph gidfs.addEdge(0, 1); gidfs.addEdge(0, 2); gidfs.addEdge(0, 3); gidfs.addEdge(1, 2); gidfs.addEdge(2, 4); gidfs.addEdge(3, 3); gidfs.addEdge(4, 4); cout << 'Output of Iterative Depth-first traversal: '; gidfs.DFS(); return 0; }

Production:

Sortie de la traversée itérative en profondeur d'abord:

0 3 2 4 1

Nous utilisons le même graphique que nous avons utilisé dans notre implémentation récursive. La différence de sortie est que nous utilisons la pile dans l'implémentation itérative. Comme les piles suivent l'ordre LIFO, nous obtenons une séquence différente de DFS. Pour obtenir la même séquence, nous pourrions vouloir insérer les sommets dans l'ordre inverse.

BFS contre DFS

Jusqu'à présent, nous avons discuté des techniques de traversée pour les graphiques, c'est-à-dire BFS et DFS.

Examinons maintenant les différences entre les deux.

BFSDFS
Signifie 'Recherche en largeur d'abord'Signifie 'Recherche en profondeur d'abord'
Les nœuds sont explorés en largeur niveau par niveau.Les nœuds sont explorés en profondeur jusqu'à ce qu'il n'y ait que des nœuds feuilles, puis rétrogradés pour explorer d'autres nœuds non visités.
BFS est exécuté à l'aide de la structure de données de file d'attente.DFS est effectué à l'aide de la structure de données de la pile.
Performances plus lentes.Plus rapide que BFS.
Utile pour trouver le chemin le plus court entre deux nœuds.Utilisé principalement pour détecter les cycles dans les graphiques.

Applications de DFS

  • Détection des cycles dans le graphique: Si nous trouvons un bord arrière lors de l'exécution de DFS dans un graphique, nous pouvons conclure que le graphique a un cycle. Par conséquent, DFS est utilisé pour détecter les cycles dans un graphique.
  • Trouver son chemin: Étant donné deux sommets x et y, nous pouvons trouver le chemin entre x et y en utilisant DFS. Nous commençons avec le sommet x, puis poussons tous les sommets sur le chemin de la pile jusqu'à ce que nous rencontrions y. Le contenu de la pile donne le chemin entre x et y.
  • Arbre couvrant minimum et chemin le plus court: Le parcours DFS du graphe non pondéré nous donne un arbre couvrant minimum et le chemin le plus court entre les nœuds.
  • Tri topologique: Nous utilisons le tri topologique lorsque nous devons planifier les travaux à partir des dépendances données parmi les travaux. Dans le domaine de l'informatique, nous l'utilisons principalement pour résoudre les dépendances de symboles dans les éditeurs de liens, la sérialisation des données, la planification des instructions, etc. DFS est largement utilisé dans le tri topologique.

Conclusion

Dans les deux derniers didacticiels, nous avons exploré plus en détail les deux techniques de traversée pour les graphiques, à savoir BFS et DFS. Nous avons vu les différences ainsi que les applications des deux techniques. BFS et DFS obtiennent fondamentalement le même résultat en visitant tous les nœuds d'un graphe, mais ils diffèrent dans l'ordre de la sortie et la manière dont cela est fait.

Nous avons également vu la mise en œuvre des deux techniques. Alors que BFS utilise une file d'attente, DFS utilise des piles pour implémenter la technique. Avec cela, nous concluons le tutoriel sur les techniques de traversée pour les graphes. Nous pouvons également utiliser BFS et DFS sur les arbres.

meilleur lecteur de musique et téléchargeur pour android

Nous en apprendrons plus sur les arbres couvrant et quelques algorithmes pour trouver le chemin le plus court entre les nœuds d'un graphe dans notre prochain didacticiel.

=> Voir ici pour explorer la liste complète des didacticiels C ++.

lecture recommandée

^