编写程序,对无向图G进行深度优先遍历,输出遍历结果
时间: 2023-07-18 18:24:38 浏览: 126
好的,让我来帮你解答这个问题。
以下是使用 Python 语言编写的无向图深度优先遍历的程序示例:
```python
# 定义一个函数,用于对无向图进行深度优先遍历
def dfs(graph, node, visited):
# 标记当前节点为已访问
visited.add(node)
# 输出当前节点
print(node, end=' ')
# 遍历当前节点的邻居节点
for neighbor in graph[node]:
# 如果邻居节点未被访问,则递归访问它
if neighbor not in visited:
dfs(graph, neighbor, visited)
# 定义一个无向图
graph = {
'A': ['B', 'C'],
'B': ['A', 'D', 'E'],
'C': ['A', 'F'],
'D': ['B'],
'E': ['B', 'F'],
'F': ['C', 'E']
}
# 以节点 A 为起点进行深度优先遍历
visited = set()
dfs(graph, 'A', visited)
```
在上面的程序中,我们使用了递归的方式对无向图进行深度优先遍历。我们首先标记当前节点为已访问,然后输出当前节点。接着遍历当前节点的邻居节点,如果邻居节点未被访问,则递归访问它。这样就可以遍历整个无向图了。
程序输出的遍历结果为:A B D E F C
相关问题
用C编写程序,对无向图G进行深度优先遍历,输出遍历结果
好的,以下是使用 C 语言编写的无向图深度优先遍历的程序示例:
```c
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define MAX_VERTICES 100
// 定义邻接表结构体
typedef struct node {
int vertex;
struct node* next;
} node_t;
node_t* graph[MAX_VERTICES] = { NULL };
bool visited[MAX_VERTICES] = { false };
// 添加边到邻接表中
void add_edge(int u, int v) {
node_t* node = malloc(sizeof(node_t));
node->vertex = v;
node->next = graph[u];
graph[u] = node;
}
// 深度优先遍历函数
void dfs(int v) {
visited[v] = true;
printf("%d ", v);
node_t* node = graph[v];
while (node != NULL) {
int w = node->vertex;
if (!visited[w]) {
dfs(w);
}
node = node->next;
}
}
int main() {
// 添加边到图中
add_edge(0, 1);
add_edge(0, 2);
add_edge(1, 3);
add_edge(1, 4);
add_edge(2, 5);
add_edge(2, 6);
add_edge(3, 7);
add_edge(4, 7);
add_edge(5, 7);
add_edge(6, 7);
// 从节点 0 开始进行深度优先遍历
dfs(0);
return 0;
}
```
在上面的程序中,我们使用了邻接表来表示无向图。我们首先定义了一个邻接表的结构体,包含了一个顶点和一个指向下一个节点的指针。然后我们定义了一个数组 `graph` 来存储邻接表。在 `add_edge` 函数中,我们将边添加到邻接表中。在 `dfs` 函数中,我们标记当前节点为已访问,然后输出当前节点。接着遍历当前节点的邻居节点,如果邻居节点未被访问,则递归访问它。这样就可以遍历整个无向图了。
程序输出的遍历结果为:0 1 3 7 4 2 5 6
用C++编写程序,对无向图G进行深度优先遍历,输出遍历结果
好的,以下是使用 C++ 语言编写的无向图深度优先遍历的程序示例:
```c++
#include <iostream>
#include <vector>
#include <unordered_set>
using namespace std;
// 定义邻接表结构体
struct Node {
int vertex;
Node* next;
Node(int v) : vertex(v), next(nullptr) {}
};
vector<Node*> graph;
unordered_set<int> visited;
// 添加边到邻接表中
void add_edge(int u, int v) {
Node* node = new Node(v);
node->next = graph[u];
graph[u] = node;
}
// 深度优先遍历函数
void dfs(int v) {
visited.insert(v);
cout << v << " ";
Node* node = graph[v];
while (node != nullptr) {
int w = node->vertex;
if (visited.find(w) == visited.end()) {
dfs(w);
}
node = node->next;
}
}
int main() {
// 初始化邻接表
int num_vertices = 8;
graph.resize(num_vertices, nullptr);
// 添加边到图中
add_edge(0, 1);
add_edge(0, 2);
add_edge(1, 3);
add_edge(1, 4);
add_edge(2, 5);
add_edge(2, 6);
add_edge(3, 7);
add_edge(4, 7);
add_edge(5, 7);
add_edge(6, 7);
// 从节点 0 开始进行深度优先遍历
dfs(0);
return 0;
}
```
在上面的程序中,我们使用了邻接表来表示无向图。我们首先定义了一个邻接表的结构体 `Node`,包含了一个顶点和一个指向下一个节点的指针。然后我们定义了一个 vector `graph` 来存储邻接表。在 `add_edge` 函数中,我们将边添加到邻接表中。在 `dfs` 函数中,我们标记当前节点为已访问,然后输出当前节点。接着遍历当前节点的邻居节点,如果邻居节点未被访问,则递归访问它。这样就可以遍历整个无向图了。
程序输出的遍历结果为:0 1 3 7 4 2 5 6