深度优先遍历代码C++

void DFS(int u) {
vis[u] = true; // 标记节点u已经被访问过
// 对节点u进行操作
for (int v = 0; v < n; v++) { // 枚举节点u的所有邻居
if (!vis[v] && g[u][v]) { // 如果节点v没有被访问过且u和v之间有边相连
DFS(v); // 递归访问节点v
}
}
}

相关问题

领接表的深度优先遍历代码c++

领接表是一种图数据结构的表示方法，通常用于稀疏图，其中每个节点包含一个指向其邻接节点列表的指针。在C++中，使用深度优先搜索(DFS)遍历这种图可以采用递归或栈的方式。以下是使用递归的简单DFS代码示例：

#include <iostream>
#include <vector>

// 结点结构体
struct Node {
    int value;
    std::vector<Node*> neighbors; // 邻接节点列表
};

void dfs(Node* node, bool visited[]) { // 递归函数
    if (node != nullptr && !visited[node->value]) { // 如果节点未访问过
        visited[node->value] = true; // 标记为已访问
        std::cout << node->value << " "; // 访问节点值
        for (Node* neighbor : node->neighbors) { // 遍历邻居
            dfs(neighbor, visited); // 递归遍历邻居节点
        }
    }
}

int main() {
    // 初始化你的图节点及邻接关系
    Node nodes[] = { ... };
    int num_nodes = sizeof(nodes) / sizeof(nodes[0]);

    // 初始化已访问数组
    bool visited[num_nodes] = {false};

    // 开始深度优先遍历
    for (Node* node : nodes) {
        if (!visited[node->value]) {
            dfs(node, visited);
        }
    }

    return 0;
}

在这个例子中，`dfs()` 函数会从给定的起始节点开始，标记已访问过的节点，并递归地探索它们的邻居节点。`visited` 数组用于跟踪节点是否已被访问。

连通图的深度优先遍历和广度优先遍历用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[]` 为你实际的图数据结构。