Cara menggunakan algoritma carian mendalam-pertama dalam C++

Cara menggunakan algoritma carian pertama mendalam dalam C++

Algoritma carian pertama mendalam (DFS) ialah algoritma untuk merentasi atau mencari graf atau pokok, bermula dari nod akar dan meneroka graf sedalam Cawangan mungkin sehingga anda tidak boleh meneruskan, kemudian kembali dan meneroka cawangan lain. DFS ialah penyelesaian yang sangat berguna untuk banyak masalah, seperti pengesanan sambungan graf, mencari kitaran graf, menjana dan mencetak semua laluan yang mungkin, dsb.

Artikel ini akan memperkenalkan cara melaksanakan algoritma carian pertama mendalam dalam C++ dan menggunakan contoh kod khusus untuk menggambarkan.

Idea asas carian mendalam-pertama ialah menggunakan rekursi atau tindanan untuk menyelamatkan nod yang perlu dilalui. Berikut ialah contoh kod algoritma DFS untuk graf yang diwakili oleh matriks bersebelahan:

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

Dalam kod contoh di atas, kami mula-mula mentakrifkan matriks bersebelahan dua dimensi global graph，以及visited数组用于标记节点是否被访问过。然后我们定义了一个dfs()函数用于实现深度优先搜索。该函数使用一个栈来保存需要遍历的节点，首先将起始节点入栈，并标记为已访问。然后开始进入循环，每次从栈中取出一个节点，遍历该节点的邻接节点，如果邻接节点未被访问过，则将其入栈并标记为已访问。这个过程将一直进行直到栈为空。最后，我们使用main()函数来读取图的信息，并调用dfs() fungsi untuk carian mendalam-dahulu.

Contoh kod di atas hanyalah aplikasi mudah algoritma carian mendalam-pertama. Malah, algoritma juga boleh dioptimumkan melalui beberapa teknik, seperti menggunakan pelaksanaan rekursif, menggunakan penandaan warna, dsb.

Algoritma carian mendalam-pertama sangat berkesan dalam menyelesaikan pelbagai masalah teori graf dan digunakan secara meluas dalam aplikasi praktikal. Kemahiran dalam pelaksanaan algoritma DFS sangat membantu untuk memahami teori graf dan menyelesaikan masalah berkaitan.

Ringkasan:

Artikel ini memperkenalkan cara melaksanakan algoritma carian pertama mendalam dalam C++ dan memberikan contoh kod khusus. Algoritma carian pertama mendalam ialah algoritma teori graf penting yang boleh menyelesaikan banyak masalah berkaitan graf dengan merentasi atau mencari cabang graf. Menguasai algoritma DFS sangat membantu untuk memahami teori graf dan menyelesaikan masalah yang berkaitan.

Atas ialah kandungan terperinci Cara menggunakan algoritma carian mendalam-pertama dalam C++. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!