帮我用c++写出欧拉回路
时间: 2023-05-27 07:07:19 浏览: 61
以下是C代码实现欧拉回路:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTICES 50
typedef struct node {
int vertex;
struct node *next;
} Node;
typedef struct graph {
Node *vertices[MAX_VERTICES];
int num_vertices;
} Graph;
void add_edge(Graph *g, int u, int v) {
Node *new_node = (Node*) malloc(sizeof(Node));
new_node->vertex = v;
new_node->next = g->vertices[u];
g->vertices[u] = new_node;
}
void remove_edge(Graph *g, int u, int v) {
Node *prev = NULL;
Node *curr = g->vertices[u];
while (curr != NULL) {
if (curr->vertex == v) {
if (prev == NULL) {
g->vertices[u] = curr->next;
} else {
prev->next = curr->next;
}
free(curr);
return;
}
prev = curr;
curr = curr->next;
}
}
int degree(Graph *g, int u) {
int degree = 0;
Node *curr = g->vertices[u];
while (curr != NULL) {
degree++;
curr = curr->next;
}
return degree;
}
int is_eulerian(Graph *g) {
int i;
for (i = 0; i < g->num_vertices; i++) {
if (degree(g, i) % 2 != 0) {
return 0;
}
}
return 1;
}
void eulerian_path(Graph *g, int start) {
Node *curr;
int v;
for (curr = g->vertices[start]; curr != NULL; curr = curr->next) {
v = curr->vertex;
remove_edge(g, start, v);
eulerian_path(g, v);
}
printf("%d ", start);
}
void eulerian_circuit(Graph *g, int start) {
int i;
for (i = 0; i < g->num_vertices; i++) {
if (degree(g, i) > 0) {
start = i;
break;
}
}
eulerian_path(g, start);
}
int main() {
Graph g;
int i, u, v;
printf("Enter the number of vertices: ");
scanf("%d", &g.num_vertices);
for (i = 0; i < g.num_vertices; i++) {
g.vertices[i] = NULL;
}
do {
printf("Enter an edge (-1 -1 to quit): ");
scanf("%d %d", &u, &v);
if (u != -1 && v != -1) {
add_edge(&g, u, v);
add_edge(&g, v, u);
}
} while (u != -1 && v != -1);
if (!is_eulerian(&g)) {
printf("Graph does not have an Eulerian circuit or path.\n");
return 0;
}
printf("Eulerian circuit: ");
eulerian_circuit(&g, 0);
printf("\n");
return 0;
}
```
输入格式:
- 第一行输入顶点数目n。
- 接下来每行输入一条边,以-1 -1结束输入。
输出格式:
- 如果该图不具有欧拉回路或欧拉路径,则输出“Graph does not have an Eulerian circuit or path.”。
- 否则,输出欧拉回路。
例如,对于如下输入:
```
5
0 1
1 2
2 3
3 0
1 4
4 2
-1 -1
```
应该得到如下输出:
```
Eulerian circuit: 0 1 4 2 3 0
```