搜狗竞价推广效果怎么样_建筑行业资讯网站_廊坊seo外包公司费用_站长工具精品

克鲁卡斯尔算法有向网代码如下:

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdlib.h>
#include<stdio.h>
#include <limits.h>
#define MAX_SIZE 100
struct
{char head;char tail;int lowcost;//权值
}Edge[MAX_SIZE*(MAX_SIZE-1)/2];
typedef struct AMGraph
{char vers[MAX_SIZE];int arcs[MAX_SIZE][MAX_SIZE];int numVertex, numEdge;
}AMGraph;
int Vexset[MAX_SIZE];
int Locate(AMGraph G,char u)
{int i;for (i = 0; i < G.numVertex; i++){if (G.vers[i] == u){return i;}}return -1;
}
void CreateAMGraph(AMGraph* G)
{printf("请输入你的顶点+边数\n");scanf("%d %d", &G->numVertex, &G->numEdge);getchar();//吸收scanf残留的换行符int i, j, k, w;printf("请输入顶点信息\n");for (i = 0; i < G->numVertex; i++){scanf(" %c", &G->vers[i]);}printf("请输入(vi,vj)以及权值\n");for (k = 0; k < G->numEdge; k++){char v1, v2;printf("请输入第%d条边依附的顶点以及权值",k+1);scanf(" %c %c %d", &v1, &v2, &w);i = Locate(*G, v1);j = Locate(*G, v2);G->arcs[i][j] = w;//G->arcs[j][i] = w;//输入都Edge数组中Edge[k].head = v1;Edge[k].tail = v2;Edge[k].lowcost = w;}printf("邻接矩阵创建成功\n");
}
void Sort(AMGraph G)
{int i, j;for (i = 0; i < G.numEdge-1; i++){for (j = 0; j < G.numEdge -1-i; j++){if (Edge[j].lowcost > Edge[j+1].lowcost){char temp_head = Edge[j].head;Edge[j].head = Edge[j + 1].head;Edge[j + 1].head = temp_head;char temp_tail = Edge[j].tail;Edge[j].tail = Edge[j + 1].tail;Edge[j + 1].tail = temp_tail;int temp_lowcost = Edge[j].lowcost;Edge[j].lowcost = Edge[j + 1].lowcost;Edge[j + 1].lowcost = temp_lowcost;}}}
}
void MiniSpanTree_KrusKal(AMGraph G)
{int i, j, v1, v2, vs1, vs2;Sort(G);//将上面创建的函数时入数组的内容按权值进行排序(从小到大)for (i = 0; i < G.numVertex; i++){Vexset[i] = i;}for (i = 0; i < G.numEdge; i++){v1 = Locate(G, Edge[i].head);v2 = Locate(G, Edge[i].tail);vs1 = Vexset[v1];vs2 = Vexset[v2];if (vs1!=vs2){printf("边 %c --> %c \n", Edge[i].head, Edge[i].tail);for (j = 0; j < G.numVertex; j++){if (Vexset[j] == vs2){Vexset[j] = vs1;}}}}
}
int main()
{AMGraph G;CreateAMGraph(&G);printf("克鲁卡斯尔算法如下\n");MiniSpanTree_KrusKal(G);return 0;
}

终端输入内容如下:

请输入你的顶点+边数
6 9
请输入顶点信息
012345
请输入(vi,vj)以及权值
请输入第1条边依附的顶点以及权值0 1 5
请输入第2条边依附的顶点以及权值0 5 2
请输入第3条边依附的顶点以及权值1 2 4
请输入第4条边依附的顶点以及权值2 3 9
请输入第5条边依附的顶点以及权值3 4 7
请输入第6条边依附的顶点以及权值3 5 3
请输入第7条边依附的顶点以及权值4 0 1
请输入第8条边依附的顶点以及权值5 2 1
请输入第9条边依附的顶点以及权值5 4 8
邻接矩阵创建成功
克鲁卡斯尔算法如下
边 4 --> 0
边 5 --> 2
边 0 --> 5
边 3 --> 5
边 1 --> 2

 有向网图片如下:

克鲁卡斯尔算法输出后的图片如下:

克鲁卡斯尔算法无向网代码如下: 

 

	for (k = 0; k < G->numEdge; k++){char v1, v2;printf("请输入第%d条边依附的顶点以及权值",k+1);scanf(" %c %c %d", &v1, &v2, &w);i = Locate(*G, v1);j = Locate(*G, v2);G->arcs[i][j] = w;G->arcs[j][i] = w;//输入都Edge数组中Edge[k].head = v1;Edge[k].tail = v2;Edge[k].lowcost = w;}

 只需要增加一个G->arcs[j][i] = w;即可，因为对于无向图来说，是对称的

无向网终端输入如下:

请输入你的顶点+边数
6 10
请输入顶点信息
012345
请输入(vi,vj)以及权值
请输入第1条边依附的顶点以及权值0 1 6
请输入第2条边依附的顶点以及权值0 2 1
请输入第3条边依附的顶点以及权值0 3 5
请输入第4条边依附的顶点以及权值1 2 5
请输入第5条边依附的顶点以及权值1 4 3
请输入第6条边依附的顶点以及权值2 3 5
请输入第7条边依附的顶点以及权值2 4 6
请输入第8条边依附的顶点以及权值2 5 4
请输入第9条边依附的顶点以及权值4 5 6
请输入第10条边依附的顶点以及权值5 3 2
邻接矩阵创建成功
克鲁卡斯尔算法如下
边 0 --> 2
边 5 --> 3
边 1 --> 4
边 2 --> 5
边 1 --> 2

无向网的图片如下:

克鲁卡斯尔算法后的图片如下: