普里姆算法和克鲁斯卡尔算法

Prim

设图G=(V,E)是一个具有n个顶点的连通网，其生成树的顶点集合为U。首先把v0放入U，再在所有的u∈U,v∈V-U的边(u,v)∈E中找一条最小权值的边，加入生成树，并把该边的v加入U集合。如果U集合已经有n个元素，则结束，否则在剩下的部分中继续寻找最小权值的边。

 1 #include
 2 #include
 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("\nEnter the adjacency matrix:\n");
18     
19     for(i=0;i)
20         for(j=0;j)
21             scanf("%d",&G[i][j]);
22     
23     total_cost=prims();
24     printf("\nspanning tree matrix:\n");
25     
26     for(i=0;i)
27     {
28         printf("\n");
29         for(j=0;j)
30             printf("%d\t",spanning[i][j]);
31     }
32     
33     printf("\n\nTotal 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)
45         for(j=0;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)
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)
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)
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
  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("\nEnter number of vertices:");
 32     
 33     scanf("%d",&n);
 34     
 35     printf("\nEnter the adjacency matrix:\n");
 36     
 37     for(i=0;i)
 38         for(j=0;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)
 51         for(j=0;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)
 65         belongs[i]=i;
 66     
 67     spanlist.n=0;
 68     
 69     for(i=0;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)
 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)
103         for(j=0;j1;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)
117     {
118         printf("\n%d\t%d\t%d",spanlist.data[i].u,spanlist.data[i].v,spanlist.data[i].w);
119         cost=cost+spanlist.data[i].w;
120     }
121  
122     printf("\n\nCost of the spanning tree=%d",cost);
123 }