c语言 关联矩阵求欧拉回路

欧拉回路是指一条路径可以遍历图中的每条边恰好一次，且最终回到起点。而欧拉回路存在的条件是：图必须是连通的且每个节点的度数都为偶数。

关联矩阵是一个二维矩阵，用来表示有向图中的边与节点之间的关系。每一列代表一个节点，每一行代表一条有向边。如果边从节点i指向节点j，则在第i行第j列的位置上标记为1，否则为0。

下面是求解欧拉回路的C语言代码，假设有n个节点，m条边，关联矩阵用二维数组matrix表示：

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

#define MAXN 1000

int matrix[MAXN][MAXN]; // 关联矩阵
int visited[MAXN]; // 标记节点是否已被访问
int degree[MAXN]; // 记录每个节点的度数

void dfs(int u, int n) {
    visited[u] = 1;
    for (int v = 0; v < n; v++) {
        if (matrix[u][v]) { // 如果u与v之间存在一条边
            matrix[u][v] = matrix[v][u] = 0; // 删除该边
            dfs(v, n); // 继续遍历
        }
    }
}

int main() {
    int n, m;
    scanf("%d%d", &n, &m);

    // 初始化关联矩阵
    for (int i = 0; i < m; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        matrix[u][v] = matrix[v][u] = 1;
        degree[u]++, degree[v]++;
    }

    // 判断是否存在欧拉回路
    int flag = 1; // 标记是否存在欧拉回路
    for (int i = 0; i < n; i++) {
        if (degree[i] % 2 != 0) { // 如果存在度数为奇数的节点
            flag = 0;
            break;
        }
    }

    if (!flag) {
        printf("No Euler circuit.\n");
        return 0;
    }

    // 寻找欧拉回路
    dfs(0, n); // 从0节点开始遍历
    for (int i = 0; i < n; i++) {
        if (!visited[i] && degree[i] > 0) { // 如果存在未遍历的节点
            flag = 0;
            break;
        }
    }

    if (!flag) {
        printf("No Euler circuit.\n");
        return 0;
    }

    printf("Euler circuit: ");
    dfs(0, n); // 重新遍历一遍
    for (int i = 0; i < n; i++) {
        if (visited[i]) {
            printf("%d ", i);
        }
    }
    printf("\n");

    return 0;
}

上述代码中，dfs函数用来遍历每一个连通块，并删除每一条遍历的边。如果遍历完一个连通块后，还存在度数不为0的节点，则说明该图没有欧拉回路。如果所有连通块都遍历完了，且所有节点的度数都为0，则说明该图存在欧拉回路。

在主函数中，我们先判断是否存在欧拉回路，如果不存在，则直接输出"No Euler circuit."，否则再进行欧拉回路的寻找。