连通图的深度优先遍历和广度优先遍历用c++代码实现

当然，我可以帮助你理解深度优先搜索 (DFS) 和广度优先搜索 (BFS) 的基本原理，并提供 C++ 代码示例。

**深度优先遍历（Depth First Search, DFS）：**
DFS 是一种用于遍历或搜索树形结构的算法。它会尽可能深地探索每个分支，直到到达最底层，然后回溯到上一层继续搜索。

#include <iostream>
#include <vector>
using namespace std;

// 图节点的表示
struct Node {
    int value;
    vector<Node*> neighbors;
};

void dfs(Node* node, bool visited[]) {
    if (!visited[node->value]) {
        visited[node->value] = true;
        cout << node->value << " ";
        
        // 访问邻居节点
        for (Node* neighbor : node->neighbors)
            dfs(neighbor, visited);
    }
}

int main() {
    Node graph[] = {...}; // 初始化你的图数据
    int num_nodes = sizeof(graph) / sizeof(graph[0]);
    
    bool visited[num_nodes] = {false};
    dfs(graph, visited);
    
    return 0;
}

**广度优先遍历（Breadth First Search, BFS）：**
BFS 是从根节点开始，按照层次顺序逐层遍历节点的算法。它是先访问当前层的所有节点，然后再移向下一层。

#include <queue>
#include <iostream>
using namespace std;

void bfs(Node* root) {
    queue<Node*> q;
    q.push(root);
    visited[root->value] = true;
    
    while (!q.empty()) {
        Node* current = q.front();
        q.pop();

        cout << current->value << " ";
        
        // 将未访问的邻居加入队列
        for (Node* neighbor : current->neighbors)
            if (!visited[neighbor->value])
                q.push(neighbor), visited[neighbor->value] = true;
    }
}

int main() {
    Node graph[] = {...}; // 初始化你的图数据
    int num_nodes = sizeof(graph) / sizeof(graph[0]);

    bool visited[num_nodes] = {false};
    bfs(graph);
    
    return 0;
}

在这两个例子中，`visited` 数组用于标记节点是否已访问过。记得替换 `graph[]` 为你实际的图数据结构。