Prim
设图G=(V,E)是一个具有n个顶点的连通网，其生成树的顶点集合为U。首先把v0放入U，再在所有的u∈U,v∈V-U的边(u,v)∈E中找一条最小权值的边，加入生成树，并把该边的v加入U集合。如果U集合已经有n个元素，则结束，否则在剩下的部分中继续寻找最小权值的边。
1 #include<stdio.h>
2 #include<stdlib.h>
3
4 #define infinity 9999
5 #define MAX 20
6
7 int G[MAX][MAX],spanning[MAX][MAX],n;
8
9 int prims();
10
11 int main()
12 {
13 int i,j,total_cost;
14 printf("Enter no. of vertices:");
15 scanf("%d",&n);
16
17 printf("
Enter the adjacency matrix:
");
18
19 for(i=0;i<n;i++)
20 for(j=0;j<n;j++)
21 scanf("%d",&G[i][j]);
22
23 total_cost=prims();
24 printf("
spanning tree matrix:
");
25
26 for(i=0;i<n;i++)
27 {
28 printf("
");
29 for(j=0;j<n;j++)
30 printf("%d ",spanning[i][j]);
31 }
32
33 printf("
Total cost of spanning tree=%d",total_cost);
34 return 0;
35 }
36
37 int prims()
38 {
39 int cost[MAX][MAX];
40 int u,v,min_distance,distance[MAX],from[MAX];
41 int visited[MAX],no_of_edges,i,min_cost,j;
42
43 //create cost[][] matrix,spanning[][]
44 for(i=0;i<n;i++)
45 for(j=0;j<n;j++)
46 {
47 if(G[i][j]==0)
48 cost[i][j]=infinity;
49 else
50 cost[i][j]=G[i][j];
51 spanning[i][j]=0;
52 }
53
54 //initialise visited[],distance[] and from[]
55 distance[0]=0;
56 visited[0]=1;
57
58 for(i=1;i<n;i++)
59 {
60 distance[i]=cost[0][i];
61 from[i]=0;
62 visited[i]=0;
63 }
64
65 min_cost=0; //cost of spanning tree
66 no_of_edges=n-1; //no. of edges to be added
67
68 while(no_of_edges>0)
69 {
70 //find the vertex at minimum distance from the tree
71 min_distance=infinity;
72 for(i=1;i<n;i++)
73 if(visited[i]==0&&distance[i]<min_distance)
74 {
75 v=i;
76 min_distance=distance[i];
77 }
78
79 u=from[v];
80
81 //insert the edge in spanning tree
82 spanning[u][v]=distance[v];
83 spanning[v][u]=distance[v];
84 no_of_edges--;
85 visited[v]=1;
86
87 //updated the distance[] array
88 for(i=1;i<n;i++)
89 if(visited[i]==0&&cost[i][v]<distance[i])
90 {
91 distance[i]=cost[i][v];
92 from[i]=v;
93 }
94
95 min_cost=min_cost+cost[u][v];
96 }
97
98 return(min_cost);
99 }
COST = 16 + 5 + 6 + 11 + 18 = 56
Kruskal
1 #include<stdio.h>
2
3 #define MAX 30
4
5 typedef struct edge
6 {
7 int u,v,w;
8 }edge;
9
10 typedef struct edgelist
11 {
12 edge data[MAX];
13 int n;
14 }edgelist;
15
16 edgelist elist;
17
18 int G[MAX][MAX],n;
19 edgelist spanlist;
20
21 void kruskal();
22 int find(int belongs[],int vertexno);
23 void union1(int belongs[],int c1,int c2);
24 void sort();
25 void print();
26
27 void main()
28 {
29 int i,j,total_cost;
30
31 printf("
Enter number of vertices:");
32
33 scanf("%d",&n);
34
35 printf("
Enter the adjacency matrix:
");
36
37 for(i=0;i<n;i++)
38 for(j=0;j<n;j++)
39 scanf("%d",&G[i][j]);
40
41 kruskal();
42 print();
43 }
44
45 void kruskal()
46 {
47 int belongs[MAX],i,j,cno1,cno2;
48 elist.n=0;
49
50 for(i=1;i<n;i++)
51 for(j=0;j<i;j++)
52 {
53 if(G[i][j]!=0)
54 {
55 elist.data[elist.n].u=i;
56 elist.data[elist.n].v=j;
57 elist.data[elist.n].w=G[i][j];
58 elist.n++;
59 }
60 }
61
62 sort();
63
64 for(i=0;i<n;i++)
65 belongs[i]=i;
66
67 spanlist.n=0;
68
69 for(i=0;i<elist.n;i++)
70 {
71 cno1=find(belongs,elist.data[i].u);
72 cno2=find(belongs,elist.data[i].v);
73
74 if(cno1!=cno2)
75 {
76 spanlist.data[spanlist.n]=elist.data[i];
77 spanlist.n=spanlist.n+1;
78 union1(belongs,cno1,cno2);
79 }
80 }
81 }
82
83 int find(int belongs[],int vertexno)
84 {
85 return(belongs[vertexno]);
86 }
87
88 void union1(int belongs[],int c1,int c2)
89 {
90 int i;
91
92 for(i=0;i<n;i++)
93 if(belongs[i]==c2)
94 belongs[i]=c1;
95 }
96
97 void sort()
98 {
99 int i,j;
100 edge temp;
101
102 for(i=1;i<elist.n;i++)
103 for(j=0;j<elist.n-1;j++)
104 if(elist.data[j].w>elist.data[j+1].w)
105 {
106 temp=elist.data[j];
107 elist.data[j]=elist.data[j+1];
108 elist.data[j+1]=temp;
109 }
110 }
111
112 void print()
113 {
114 int i,cost=0;
115
116 for(i=0;i<spanlist.n;i++)
117 {
118 printf("
%d %d %d",spanlist.data[i].u,spanlist.data[i].v,spanlist.data[i].w);
119 cost=cost+spanlist.data[i].w;
120 }
121
122 printf("
Cost of the spanning tree=%d",cost);
123 }
