Comment utiliser l'algorithme de recherche en profondeur d'abord en C++

Comment utiliser l'algorithme de recherche en profondeur d'abord en C++

L'algorithme de recherche en profondeur d'abord (DFS) est un algorithme permettant de parcourir ou de rechercher un graphe ou un arbre, en partant d'un nœud racine et en explorant le graphe aussi profondément que Branche possible jusqu'à ce que vous ne puissiez plus continuer, puis revenez en arrière et explorez d'autres branches. DFS est une solution très utile à de nombreux problèmes, tels que la détection de connectivité graphique, la recherche de cycles graphiques, la génération et l'impression de tous les chemins possibles, etc.

Cet article présentera comment implémenter l'algorithme de recherche en profondeur d'abord en C++ et utilisera des exemples de code spécifiques pour illustrer.

L'idée de base de la recherche en profondeur est d'utiliser la récursivité ou la pile pour enregistrer les nœuds qui doivent être parcourus. Voici un exemple de code de l'algorithme DFS pour un graphique représenté par une matrice de contiguïté :

#include <iostream>
#include <stack>

using namespace std;

const int MAX = 100;
bool visited[MAX];
int graph[MAX][MAX];
int numVertices;

void dfs(int start) {
    stack<int> s;
    visited[start] = true;
    cout << start << " ";

    s.push(start);

    while (!s.empty()) {
        int current = s.top();
        s.pop();

        for (int i = 0; i < numVertices; i++) {
            if (graph[current][i] == 1 && !visited[i]) {
                visited[i] = true;
                cout << i << " ";
                s.push(i);
            }
        }
    }
}

int main() {
    int numEdges, start;

    cout << "Enter the number of vertices: ";
    cin >> numVertices;
    cout << "Enter the number of edges: ";
    cin >> numEdges;

    for (int i = 0; i < numEdges; i++) {
        int u, v;
        cout << "Enter edge (u, v): ";
        cin >> u >> v;
        graph[u][v] = 1;
        graph[v][u] = 1; // Assuming undirected graph
    }

    cout << "Enter the starting vertex for DFS: ";
    cin >> start;

    dfs(start);

    return 0;
}

Dans l'exemple de code ci-dessus, nous définissons d'abord une matrice de contiguïté bidimensionnelle globale graph，以及visited数组用于标记节点是否被访问过。然后我们定义了一个dfs()函数用于实现深度优先搜索。该函数使用一个栈来保存需要遍历的节点，首先将起始节点入栈，并标记为已访问。然后开始进入循环，每次从栈中取出一个节点，遍历该节点的邻接节点，如果邻接节点未被访问过，则将其入栈并标记为已访问。这个过程将一直进行直到栈为空。最后，我们使用main()函数来读取图的信息，并调用dfs() fonction pour la recherche en profondeur d'abord.

L'exemple de code ci-dessus n'est qu'une simple application de l'algorithme de recherche en profondeur d'abord. En fait, l'algorithme peut également être optimisé grâce à certaines techniques, telles que l'utilisation d'une implémentation récursive, l'utilisation du marquage de couleur, etc.

L'algorithme de recherche en profondeur est très efficace pour résoudre divers problèmes de théorie des graphes et est largement utilisé dans des applications pratiques. La maîtrise de la mise en œuvre de l'algorithme DFS est très utile pour comprendre la théorie des graphes et résoudre les problèmes associés.

Résumé :

Cet article présente comment implémenter l'algorithme de recherche en profondeur d'abord en C++ et donne des exemples de code spécifiques. L'algorithme de recherche en profondeur d'abord est un algorithme important de la théorie des graphes qui peut résoudre de nombreux problèmes liés aux graphes en parcourant ou en recherchant des branches du graphe. La maîtrise de l'algorithme DFS est très utile pour comprendre la théorie des graphes et résoudre les problèmes associés.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!