大林算法c语言
时间: 2023-07-26 18:12:28 浏览: 58
大林算法(Dulmage-Mendelsohn decomposition)是一种图论算法,用于将一个二分图(或称双向图)分解为一组最大匹配和一组最小点覆盖。
以下是一个基于C语言实现的大林算法示例:
```c
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define MAXN 100 // 最大顶点数
#define INF 0x7fffffff // 无穷大
int n; // 顶点数
int w[MAXN][MAXN]; // 邻接矩阵
int llink[MAXN], rlink[MAXN]; // 左、右侧顶点所连的顶点编号
bool visited[MAXN]; // 判断右半边的顶点是否被访问过
bool dfs(int u)
{
int v;
for (v = 0; v < n; v++)
{
if (w[u][v] && !visited[v])
{
visited[v] = true;
if (rlink[v] == -1 || dfs(rlink[v]))
{
llink[u] = v;
rlink[v] = u;
return true;
}
}
}
return false;
}
int bipartite_matching()
{
int ans = 0;
int i, j;
for (i = 0; i < n; i++)
{
llink[i] = -1;
rlink[i] = -1;
}
for (i = 0; i < n; i++)
{
for (j = 0; j < n; j++)
{
visited[j] = false;
}
if (dfs(i))
{
ans++;
}
}
return ans;
}
int min_vertex_cover()
{
int ans = bipartite_matching();
int i, j;
bool left[MAXN], right[MAXN];
for (i = 0; i < n; i++)
{
left[i] = right[i] = false;
}
for (i = 0; i < n; i++)
{
if (llink[i] == -1)
{
left[i] = true;
}
}
for (i = 0; i < n; i++)
{
if (llink[i] != -1)
{
for (j = 0; j < n; j++)
{
if (w[i][j] && rlink[j] == -1)
{
right[j] = true;
}
}
}
}
for (i = 0; i < n; i++)
{
if (left[i])
{
printf("%d ", i + 1);
}
}
for (i = 0; i < n; i++)
{
if (right[i])
{
printf("%d ", i + 1);
}
}
printf("\n");
return ans;
}
int main()
{
int i, j;
scanf("%d", &n);
for (i = 0; i < n; i++)
{
for (j = 0; j < n; j++)
{
scanf("%d", &w[i][j]);
}
}
printf("The size of minimum vertex cover is %d.\n", min_vertex_cover());
return 0;
}
```
注意,大林算法的时间复杂度是 $O(n^3)$,适用于顶点数较少的二分图分解。