无向图的深度优先遍历

深度优先遍历（Depth First Search, DFS）是一种图遍历算法，它可以用来遍历无向图。下面是无向图的深度优先遍历的基本步骤：

1. 从图中任意一个顶点开始遍历，将该顶点标记为已访问；

2. 从该顶点开始，遍历它的所有邻接点，如果邻接点未被访问，则递归访问该邻接点，并标记为已访问；

3. 重复步骤2，直到该顶点的所有邻接点都被访问过。

4. 如果还存在未被访问的顶点，则从中选择一个顶点开始重复以上步骤，直到所有顶点都被访问过。

下面是一个使用递归实现的无向图深度优先遍历的示例代码：

visited = set()  # 用集合表示已经访问过的顶点

# 递归实现深度优先遍历
def dfs(graph, v):
    visited.add(v)  # 标记为已访问
    print(v, end=' ')  # 输出遍历到的顶点
    for w in graph[v]:
        if w not in visited:
            dfs(graph, w)

# 示例图的邻接表表示
graph = {0: [1, 2], 1: [0, 2, 3], 2: [0, 1, 3], 3: [1, 2]}

# 从顶点0开始遍历
dfs(graph, 0)

上述代码输出结果为：0 1 2 3。注意，这里的示例图是无向图，因此在构造邻接表时需要保证每一条边都被记录两次。

相关问题

无向图深度优先遍历序列

无向图深度优先遍历序列可以通过深度优先搜索（DFS）算法获得。DFS算法可以通过递归或栈实现。下面是一种递归实现的DFS算法，其中visited数组用于记录每个节点是否被访问过，dfs函数用于递归地访问每个节点并将其加入遍历序列中：

vector<int> dfs(vector<vector<int>>& graph, vector<bool>& visited, int node) {
    visited[node] = true;
    vector<int> traversal{node};
    for (int neighbor : graph[node]) {
        if (!visited[neighbor]) {
            vector<int> neighbor_traversal = dfs(graph, visited, neighbor);
            traversal.insert(traversal.end(), neighbor_traversal.begin(), neighbor_traversal.end());
        }
    }
    return traversal;
}

vector<int> dfsTraversal(vector<vector<int>>& graph) {
    int n = graph.size();
    vector<bool> visited(n, false);
    vector<int> traversal;
    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            vector<int> i_traversal = dfs(graph, visited, i);
            traversal.insert(traversal.end(), i_traversal.begin(), i_traversal.end());
        }
    }
    return traversal;
}

其中，graph是无向图的邻接表表示，visited是一个bool类型的数组，表示各个节点是否被访问过。dfsTraversal函数返回的是遍历序列。

无向图的深度优先遍历广度优先遍历c语言

在C语言中，无向图的深度优先遍历（Depth-First Search, BFS）都是用于搜索图的数据结构算法。

**深度优先遍历（DFS）**:
1. **递归实现**：从起始顶点开始，选择一条未访问的边并深入探索。如果当前节点的所有邻接节点都已访问，则回溯到上一个节点继续处理。

   void dfs(int node, int graph[], int visited[]) {
       visited[node] = 1;
       for (int i = 0; i < num_nodes; i++) {
           if (graph[node][i] == 1 && visited[i] == 0)
               dfs(i, graph, visited);
       }
   }

2. **栈实现**：可以使用栈数据结构模拟递归过程，将待访问的节点压入栈中。

**广度优先遍历（BFS）**:
1. **队列实现**：从起始顶点开始，首先将其加入队列，然后每次从队列头部取出一个节点，访问其所有邻接节点并将它们加入队列，直到队列为空。

   void bfs(int start) {
       queue<int> q;
       visited[start] = 1;
       q.push(start);
       while (!q.empty()) {
           int curr = q.front();
           q.pop();
           // Process the current node
           for (int neighbor = 0; neighbor < num_nodes; neighbor++) {
               if (graph[curr][neighbor] == 1 && visited[neighbor] == 0) {
                   visited[neighbor] = 1;
                   q.push(neighbor);
               }
           }
       }
   }