c语言假设以邻接矩阵作为图的存储结构,编写算法判别在给定的有向图中是否存在一个简单有向回路,若存在,则以顶点序列的方式输出该回路(找到一条即可)。(注:图中不存在顶点到自己的弧)
时间: 2024-04-16 07:26:17 浏览: 133
您可以使用深度优先搜索(DFS)算法来判断给定的有向图中是否存在一个简单有向回路,并以顶点序列的方式输出该回路。
以下是使用邻接矩阵表示图的C语言代码示例:
```c
#include <stdio.h>
#include <stdbool.h>
#define MAX_SIZE 100
bool visited[MAX_SIZE]; // 标记顶点是否已访问
int path[MAX_SIZE]; // 保存路径
int pathLength; // 路径长度
// 深度优先搜索函数
dfs(int graph[MAX_SIZE][MAX_SIZE], int v, int start) {
visited[v] = true;
path[pathLength++] = v;
for (int i = 0; i < start; i++) {
if (graph[v][i]) {
if (!visited[i]) {
if (dfs(graph, i, start)) {
return true;
}
} else {
// 存在回路,输出回路路径
int j;
for (j = 0; j < pathLength; j++) {
if (path[j] == i) {
break;
}
}
printf("回路路径:");
for (; j < pathLength; j++) {
printf("%d ", path[j]);
}
printf("%d\n", i);
return true;
}
}
}
pathLength--;
visited[v] = false;
return false;
}
// 判断是否存在简单有向回路
bool hasCycle(int graph[MAX_SIZE][MAX_SIZE], int n) {
pathLength = 0;
for (int i = 0; i < n; i++) {
if (!visited[i]) {
if (dfs(graph, i, n)) {
return true;
}
}
}
return false;
}
int main() {
int graph[MAX_SIZE][MAX_SIZE];
int n; // 顶点数
printf("请输入顶点数:");
scanf("%d", &n);
printf("请输入邻接矩阵(以0和1表示存在和不存在的边):\n");
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
scanf("%d", &graph[i][j]);
}
}
if (!hasCycle(graph, n)) {
printf("不存在简单有向回路。\n");
}
return 0;
}
```
您可以根据需要修改输入输出的方式,运行程序后输入顶点数和邻接矩阵,即可判断给定有向图中是否存在简单有向回路,并输出回路的顶点序列。
阅读全文