离散数学 二部图的所有完备匹配算法 c++代码

二部图是指一个图的顶点可以被分为两个不相交的集合，图的每条边的两个端点分别属于这两个集合。完备匹配是指图中的每个顶点有且仅有一条边与之关联的情况。

二部图的所有完备匹配算法可以使用深度优先搜索（DFS）来实现。以下是用C代码表示的算法：

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

#define N 100

bool visited[N];  // 记录顶点是否已访问
int match[N];  // 记录匹配的顶点
int g[N][N];  // 图的邻接矩阵

bool dfs(int u, int m, int n) {
    // 对顶点u进行深度优先搜索，m和n分别是左右两个集合的大小
    for (int v = 1; v <= n; v++) {
        if (g[u][v] && !visited[v]) {
            visited[v] = true;
            // 如果v还未匹配或者能找到增广路径的下一个点
            if (match[v] == 0 || dfs(match[v], m, n)) {
                match[v] = u;
                return true;
            }
        }
    }
    return false;
}

int bipartiteMatching(int m, int n) {
    // 二部图的完备匹配
    int count = 0;
    for (int u = 1; u <= m; u++) {
        // 初始化visited数组
        for (int i = 1; i <= n; i++) {
            visited[i] = false;
        }
        if (dfs(u, m, n)) {
            count++;
        }
    }
    return count;
}

int main() {
    int m, n;  // 分别代表左右两个集合的大小
    scanf("%d %d", &m, &n);
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            scanf("%d", &g[i][j]);  // 输入边的信息
        }
    }
    int matching = bipartiteMatching(m, n);
    printf("完备匹配的个数：%d\n", matching);
    return 0;
}

在上述代码中，我们使用邻接矩阵来表示二部图的边的关系，g[i][j]为1表示第i个点和第j个点之间有一条边。match[]数组用来记录匹配的顶点，初始时所有元素为0。dfs()函数是主要的搜索函数，用来寻找增广路径。bipartiteMatching()函数是二部图完备匹配的主要函数，通过遍历左侧集合中的每个顶点来找到所有的完备匹配。最终输出找到的完备匹配的个数。

希望对你有所帮助！