用C++编写程序对给定的有向图(不一定连通)进行深度优先遍历,图中包含n个顶点,编号为0至n-1。本题限定在深度优先遍历过程中,如果同时出现多个待访问的顶点,则优先选择编号最小的一个进行访问,以顶点0为遍历起点。
时间: 2024-05-15 17:17:33 浏览: 188
好的,我可以为您解答这个问题。以下是C语言代码示例:
```c
#include <stdio.h>
#define MAX_N 100
int n; // 顶点个数
int graph[MAX_N][MAX_N]; // 邻接矩阵
int visited[MAX_N]; // 标记数组,记录每个顶点是否已被访问
void dfs(int v) {
visited[v] = 1; // 标记当前顶点已被访问
printf("%d ", v); // 输出当前顶点编号
int i;
for (i = 0; i < n; i++) {
if (graph[v][i] && !visited[i]) { // 如果存在从v到i的边且i未被访问
dfs(i); // 递归访问i
}
}
}
int main() {
int m;
scanf("%d %d", &n, &m); // 输入顶点个数和边数
int i, j;
for (i = 0; i < m; i++) {
int u, v;
scanf("%d %d", &u, &v); // 输入一条边的起点和终点
graph[u][v] = 1; // 在邻接矩阵中标记该边
}
dfs(0); // 从顶点0开始深度优先遍历
printf("\n");
return 0;
}
```
这段代码使用邻接矩阵来存储有向图,使用递归函数dfs进行深度优先遍历。在dfs函数中,我们首先将当前顶点标记为已访问,然后输出其编号,并依次递归访问其所有未访问的邻居顶点。在递归访问邻居顶点时,我们会优先选择编号最小的邻居顶点。
阅读全文