How to use graph search algorithms in C++

How to use the graph search algorithm in C

The graph search algorithm is a commonly used algorithm for finding paths, traversing nodes, or solving other problems in graph structures. Problems related to graphs. In C, there are many implementations of graph search algorithms, such as depth-first search (DFS), breadth-first search (BFS), Dijkstra's algorithm, A* algorithm, etc. In this article, we will introduce how to use graph search algorithms in C and give specific code examples.

1. Depth First Search (DFS)

Depth first search is a classic graph search algorithm. Its basic idea is to deeply traverse the nodes of the graph until the target node is found or the traversal is completed. The whole picture. The following is a sample code for implementing DFS using 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;
}

In the above code, we first define the node data structure of the graph. Each node contains a value (val) and a list of neighbor nodes (neighbors). . Then, we define a stack (stk) to save the nodes to be visited. In the DFS function, we first put the starting node into the stack and then start accessing the nodes iteratively. For each node, we mark it as visited and act on it (in this case, just output the node's value). Next, we traverse the neighbor nodes of the current node and add unvisited neighbor nodes to the stack. This way, we can access the entire graph in a depth-first manner.

2. Breadth First Search (BFS)

Breadth First Search is another commonly used graph search algorithm. Its basic idea is to traverse the nodes of the graph layer by layer until the target node or Traverse the entire graph. The following is a sample code for implementing BFS using 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;
}

In the above code, we use queue (q) to save the nodes to be accessed. In the BFS function, we first put the starting node into the queue and then start accessing the nodes iteratively. For each node, we mark it as visited and act on it (in this case, just output the node's value). Next, we traverse the neighbor nodes of the current node and add unvisited neighbor nodes to the queue. This way, we can access the entire graph in a breadth-first manner.

3. Implementation of other graph search algorithms

In addition to depth-first search and breadth-first search, C also provides implementations of many other graph search algorithms, such as the Dijkstra algorithm and the A* algorithm. The implementation of these algorithms is slightly more complex and cannot be shown in this article. However, you can find implementations of these algorithms in C's standard library or use third-party libraries to implement them. Using these algorithms, you can solve more complex graph problems, such as shortest path, shortest distance, etc.

To sum up, this article introduces how to use the graph search algorithm in C, and gives specific code examples of depth-first search and breadth-first search. I hope this article can help you understand and apply graph search algorithms.

The above is the detailed content of How to use graph search algorithms in C++. For more information, please follow other related articles on the PHP Chinese website!