最小生成树kruskal算法-数据结构课程设计 第2页

void sort(edge edges[],MGraph *G)//对权值进行排序
{
int i, j;

for ( i = 1; i < G->arcnum; i++)
{
for ( j = i + 1; j <= G->arcnum; j++)
{
if (edges[i].weight > edges[j].weight)
{
Swapn(edges, i, j);
}
}
}

printf("权排序之后的为:\n");
for (i = 1; i < G->arcnum; i++)
{
printf("<< %d, %d >>   %d\n", edges[i].begin, edges[i].end, edges[i].weight);
}

}

void Swapn(edge *edges,int i, int j)//交换权值 以及头和尾
{

int temp;

temp = edges[i].begin;
edges[i].begin = edges[j].begin;
edges[j].begin = temp;
temp = edges[i].end;
edges[i].end = edges[j].end;
edges[j].end = temp;
temp = edges[i].weight;
edges[i].weight = edges[j].weight;
edges[j].weight = temp;
}

void MiniSpanTree(MGraph *G)//生成最小生成树
{
int i, j, n, m;
int k = 1;
int parent[M];

edge edges[M];

for ( i = 1; i < G->vexnum; i++)
{
for (j = i + 1; j <= G->vexnum; j++)
{
if (G->arc[i][j].adj == 1)
{
edges[k].begin = i;
edges[k].end = j;
edges[k].weight = G->arc[i][j].weight;
k++;
}

}
}

sort(edges, G);
for (i = 1; i <= G->arcnum; i++)
{
parent[i] = 0;
}
printf("最小生成树为:\n");
for (i = 1; i <= G->arcnum; i++)//核心部分
{
n = Find(parent, edges[i].begin);
m = Find(parent, edges[i].end);
if (n != m)
{
parent[n] = m;
printf("<< %d, %d >>   %d\n", edges[i].begin, edges[i].end, edges[i].weight);
}
}
}

int Find(int *parent, int f)//找尾
{
while ( parent[f] > 0)
{
f = parent[f];
}
return f;
}

int main(void)//主函数
{
MGraph *G;

G = (MGraph*)malloc(sizeof(MGraph));
if (G == NULL)
{
printf("memory allcation failed,goodbye");
exit(1);
}

CreatGraph(G);
MiniSpanTree(G);

system("pause");
return 0;
}

Trackback: http://tb.blog.csdn.net/TrackBack.aspx?PostId=965291

上一页  [1] [2]