建立通信网络(3)

printf(\权排序之后的为:\\n\ for (i = 1; i <= G->arcnum; i++) { printf(\ %d\\n\ } }

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[m] = n; printf(\ %d\\n\ } } }

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(\ exit(1); } CreatGraph(G);

MiniSpanTree(G); system(\ return 0; }