用c语言判断一个图是不是欧拉图,如果是,求出所有欧拉回路
时间: 2024-05-16 22:12:50 浏览: 18
判断欧拉图可以使用以下定理:
一个无向图是欧拉图当且仅当每个节点的度数都是偶数。
因此,我们可以使用一个数组来记录每个节点的度数,然后遍历该数组判断是否每个节点的度数都是偶数。
求出所有欧拉回路可以使用DFS搜索,以下是代码示例:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_N 101
int graph[MAX_N][MAX_N];
int degree[MAX_N];
int visited[MAX_N];
int path[MAX_N];
int path_len = 0;
int n;
void dfs(int u) {
visited[u] = 1;
path[path_len++] = u;
if (path_len == n) {
for (int i = 0; i < path_len; i++) {
printf("%d ", path[i]);
}
printf("\n");
} else {
for (int v = 1; v <= n; v++) {
if (graph[u][v] && !visited[v]) {
dfs(v);
}
}
}
visited[u] = 0;
path_len--;
}
int main() {
scanf("%d", &n);
int m;
scanf("%d", &m);
for (int i = 0; i < m; i++) {
int u, v;
scanf("%d%d", &u, &v);
graph[u][v] = graph[v][u] = 1;
degree[u]++;
degree[v]++;
}
int is_eulerian = 1;
for (int i = 1; i <= n; i++) {
if (degree[i] % 2 == 1) {
is_eulerian = 0;
break;
}
}
if (is_eulerian) {
dfs(1);
} else {
printf("Not Eulerian\n");
}
return 0;
}
```
输入格式为:
```
n m // 图的节点数和边数
u1 v1 // 边的起点和终点
u2 v2
...
```
输出格式为:
如果图不是欧拉图,则输出 "Not Eulerian"。
如果图是欧拉图,则输出所有欧拉回路,每个回路占一行,节点之间用空格隔开。