最小生成树之kruskal算法

最小生成树之kruskal算法

1.kruskal算法

假设连通网N＝（V，{E}）。则令最小生成树的初始状态为只有n个顶点而无边的非连通图T＝（V，{}），图中每个顶点自成一个连通分量。在E中选择最小代价的边，若该边依附的顶点落在T中不同的连通分量中，则将该边加入到T中，否则舍去此边而选择下一条代价最小的边，依次类推，直到T中所有顶点都在同一连通分量上为止。

示例如下：

图中先将每个顶点看作独立的子图，然后查找最小权值边，这条边是有限制条件的，边得两个顶点必须不在同一个图中，如上图，第一个图中找到最小权值边为（v1，v3），且满足限制条件，继续查找到边（v4，v6），（v2，v5），（v3，v6），当查找到最后一条边时，仅仅只有（v2，v3）满足限制条件，其他的如（v3，v4），（v1，v4）都在一个子图里面，不满足条件，至此已经找到最小生成树的所有边。

2.kruskal算法程序设计

由于我们要查找边权值最小的边，那么我们的第一步应该把边权值排序，这样就可以很快查找到权值最小的边，为了简化程序设计，我们不使用其他的数据结构，仅仅设立一个结构体数组来存储边，用一个标记数组来标记哪些边已经被选择（实际程序设计的时候没有用到标记数组）；

解决了边得存储和排序问题，现在是算法最关键的就是怎么判断边的两个顶点不在一个子图里面，一个简单的办法是设立一个辅助数组f[n]，初始化如下：

void Initialize()

{

int i;

for(i=0; i

 f[i] = i;

}

如此初始化是为了让每个顶点各自为一个图，如果找到一条边（i,j）那么做如下标记：(i

void Mark_same(int i, int j)

{

//找到i的父节点

while(f[i] != i)

{

i= f[i];

}

f[j] = i;//将j指向其父节点

}

上面的标记过程也给了我们怎么判断两个顶点是否在一个图中找到了方法，即判断其父节点是否相同，相同则是在一个图里；

int Is_same(int i, int j)

{

//找到i的父节点

while(f[i] != i)

{

i= f[i];

}

//找到i的父节点

while(f[j] != j)

{

j= f[j];

}

return i == j ? 1 : 0;

}

注意：实际设计程序的时候不用标记已选边，因为已选择的边会讲端点集合合并为一个集合，从而在判断是否为同一集合的时候就可以排除了。

测试用例：

Kruskal.txt

0 1 6

0 2 1

0 3 5

1 2 5

1 4 3

2 3 5

2 4 6

2 5 4

4 5 6

3 5 2

测试程序：

#include 

#include 

 

#define MAX 100

#define N 6//顶点数目 

 

/* 定义边(x,y)，权为w */

typedef struct

{

int x,y;

int w;

}edge;

 

edge e[MAX];

/* father[x]表示x的父节点 */

int father[N];

 

/* 比较函数，按权值(相同则按x坐标)非降序排序 */

int cmp(const void *a, const void *b)

{

if ((*(edge *)a).w == (*(edge *)b).w)

{

return (*(edge *)a).x - (*(edge *)b).x;

}

return (*(edge *)a).w - (*(edge *)b).w;

}

 

/* 判断集合是否相同 */

int Is_same(int i, int j)

{

//找到i的父节点

while(father[i] != i)

{

i =  father[i];

}

//找到i的父节点

while(father[j] != j)

{

j = father[j];

}

return i == j ? 1 : 0;

}

/* 合并x,y所在的集合 */

void Mark_same(int i, int j)

{

int temp;

if(i > j)

{

temp = i;

i = j;

j = temp;

} 

//找到i的父节点

while(father[i] != i)

{

i= father[i];

}

father[j] = i;//将j指向其父节点

}

//初始化 father数组 

void Initialize()

{

int i;

for(i=0; i

 father[i] = i;

}

/* 主函数 */

int main()

{

int i = 0,j, n;

int x, y;

  FILE *fr;

fr = fopen("kruskal.txt","r");

if(!fr)

{

printf("fopen failed\n");

exit(1); 

}

/* 读取边信息并初始化集合 */

while(fscanf(fr,"%d %d %d", &e[i].x, &e[i].y, &e[i].w) != EOF)

i++;

/* 将边排序 */

qsort(e, i, sizeof(edge), cmp);

Initialize();

 

for (i = 0; i < N; i++)

{

if(!Is_same(e[i].x, e[i].y))

{

printf("%d %d\n",e[i].x+1, e[i].y+1);

Mark_same(e[i].x, e[i].y);

}

}

 

system("pause");

return 0;

}

程序结果：

1 3

4 6

2 5

3 6

1 4

2 3

请按任意键继续. . .