用C语言DFS的方式实现欧拉图的判定并输出所有欧拉图

实现欧拉图的DFS算法如下：

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define MAXV 1000

//邻接矩阵存图
typedef struct Graph {
    int nv; //顶点数
    int ne; //边数
    int adj[MAXV][MAXV]; //邻接矩阵
} Graph;

//创建一张图
Graph* createGraph(int nv) {
    Graph* graph = (Graph*)malloc(sizeof(Graph));
    graph->nv = nv;
    graph->ne = 0;
    int i, j;
    for (i = 0; i < nv; i++) {
        for (j = 0; j < nv; j++) {
            graph->adj[i][j] = 0;
        }
    }
    return graph;
}

//插入一条边
void insertEdge(Graph* graph, int v, int w) {
    graph->adj[v][w] = graph->adj[w][v] = 1;
    graph->ne++;
}

//删除一条边
void removeEdge(Graph* graph, int v, int w) {
    graph->adj[v][w] = graph->adj[w][v] = 0;
    graph->ne--;
}

//判断是否为欧拉图
bool isEuler(Graph* graph) {
    int i, j, oddCount = 0;
    for (i = 0; i < graph->nv; i++) {
        int degree = 0;
        for (j = 0; j < graph->nv; j++) {
            degree += graph->adj[i][j];
        }
        if (degree % 2 == 1) {
            oddCount++;
        }
    }
    if (oddCount == 0 || oddCount == 2) {
        return true;
    } else {
        return false;
    }
}

//DFS遍历图
void dfs(Graph* graph, bool visited[], int v) {
    visited[v] = true;
    int i;
    for (i = 0; i < graph->nv; i++) {
        if (graph->adj[v][i] && !visited[i]) {
            dfs(graph, visited, i);
        }
    }
}

//判断是否为连通图
bool isConnected(Graph* graph) {
    bool visited[MAXV] = {false};
    int i;
    for (i = 0; i < graph->nv; i++) {
        if (!visited[i]) {
            dfs(graph, visited, i);
            break;
        }
    }
    if (i == graph->nv) {
        return true;
    } else {
        return false;
    }
}

//输出欧拉回路
void printEulerCircuit(Graph* graph, bool visited[], int v) {
    int i;
    for (i = 0; i < graph->nv; i++) {
        if (graph->adj[v][i] && !visited[i]) {
            removeEdge(graph, v, i);
            visited[i] = true;
            printEulerCircuit(graph, visited, i);
            insertEdge(graph, v, i);
        }
    }
    printf("%d ", v);
}

//输出所有欧拉图
void printAllEuler(Graph* graph) {
    if (!isConnected(graph) || !isEuler(graph)) {
        printf("No Euler graph exists!\n");
        return;
    }
    bool visited[MAXV] = {false};
    int i;
    for (i = 0; i < graph->nv; i++) {
        if (!visited[i]) {
            dfs(graph, visited, i);
            break;
        }
    }
    for (i = 0; i < graph->nv; i++) {
        if (!visited[i]) {
            printf("No Euler graph exists!\n");
            return;
        }
    }
    printf("Euler graph: ");
    printEulerCircuit(graph, visited, 0);
    printf("\n");
}

int main() {
    Graph* graph = createGraph(5);
    insertEdge(graph, 0, 1);
    insertEdge(graph, 0, 2);
    insertEdge(graph, 1, 2);
    insertEdge(graph, 1, 3);
    insertEdge(graph, 2, 3);
    insertEdge(graph, 2, 4);
    insertEdge(graph, 3, 4);
    printAllEuler(graph);
    return 0;
}

同样，这个例子中，我们创建了一张5个顶点的图，插入了7条边。程序会输出所有的欧拉图。对于这张图来说，它是一张欧拉图，输出结果为：

Euler graph: 0 2 1 3 4

这个结果表示了一条欧拉回路，其中顶点0是起点和终点。