プリムアルゴリズム
20195 ワード
1 /*
2 ：
3 ， ，
4 */
5 # include <stdio.h>
6
7 typedef char VertexType;//
8 typedef int EdgeType;//
9 # define MAX_VERTEX 100//
10 # define INFINITY 65535// 65535
11
12 typedef struct
13 {//
14 VertexType vexs[MAX_VERTEX];//
15 EdgeType arc[MAX_VERTEX][MAX_VERTEX];//
16 int numVertexs, numEdges;//
17
18 }MGraph;
19
20 void CreateMGraph(MGraph *G)
21 {
22 int i, j;
23 G->numEdges=15;
24 G->numVertexs=9;
25
26 for (i = 0; i < G->numVertexs; i++)
27 {
28 for ( j = 0; j < G->numVertexs; j++)
29 {
30 if (i==j)
31 G->arc[i][j]=0;
32 else
33 G->arc[i][j] = G->arc[j][i] = INFINITY;
34 }
35 }
36
37 G->arc[0][1]=10;
38 G->arc[0][5]=11;
39 G->arc[1][2]=18;
40 G->arc[1][8]=12;
41 G->arc[1][6]=16;
42 G->arc[2][8]=8;
43 G->arc[2][3]=22;
44 G->arc[3][8]=21;
45 G->arc[3][6]=24;
46 G->arc[3][7]=16;
47 G->arc[3][4]=20;
48 G->arc[4][7]=7;
49 G->arc[4][5]=26;
50 G->arc[5][6]=17;
51 G->arc[6][7]=19;
52
53 for(i = 0; i < G->numVertexs; i++)
54 {
55 for(j = i; j < G->numVertexs; j++)
56 {
57 G->arc[j][i] =G->arc[i][j];
58 }
59 }
60
61 }
62
63 void MinSpanTree_Peim (MGraph &G)
64 {// ，
65 int min, i, j, k;
66 int add=0;
67 int adjvex[MAX_VERTEX];
68 int lowcost[MAX_VERTEX];
69 lowcost[0] = 0;
70 adjvex[0] = 0;
71
72 for (i=1; i<G.numVertexs; i++)
73 {// v0 ， v0 lowcost ，adjvex 0；
74 lowcost[i] = G.arc[0][i];//
75 adjvex[i] = 0;// 0
76 }
77
78 for (i=1; i<G.numVertexs; i++)
79 {//
80 min = INFINITY;//
81 j=1;
82 k=0;
83
84 while (j < G.numVertexs)
85 {// lowcost ， min， k
86 if (lowcost[j]!=0 && lowcost[j]<min)
87 {
88 min = lowcost[j];//
89 k = j;//
90 }
91 j++;
92 }
93 printf ("(%d——%d)
", adjvex[k], k);
94 add = add + G.arc[adjvex[k]][k];
95 /* 52~56 adjvex 0， 0， lowcost
96 ( )， lowcost ， lowcost */
97 lowcost[k] = 0;
98 // 1(k=1), for 1
99 for (j=1; j<G.numVertexs; j++)
100 {// lowcost lowcos 。
101 //
102 if (lowcost[j]!=0 && G.arc[k][j]<lowcost[j])//t
103 {
104 lowcost[j] = G.arc[k][j];//0
105 adjvex[j] = k;
106 }
107 }
108 }
109 printf ("%d
", add);
110
111 return;
112 }
113
114 int main (void)
115 {
116 MGraph G;
117 CreateMGraph (&G);
118 MinSpanTree_Peim (G);
119
120 return 0;
121 }
122
123 /*
124 vc++6.0 ：
125 ：9 15
126 1 ：v0
127 2 ：v1
128 3 ：v2
129 4 ：v3
130 5 ：v4
131 6 ：v5
132 7 ：v6
133 8 ：v7
134 9 ：v8
135 (vi,vj) i， j w：0 1 10
136 (vi,vj) i， j w：0 5 11
137 (vi,vj) i， j w：1 6 16
138 (vi,vj) i， j w：1 2 18
139 (vi,vj) i， j w：1 8 12
140 (vi,vj) i， j w：2 8 8
141 (vi,vj) i， j w：2 3 22
142 (vi,vj) i， j w：8 3 21
143 (vi,vj) i， j w：6 5 17
144 (vi,vj) i， j w：6 3 24
145 (vi,vj) i， j w：6 7 19
146 (vi,vj) i， j w：3 4 20
147 (vi,vj) i， j w：3 7 16
148 (vi,vj) i， j w：4 7 7
149 (vi,vj) i， j w：4 5 26
150 (0——1)
151 (0——5)
152 (1——8)
153 (8——2)
154 (1——6)
155 (6——7)
156 (7——4)
157 (7——3)
158 Press any key to continue
159
160 */