通过邻接矩阵表示法存储有向图,编写递归函数采用DFS从有向图G中的顶点vi出发,判断图G中是否存在回路,如果存在回路则打印该回路中的各顶点元素值。
时间: 2024-02-11 08:07:56 浏览: 10
好的,这是一个常见的图论问题。可以使用深度优先搜索(DFS)来解决。
具体思路如下:
1. 从顶点 vi 出发,遍历其所有邻接顶点。
2. 如果邻接顶点未被访问过,则继续递归遍历。
3. 如果邻接顶点已被访问过,且不是当前顶点的父节点,则说明存在回路。输出回路中的各顶点元素值。
4. 如果当前顶点的所有邻接顶点都被访问过,则回溯到上一个顶点继续遍历。
下面是代码实现:(假设邻接矩阵为 G,顶点个数为 n)
```
void DFS(int i, int visited[], int n, int G[][n], int parent) {
visited[i] = 1;
for(int j = 0; j < n; j++) {
if(G[i][j]) {
if(visited[j] == 0) {
DFS(j, visited, n, G, i);
}
else if(j != parent) {
// 判断是否存在回路
// 若存在,则输出回路中的各顶点元素值
printf("%d ", j);
int k = i;
while(k != j) {
printf("%d ", k);
k = parent[k];
}
printf("%d\n", j);
}
}
}
}
```
其中,visited 数组用于记录每个顶点是否被访问过,parent 数组用于记录当前顶点的父节点。从顶点 vi 出发,调用 DFS 函数即可判断是否存在回路。