通过邻接矩阵表示法存储有向图,编写递归函数采用DFS从有向图G中的顶点vi出发,判断图G中是否存在回路,如果存在回路则打印该回路中的各顶点元素值。请填写如下函数框架中缺少的4条语句部分。
时间: 2024-02-11 16:07:55 浏览: 15
```
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 = // 语句1:填写缺失的部分,找到回路中的下一个顶点
}
printf("%d\n", j);
}
}
}
}
```
语句1:填写缺失的部分,找到回路中的下一个顶点。
可以通过 parent 数组来记录当前顶点的父节点,从而找到回路中的下一个顶点。具体地,假设当前顶点为 i,上一个顶点为 parent,下一个顶点为 j,那么下一个顶点 j 可以通过以下方式找到:
```
int k = i;
while(k != j) {
printf("%d ", k);
k = parent[k];
}
printf("%d ", j);
```