使用C++编写一个图的深度和广度优先遍历的代码

以你之姓@ 2024-03-26 21:58 6阅读 0赞

下面是图的深度优先遍历的代码

//qq460219753获取更多代码
    #include <iostream>
    #include <vector>
    #include <stack>
    
    using namespace std;
    
    // 定义一个图节点结构体
    struct GraphNode {
        
        int val;
        vector<GraphNode*> neighbors;
        GraphNode(int x) : val(x) {
        };
    };
    
    // 深度优先遍历函数
    void DFS(GraphNode* node, vector<bool>& visited) {
        
        // 如果节点已经被访问过，则直接返回
        if (visited[node->val]) {
        
            return;
        }
        
        // 输出当前节点的值，并将其标记为已访问
        cout << node->val << " ";
        visited[node->val] = true;
        
        // 遍历当前节点的所有邻居节点
        for (int i = 0; i < node->neighbors.size(); i++) {
        
            // 对于每个未访问过的邻居节点，递归调用DFS函数
            if (!visited[node->neighbors[i]->val]) {
        
                DFS(node->neighbors[i], visited);
            }
        }
    }
    
    int main() {
        
        // 构建一个有向图
        GraphNode* node0 = new GraphNode(0);
        GraphNode* node1 = new GraphNode(1);
        GraphNode* node2 = new GraphNode(2);
        GraphNode* node3 = new GraphNode(3);
        GraphNode* node4 = new GraphNode(4);
        node0->neighbors.push_back(node1);
        node0->neighbors.push_back(node2);
        node1->neighbors.push_back(node2);
        node2->neighbors.push_back(node0);
        node2->neighbors.push_back(node3);
        node3->neighbors.push_back(node3);
        node4->neighbors.push_back(node2);
        node4->neighbors.push_back(node3);
        
        // 初始化visited数组，所有节点均未被访问过
        vector<bool> visited(5, false);
        
        // 从节点0开始进行深度优先遍历
        DFS(node0, visited);
        
        return 0;
       
    }

注释：

定义一个图节点结构体，包含节点的值和邻居节点数组。  
定义深度优先遍历函数，输入参数为当前节点和一个表示每个节点是否被访问过的visited数组。  
如果当前节点已经被访问过，则直接返回。  
输出当前节点的值，并将其标记为已访问。  
遍历当前节点的所有邻居节点。  
对于每个未访问过的邻居节点，递归调用DFS函数。  
在main函数中，构建一个有向图，并初始化visited数组。  
从节点0开始进行深度优先遍历。  
返回0，表示程序正常结束。

下面是图的广度优先遍历的代码

#include <iostream>
    #include <vector>
    #include <queue>
    #include <unordered_set>
    
    using namespace std;
    
    // 定义图节点结构体
    struct GraphNode {
        
        int val;  // 节点的值
        vector<GraphNode*> neighbors;  // 节点的邻居
        GraphNode(int x) : val(x) {
        }
    };
    
    // 广度优先遍历函数
    void bfs(GraphNode* node) {
        
        // 定义一个队列来存储遍历到的节点
        queue<GraphNode*> q;
        // 定义一个哈希表来存储已经遍历过的节点
        unordered_set<GraphNode*> visited;
        // 将起始节点加入队列
        q.push(node);
        // 将起始节点标记为已访问
        visited.insert(node);
        // 当队列不为空时，继续遍历
        while (!q.empty()) {
        
            // 取出队列中的节点
            GraphNode* curr = q.front();
            q.pop();
            // 对当前节点进行操作，这里只是打印节点的值
            cout << curr->val << " ";
            // 遍历当前节点的所有邻居
            for (auto neighbor : curr->neighbors) {
        
                // 如果邻居节点未被访问过，将其加入队列和已访问哈希表
                if (visited.find(neighbor) == visited.end()) {
        
                    q.push(neighbor);
                    visited.insert(neighbor);
                }
            }
        }
    }
    
    // 主函数
    int main() {
        
        // 构建一个图
        GraphNode* node0 = new GraphNode(0);
        GraphNode* node1 = new GraphNode(1);
        GraphNode* node2 = new GraphNode(2);
        GraphNode* node3 = new GraphNode(3);
        node0->neighbors = {
        node1, node2};
        node1->neighbors = {
        node2, node3};
        node2->neighbors = {
        node0, node3};
        node3->neighbors = {
        node3};
        // 对图进行广度优先遍历
        bfs(node0);
        return 0;
    }

代码解释：

定义了一个 GraphNode 结构体，用来表示图的节点。其中包含一个整型变量 val 表示节点的值，以及一个 vector 类型的变量 neighbors 表示节点的邻居。

定义了 bfs 函数，用来进行广度优先遍历。函数的参数是起始节点 node。在函数中，首先定义了一个队列 q 来存储遍历到的节点，以及一个哈希表 visited 来存储已经遍历过的节点。将起始节点加入队列，并将其标记为已访问。当队列不为空时，取出队列中的节点，对其进行操作（这里只是打印节点的值），然后遍历当前节点的所有邻居。如果邻居节点未被访问过，将其加入队列和已访问哈希表，直到队列为空。

在主函数中，构建了一个图，并对其进行广度优先遍历。具体地，构建了四个节点，分别为 node0、node1、node2 和 node3，然后将它们的邻居连接起来，形成了一个简单的无向图。最后，将起始节点 node0 传入 bfs 函数中进行遍历。

在函数中，使用了 queue 来存储遍历到的节点。queue 是标准库中的一个容器，用来实现队列数据结构。其成员函数包括 push（向队列尾部添加元素）、front（获取队列头部元素）和 pop（删除队列头部元素）等。

同时，使用了 unordered\_set 来存储已经遍历过的节点。unordered\_set 是标准库中的一个容器，用来实现哈希表数据结构。其成员函数包括 insert（向哈希表中添加元素）、find（查找指定元素是否在哈希表中）等。

在函数中，使用了 auto 关键字来自动推断变量类型。这个关键字在 C++11 中引入，可以根据变量的初始化表达式自动推断其类型，从而简化代码。