C++ でグラフ検索アルゴリズムを使用する方法

C でのグラフ検索アルゴリズムの使用方法

グラフ検索アルゴリズムは、パスの検索、ノードのトラバース、またはグラフ構造内のその他の問題の解決に一般的に使用されるアルゴリズムです。グラフに関する問題。 C には、深さ優先検索 (DFS)、幅優先検索 (BFS)、ダイクストラ アルゴリズム、A* アルゴリズムなど、グラフ検索アルゴリズムの実装が多数あります。この記事では、C でグラフ検索アルゴリズムを使用する方法と具体的なコード例を紹介します。

1. 深さ優先検索 (DFS)

深さ優先検索は、古典的なグラフ検索アルゴリズムであり、その基本的な考え方は、ターゲット ノードが見つかるまでグラフのノードを深く走査することです。横断完了、全体像。以下は、C を使用して DFS を実装するためのサンプル コードです:

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

上記のコードでは、最初にグラフのノード データ構造を定義します。各ノードには値 (val) と隣接ノードのリスト (近所の人）。次に、訪問するノードを保存するスタック (stk) を定義します。 DFS 関数では、最初に開始ノードをスタックに配置し、次にノードへの反復アクセスを開始します。各ノードについて、そのノードを訪問済みとしてマークし、それに基づいて処理します (この場合、ノードの値を出力するだけです)。次に、現在のノードの隣接ノードを走査し、未訪問の隣接ノードをスタックに追加します。このようにして、深さ優先の方法でグラフ全体にアクセスできます。

2. 幅優先検索 (BFS)

幅優先検索は、もう 1 つの一般的に使用されるグラフ検索アルゴリズムです。その基本的な考え方は、ターゲット ノードまたはグラフ全体を調べます。以下は、C を使用して BFS を実装するためのサンプル コードです。

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

上記のコードでは、アクセスするノードを保存するためにキュー (q) を使用します。 BFS 関数では、最初に開始ノードをキューに入れてから、ノードへの反復的なアクセスを開始します。各ノードについて、そのノードを訪問済みとしてマークし、それに基づいて処理します (この場合、ノードの値を出力するだけです)。次に、現在のノードの隣接ノードを走査し、未訪問の隣接ノードをキューに追加します。このようにして、幅優先の方法でグラフ全体にアクセスできます。

3. 他のグラフ検索アルゴリズムの実装

深さ優先検索と幅優先検索に加えて、C はダイクストラ アルゴリズムや幅優先検索など、他の多くのグラフ検索アルゴリズムの実装も提供します。 A* アルゴリズム。これらのアルゴリズムの実装は少し複雑なので、この記事では説明できません。ただし、これらのアルゴリズムの実装は C の標準ライブラリで見つけることも、サードパーティのライブラリを使用して実装することもできます。これらのアルゴリズムを使用すると、最短経路や最短距離など、より複雑なグラフの問題を解決できます。

要約すると、この記事では、C でグラフ検索アルゴリズムを使用する方法を紹介し、深さ優先検索と幅優先検索の具体的なコード例を示します。この記事がグラフ検索アルゴリズムの理解と応用に役立つことを願っています。

以上がC++ でグラフ検索アルゴリズムを使用する方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。