Cara menggunakan algoritma carian graf dalam C++

Cara menggunakan algoritma carian graf dalam C++

Algoritma carian graf ialah algoritma yang biasa digunakan untuk mencari laluan dalam struktur graf, merentasi nod atau menyelesaikan masalah berkaitan graf lain. Dalam C++, terdapat banyak pelaksanaan algoritma carian graf, seperti carian depth-first (DFS), breadth-first search (BFS), algoritma Dijkstra, algoritma A*, dsb. Dalam artikel ini, kami akan memperkenalkan cara menggunakan algoritma carian graf dalam C++ dan memberikan contoh kod khusus.

1. Depth First Search (DFS)

Depth First Search ialah algoritma carian graf klasik ialah merentasi nod graf secara mendalam sehingga nod sasaran ditemui atau keseluruhan graf dilalui. Berikut ialah contoh kod untuk melaksanakan DFS menggunakan C++:

#include <iostream>
#include <vector>
#include <stack>

using namespace std;

// 定义图的节点数据结构
struct Node {
    int val;
    vector<Node*> neighbors;
    bool visited;
    
    Node(int x) : val(x), visited(false) {} // 初始化节点
};

// 深度优先搜索函数
void dfs(Node* node) {
    stack<Node*> stk;
    stk.push(node);
    
    while (!stk.empty()) {
        Node* cur = stk.top();
        stk.pop();
        
        if (cur->visited) {
            continue;
        }
        
        cur->visited = true;
        
        // 对当前节点进行操作
        cout << cur->val << " ";
        
        // 遍历当前节点的邻居节点
        for (Node* neighbor : cur->neighbors) {
            if (!neighbor->visited) {
                stk.push(neighbor);
            }
        }
    }
}

int main() {
    // 构造图
    Node* node1 = new Node(1);
    Node* node2 = new Node(2);
    Node* node3 = new Node(3);
    Node* node4 = new Node(4);
    node1->neighbors.push_back(node2);
    node1->neighbors.push_back(node4);
    node2->neighbors.push_back(node1);
    node2->neighbors.push_back(node3);
    node3->neighbors.push_back(node2);
    node3->neighbors.push_back(node4);
    node4->neighbors.push_back(node1);
    node4->neighbors.push_back(node3);
    
    // 调用深度优先搜索函数
    dfs(node1);

    return 0;
}

Dalam kod di atas, kami mula-mula mentakrifkan struktur data nod graf, setiap nod mengandungi nilai (val) dan senarai nod jiran (jiran). Kemudian, kami mentakrifkan tindanan (stk) untuk menyimpan nod yang akan dilawati. Dalam fungsi DFS, kami mula-mula meletakkan nod permulaan ke dalam timbunan dan kemudian mula mengakses nod secara berulang. Untuk setiap nod, kami menandakannya sebagai dilawati dan bertindak ke atasnya (dalam kes ini, hanya keluarkan nilai nod). Seterusnya, kami melintasi nod jiran nod semasa dan menambah nod jiran yang tidak dilawati pada timbunan. Dengan cara ini, kita boleh mengakses keseluruhan graf dengan cara yang lebih mendalam.

2. Breadth First Search (BFS)

Breadth First Search ialah satu lagi algoritma carian graf yang biasa digunakan ialah merentasi nod lapisan graf demi lapisan sehingga nod sasaran ditemui atau keseluruhan graf dilalui. Berikut ialah contoh kod untuk melaksanakan BFS menggunakan C++:

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

// 定义图的节点数据结构
struct Node {
    int val;
    vector<Node*> neighbors;
    bool visited;
    
    Node(int x) : val(x), visited(false) {} // 初始化节点
};

// 广度优先搜索函数
void bfs(Node* node) {
    queue<Node*> q;
    q.push(node);
    
    while (!q.empty()) {
        Node* cur = q.front();
        q.pop();
        
        if (cur->visited) {
            continue;
        }
        
        cur->visited = true;
        
        // 对当前节点进行操作
        cout << cur->val << " ";
        
        // 遍历当前节点的邻居节点
        for (Node* neighbor : cur->neighbors) {
            if (!neighbor->visited) {
                q.push(neighbor);
            }
        }
    }
}

int main() {
    // 构造图
    Node* node1 = new Node(1);
    Node* node2 = new Node(2);
    Node* node3 = new Node(3);
    Node* node4 = new Node(4);
    node1->neighbors.push_back(node2);
    node1->neighbors.push_back(node4);
    node2->neighbors.push_back(node1);
    node2->neighbors.push_back(node3);
    node3->neighbors.push_back(node2);
    node3->neighbors.push_back(node4);
    node4->neighbors.push_back(node1);
    node4->neighbors.push_back(node3);
    
    // 调用广度优先搜索函数
    bfs(node1);

    return 0;
}

Dalam kod di atas, kami menggunakan baris gilir (q) untuk menyimpan nod yang akan dilawati. Dalam fungsi BFS, kami mula-mula meletakkan nod permulaan ke dalam baris gilir dan kemudian mula mengakses nod secara berulang. Untuk setiap nod, kami menandakannya sebagai dilawati dan bertindak ke atasnya (dalam kes ini, hanya keluarkan nilai nod). Seterusnya, kami melintasi nod jiran nod semasa dan menambah nod jiran yang tidak dilawati pada baris gilir. Dengan cara ini, kita boleh mengakses keseluruhan graf dengan cara yang luas.

3. Pelaksanaan algoritma carian graf lain

Selain carian mendalam-dahulu dan carian luas-dahulu, C++ juga menyediakan pelaksanaan banyak algoritma carian graf lain, seperti algoritma Dijkstra dan algoritma A*. Pelaksanaan algoritma ini lebih kompleks sedikit dan tidak boleh ditunjukkan dalam artikel ini. Walau bagaimanapun, anda boleh mencari pelaksanaan algoritma ini dalam perpustakaan standard C++ atau menggunakan perpustakaan pihak ketiga untuk melaksanakannya. Menggunakan algoritma ini, anda boleh menyelesaikan masalah graf yang lebih kompleks, seperti laluan terpendek, jarak terpendek, dsb.

Ringkasnya, artikel ini memperkenalkan cara menggunakan algoritma carian graf dalam C++ dan memberikan contoh kod khusus bagi carian mendalam-dahulu dan carian luas-dahulu. Saya harap artikel ini dapat membantu anda memahami dan menggunakan algoritma carian graf.

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