データ構造(厳格版)教科書コードを再ノックします.
116396 ワード
データ構造第七章図
四つの基本記憶構造の隣接行列表示法
隣接表表示法
クロスリンク表示法
隣接多重表表示法
図の連結成分と生成ツリーがない
テストデータ
3 13 13 0 ABCDEFGHIJKLM A＿A＿A＿B＿B＿M＿E＿H＿G＿I＿H＿J＿M L
最小生成樹のプリムアルゴリズム
テストデータ:
3 6 10 ABCDEF A 6 A D 5 A C 1 B 5 B E 3 C 5 C E 6 C 4 D F 2 E 6
トポロジー
最短経路-ディジェストラ
テストデータ
//迪杰特斯1 6 8 0 ABCDEF A 10 A E 30 A F 100 B C 5 C D 50 E D 20 E F 60 D F 10
転載先:https://www.cnblogs.com/twomeng/p/9509532.html
四つの基本記憶構造の隣接行列表示法
1 /*
2 * ：
3 * ：2018/4/1
4 */
5
6 /*
7 ：
8 enum < > {< >};
9 enum day {Sun,Mon,Tue,Wed,Thu,Fri,Sat};
10 day d1,d2,d3;
11 d1 = Thu; d2 = Sat; d3 = Tue;
12 ， , 。
13 */
14 #include
15 #define INFINITY INT_MAX
16
17
18 using namespace std;
19 // /
20 const int MAXSIZE = 20;
21 typedef char vertexType;
22 typedef int vrType;
23 typedef char infoType;
24 typedef enum{DG,DN,UDG,UDN} graphKind;
25
26 typedef struct arcCell
27 {
28 vrType adj;
29 infoType *info;
30 }arcCell,adjMatrix[MAXSIZE][MAXSIZE];
31
32 typedef struct
33 {
34 vertexType vex[MAXSIZE];
35 adjMatrix arc;
36 int vexnum,arcnum;
37 graphKind kind;
38 }MGraph;
39
40 int locate(MGraph &g,vertexType v)
41 {
42 for (int i=0;i)
43 {
44 if( g.vex[i] == v)
45 return i;
46 }
47 return -1;
48 }
49 void createUDN(MGraph &g)
50 {
51 int hasInfo;
52 cout << " 、 、 "<<endl;
53 cin >> g.vexnum >>g.arcnum >> hasInfo;
54 int i,j;
55 for (i=0;i)
56 {
57 cin >>g.vex[i];
58 }
59 for (i=0;i)
60 for (j=0;j)
61 {
62 g.arc[i][j].adj = INFINITY;
63 g.arc[i][j].info = NULL;
64 }
65 vertexType v1,v2;
66 vrType w;
67 cout << " ：" <<endl;
68 for (int k=0;k)
69 {
70 cin >>v1 >>v2>>w;
71 i = locate(g,v1);
72 j = locate(g,v2);
73 g.arc[i][j].adj = w;
74 if (hasInfo)
75 cin >> g.arc[i][j].info;
76 g.arc[j][i] = g.arc[i][j];
77 }
78 }
79 void createGraph(MGraph &g)
80 {
81 graphKind kind;
82 cout << "graphkind"<<endl ;
83 cin >> (int &)kind;
84 switch(kind)
85 {
86 case UDN:createUDN(g);
87 }
88 }
89 void printMatrix(MGraph &g)
90 {
91 int i,j;
92 for (i=0;i< g.vexnum ; i++)
93 {
94 for (j = 0 ;j)
95 {
96 if (g.arc[i][j].adj == INFINITY)
97 cout << '#' << ' ';
98 else
99 cout << g.arc[i][j].adj <<' ';
100 }
101 cout <<endl;
102 }
103
104 }
105 //
106 bool visited[MAXSIZE];
107
108 int firstAdjVex(MGraph &g,int v)
109 {
110 // ， v ，
111 int j;
112 for (j = 0; j < g.vexnum ; j++)
113 {
114 if (g.arc[v][j].adj!=INFINITY)
115 return j;
116 }
117 return -1;
118 }
119 int nextAdjVex(MGraph &g,int v,int w)
120 {
121 // v w
122 int j;
123 for (j = w+1;j)
124 {
125 if (g.arc[v][j].adj!=INFINITY)
126 return j;
127 }
128 return -1;
129 }
130 void DFS(MGraph &g,int v)
131 {
132 visited[v] = true; // V
133 cout << g.vex[v] << ' ';
134 for (int w = firstAdjVex(g,v); w >= 0 ;w = nextAdjVex(g,v,w))
135 {
136 if (!visited[w])
137 DFS(g,w);// DFS
138 }
139 }
140 void DFSTraverse(MGraph &g)
141 {
142 int i;
143 for (i=0;i)
144 visited[i] = false; // visited,
145 for (i=0;i//
146 {
147 if (!visited[i])
148 DFS(g,i);
149 }
150
151 }
152 int main()
153 {
154 MGraph g;
155 createGraph(g);
156 // printMatrix(g);
157 DFSTraverse(g);
158
159 return 0;
160 } 隣接表表示法
1 /*
2 * ：
3 * ：2018/4/1
4 */
5
6 /*
7 ：
8 enum < > {< >};
9 enum day {Sun,Mon,Tue,Wed,Thu,Fri,Sat};
10 day d1,d2,d3;
11 d1 = Thu; d2 = Sat; d3 = Tue;
12 ， , 。
13 */
14 #include
15 #include <string>
16 #include
17 #define INFINITY INT_MAX
18
19
20 using namespace std;
21
22 //
23
24 const int MAXSIZE = 20;
25
26 typedef char vertexType;
27 typedef char infoType;
28 typedef enum{DG,UDG} graphKind;
29
30 typedef struct arcNode
31 {
32 int adjvex;
33 infoType *info;
34 struct arcNode *nextarc;
35 }arcNode;
36
37 typedef struct
38 {
39 vertexType data;
40 struct arcNode *firstarc;
41 }VNode;
42
43 typedef struct
44 {
45 VNode adjList[MAXSIZE];
46 int vexnum,arcnum;
47 graphKind kind;
48 }ALGraph;
49
50 int locate(ALGraph &g,vertexType v)
51 {
52 int i;
53 for (i = 0;i)
54 {
55 if ( g.adjList[i].data == v )
56 return i;
57 }
58 return -1;
59 }
60
61 void createUDG(ALGraph &g)
62 {
63 int hasInfo;
64 cout << " 、 、 "<<endl;
65 cin >> g.vexnum >> g.arcnum>>hasInfo;
66 int i,j,k;
67 cout << " " <<endl;
68 for (i=0;i)
69 {
70 cin >> g.adjList[i].data ;
71 g.adjList[i].firstarc = NULL;
72 }
73 vertexType v1,v2;
74 arcNode *p,*q;
75 cout << " ：" <<endl;
76 for (k = 0; k < g.arcnum;k++)
77 { //
78 cin >> v1 >> v2;
79 i = locate(g,v1);
80 j = locate(g,v2);
81 p = (arcNode*)malloc(sizeof(arcNode));
82 if (hasInfo)
83 cin >> p->info;
84 p->adjvex = j;
85 p->nextarc = g.adjList[i].firstarc;
86 g.adjList[i].firstarc = p;
87
88 //
89 q = (arcNode*)malloc(sizeof(arcNode));
90 if (hasInfo)
91 q->info = p->info;
92 q->adjvex = i;
93 q->nextarc = g.adjList[j].firstarc;
94 g.adjList[j].firstarc = q;
95 }
96 }
97
98 void createDG(ALGraph &g)
99 {
100 int hasInfo;
101 cout << " 、 、 "<<endl;
102 cin >>g.vexnum >>g.arcnum >> hasInfo;
103
104 int i,j,k;
105 cout << " " <<endl;
106 for (i=0;i)
107 {
108 cin >> g.adjList[i].data;
109 g.adjList[i].firstarc = NULL;
110 }
111 arcNode *p;
112 vertexType v1,v2;
113 cout << " " <<endl ;
114 for (k = 0;k)
115 {
116 cin >>v1>>v2;
117 i = locate(g,v1);
118 j = locate(g,v2);
119 p = (arcNode*)malloc(sizeof(arcNode));
120 p->adjvex = j;
121 p->nextarc = g.adjList[i].firstarc;
122 if (hasInfo)
123 cin >> p->info;
124 g.adjList[i].firstarc = p;
125 }
126
127
128 }
129
130 void buildNALG(ALGraph &g,ALGraph &ng)
131 {
132 ng.vexnum = g.vexnum;
133 ng.arcnum = g.arcnum;
134
135 int i,j;
136 for (i=0;i)
137 {
138 ng.adjList[i].data = g.adjList[i].data;
139 ng.adjList[i].firstarc = NULL;
140 }
141 arcNode *p,*q;
142 for (i = 0;i)
143 {
144 for (j = 0;j)
145 {
146 if (i==j)
147 continue;
148 p = g.adjList[j].firstarc;
149 while (p)
150 {
151 if (p->adjvex == i)
152 {
153 q = (arcNode *)malloc(sizeof(arcNode));
154 q->adjvex = j;
155 q->info = p->info;
156 q->nextarc = ng.adjList[i].firstarc;
157 ng.adjList[i].firstarc = q;
158 }
159 p = p->nextarc;
160 }
161
162 }
163 }
164 }
165
166 void createGraph(ALGraph &g)
167 {
168 graphKind kind;
169 cout << "kind:"<<endl;
170 cin >> (int &)kind;
171 switch(kind)
172 {
173 case UDG:createUDG(g);break;
174 case DG:createDG(g);
175 }
176 }
177 void printGraph(ALGraph &g)
178 {
179 int i;
180 arcNode *p;
181 for (i=0;i)
182 {
183 if (!g.adjList[i].firstarc)
184 cout <"->NULL";
185 else
186 cout << g.adjList[i].data <<"->";
187 p = g.adjList[i].firstarc;
188 while (p)
189 {
190 if (!p->nextarc)
191 cout <adjvex;
192 else
193 cout <adjvex << "->";
194 p = p->nextarc;
195 }
196 cout <<endl;
197 }
198
199 }
200 //
201 bool visited[MAXSIZE];
202
203 int firstAdjVex(ALGraph &g,int v)
204 {
205 if (g.adjList[v].firstarc)
206 return g.adjList[v].firstarc->adjvex;
207 else
208 return -1;
209 }
210 int nextAdjVex(ALGraph &g,int v,int w)
211 {
212 arcNode *p;
213 p = g.adjList[v].firstarc;
214 for (p ; p ; p = p ->nextarc)
215 {
216 if (p->adjvex == w)
217 {
218 if (p->nextarc)
219 {
220 return p->nextarc->adjvex;
221 }
222 else
223 return -1;
224 }
225 }
226 }
227 void DFS(ALGraph &g,int v)
228 {
229 visited[v] = true;
230 cout << g.adjList[v].data<<' ';
231 for (int w = firstAdjVex(g,v) ; w>=0 ; w = nextAdjVex(g,v,w)) // w, return -1！
232 {
233 if (!visited[w])
234 DFS(g,w);
235 }
236 }
237 void DFSTraverse(ALGraph &g)
238 {
239 int i;
240 for (i=0;i)
241 {
242 visited[i] = false;
243 }
244 for (i = 0;i)
245 {
246 if (!visited[i])
247 DFS(g,i);
248 }
249 }
250
251 //
252 void BFSTraverse(ALGraph &g)
253 {
254 for (int i = 0;i)
255 visited[i] = false;
256 queue<int> que;
257 for (int i = 0;i)
258 {
259 if (!visited[i])
260 {
261 visited[i] = true;
262 cout << g.adjList[i].data<<' ';
263 que.push(i);
264 while (!que.empty())
265 {
266 int u = que.front();
267 que.pop();
268 for (int w = firstAdjVex(g,u) ; w >=0 ;w= nextAdjVex(g,u,w))
269 {
270 if (!visited[w])
271 {
272 visited[w] = true;
273 cout << g.adjList[w].data <<' ';
274 que.push(w);
275 }
276 }
277 }
278 }
279 }
280 }
281 int main()
282 {
283 ALGraph g,ng;
284 createGraph(g);
285 //buildNALG(g,ng);
286 printGraph(g);
287 DFSTraverse(g);
288
289
290 return 0;
291 } クロスリンク表示法
1 /*
2 * ：
3 * ：2018/4/1
4 */
5
6 /*
7 ：
8 enum < > {< >};
9 enum day {Sun,Mon,Tue,Wed,Thu,Fri,Sat};
10 day d1,d2,d3;
11 d1 = Thu; d2 = Sat; d3 = Tue;
12 ， , 。
13 */
14 #include
15 #include <string>
16 #include
17
18
19 using namespace std;
20 //
21 const int MAXSIZE = 20;
22
23 typedef char vertexType;
24 typedef char infoType;
25
26 typedef struct arcNode
27 {
28 int tailvex,headvex;//
29 struct arcNode *hlink,*tlink;//hlink
30 infoType *info;
31 }arcNode;
32
33 typedef struct
34 {
35 vertexType data;
36 struct arcNode *firstin,*firstout;
37 }VNode;
38
39 typedef struct
40 {
41 int vexnum,arcnum;
42 VNode olist[MAXSIZE];
43 }OLGraph;
44
45 int locate(OLGraph &g,vertexType v)
46 {
47 int i;
48 for (i=0;i)
49 {
50 if ( g.olist[i].data == v )
51 return i;
52 }return -1;
53 }
54 void createDG(OLGraph &g)
55 {
56 cout << " 、 、 " << endl;
57 int hasInfo;
58 cin >> g.vexnum >>g.arcnum >> hasInfo;
59 int i,j,k;
60 cout << " :" << endl;
61 for (i=0;i)
62 {
63 cin >> g.olist[i].data;
64 g.olist[i].firstin = NULL;
65 g.olist[i].firstout = NULL;
66 }
67 cout << " ："<<endl;
68 vertexType v1,v2;
69 arcNode *p;
70 for (k = 0;k)
71 {
72 cin >> v1 >> v2;a
73 i = locate(g,v1);
74 j = locate(g,v2);
75 p->tailvex = i;
76 p->headvex = j;
77 if (hasInfo)
78 cin >> p->info;
79 p->tlink = g.olist[i].firstout;
80 g.olist[i].firstout = p;
81 // ， +
82 p->hlink = g.olist[j].firstin;
83 g.olist[j].firstin = p;
84 }
85 }
86 int main()
87 {
88
89
90
91 return 0;
92 } 隣接多重表表示法
1 /*
2 * ：
3 * ：2018/4/1
4 */
5
6 /*
7 ：
8 enum < > {< >};
9 enum day {Sun,Mon,Tue,Wed,Thu,Fri,Sat};
10 day d1,d2,d3;
11 d1 = Thu; d2 = Sat; d3 = Tue;
12 ， , 。
13 */
14 #include
15 #include <string>
16 #include
17
18
19 using namespace std;
20 //
21 const int MAXSIZE = 20;
22 typedef char vertexType;
23
24 typedef struct eNode
25 {
26 bool mark;
27 int ivex,jvex;
28 struct eNode *ilink,*jlink; // ilink ivex
29 }eNode;
30
31 typedef struct VNode
32 {
33 vertexType data;
34 struct eNode *firstedge;
35 }VNode;
36
37 typedef struct
38 {
39 VNode adjmulist[MAXSIZE];
40 int vexnum,edgenum;
41 }AMLGraph;
42
43 void createAMLGraph(AMLGraph &g)
44 {
45 cout << " 、 、 "<<endl;
46 int hasInfo;
47 cin >> g.vexnum >> g.edgenum >> hasInfo;
48
49 int i,j,k;
50 for (i=0;i)
51 {
52 cin >> g.adjmulist[i].data;
53 g.adjmulist[i].firstedge = NULL;
54 }
55
56 eNode *p;
57 vertexType v1,v2;
58 for (k=0;k)
59 {
60 cin >> v1 >> v2;
61 i = locate(g,v1);
62 j = locate(g,v2);
63 p = (eNode *)malloc(sizeof(eNode));
64 p->ivex = i;
65 p->jvex = j;
66 p->ilink = g.adjmulist[i].firstedge;
67 p->jlink = g.adjmulist[j].firstedge;
68 g.adjmulist[i].firstedge = p;
69 g.adjmulist[j].firstedge = p;
70 }
71 }
72 int main()
73 {
74
75
76
77 return 0;
78 } 図の連結成分と生成ツリーがない
1 /*
2 * 7.4
3 * 1. ， ， ；
4 * ， 。
5 * 2. ， 。
6 * 3. ， 。
7 * 4. - 。
8 * 5. ， - 。
9 */
10 // （ ）
11
12 typedef char Elemtype;
13 typedef struct CSNode
14 {
15 Elemtype data;
16 struct CSNode *child,*sibling;
17 }CSNode,*CSTree;
18
19
20 void DFSTree(ALGraph &g,CSTree &t,int v)
21 {
22 // v
23 visited[v] = true;
24 cout <' ';
25 CSTree p,q;
26 bool isfirst = true;
27 for (int w = firstAdjVex(g,v) ; w>=0 ; w = nextAdjVex(g,v,w))
28 {
29 if (!visited[w])
30 {
31 p = (CSTree)malloc(sizeof(CSNode));
32 p->data = g.adjList[w].data;
33 p->child = NULL;
34 p->sibling = NULL;
35 // P T ，
36 if (isfirst)
37 {
38 t->child = p;
39 isfirst = false;
40 }else
41 {
42 q->sibling = p;
43 }
44 q = p;
45 DFSTree(g,p,w); // p ！
46
47 }
48 }
49 }
50 void DFSForest(ALGraph &g,CSTree &t)
51 {
52 for (int i=0;i)
53 visited[i] = false;
54 CSTree p,q;
55 for (int i=0;i)
56 {
57 if (!visited[i])
58 {
59 p = (CSTree)malloc(sizeof(CSNode));
60 p->data = g.adjList[i].data;
61 p->child = NULL;
62 p->sibling = NULL;
63 if (!t)
64 {
65 t = p; //
66 }else
67 {
68 q->sibling = p; // ，
69 }
70 q = p;
71 DFSTree(g,p,i);// i p
72 }
73 }
74
75
76 }
77 void level(CSTree &t)
78 {
79 queue q;
80 CSTree p;
81 if (t) //
82 {
83 q.push(t); //
84 while (!q.empty())
85 {
86 p = q.front(); //
87 q.pop();
88 cout << p->data << ' ';
89
90 if (p->child)
91 {
92 q.push(p->child);
93 }
94 if (p->sibling)
95 {
96 q.push(p->sibling);
97 }
98 }
99 }
100 } テストデータ
3 13 13 0 ABCDEFGHIJKLM A＿A＿A＿B＿B＿M＿E＿H＿G＿I＿H＿J＿M L
最小生成樹のプリムアルゴリズム
1 struct
2 {
3 vertexType adjvex;
4 vrType lowcost;
5 }closedge[MAXSIZE];
6 // ： U V-U
7
8 int locateVex(MGraph &g,vertexType v)
9 {
10 int k = -1;
11 for (int i = 0 ;i)
12 {
13 if (g.vex[i] == v)
14 k = i;
15 return k;
16 }
17 return k;
18 }
19
20 int minimum(MGraph &g)
21 {
22 int min1 = INFINITY;
23 int k = -1;
24
25 for (int i = 0;i)
26 {
27 if ( closedge[i].lowcost != 0 )
28 {
29 if ( closedge[i].lowcost < min1 )
30 {
31 min1 = closedge[i].lowcost;
32 k = i;
33 }
34 }
35 }
36 return k;
37 }
38
39 void miniSpanTree_prim(MGraph &g,vertexType u)
40 {
41
42 int k = locate(g,u);
43 for (int i=0;i)
44 { // closedge K
45 if (i != k )
46 {
47 closedge[i].adjvex = u;
48 closedge[i].lowcost = g.arc[k][i].adj; // u lowcost INFINITY
49 }
50 }
51 closedge[k].lowcost = 0; // U 0
52
53 for (int i = 1;i// g.vexnum -1 V-U ， U = V
54 {
55 // ， U
56 k = minimum(g); // K
57 cout <<"( " <" , "<" )" << endl; //
58 closedge[k].lowcost = 0; // K U
59 // closedge
60 for (int j = 0;j)
61 {
62 if (g.arc[k][j].adj < closedge[j].lowcost)
63 {
64 closedge[j].adjvex = g.vex[k];
65 closedge[j].lowcost = g.arc[k][j].adj;
66 }
67 }
68
69 }
70 } テストデータ:
3 6 10 ABCDEF A 6 A D 5 A C 1 B 5 B E 3 C 5 C E 6 C 4 D F 2 E 6
トポロジー
1 /*
2 ：
3 1. ： ， ，
4 2. 。 ： ；
5 ： 。
6 ： V ， DFS（V） U V ， 。
7 3. 。 ， 。
8 ：1） 2）
9
10 ：
11 1.
12 2. ： ， ，
13 3.
14 4. ， AOV ，
15 5. AOV ， ： ， 。
16 6. ？ ，
17
18 */
19 int indegree[MAXSIZE];
20 void findInDegree(ALGraph &g)
21 {
22 ALGraph ng;
23 buildNALG(g,ng);
24 arcNode *p;
25 int d = 0;
26 for (int i=0;i)
27 {
28 d = 0;
29 p = ng.adjList[i].firstarc;
30 while (p)
31 {
32 d ++ ;
33 p = p->nextarc;
34 }
35 indegree[i] = d;
36 }
37 // for (int i=0;i38 // cout <
39 }
40 int topoLogicalSort(ALGraph &g)
41 {
42 findInDegree(g); //
43 stack<int> st;
44 // 0
45 for (int i =0;i)
46 {
47 if (!indegree[i])
48 st.push(i);
49 }
50 int i;
51 arcNode *p;
52 int count = 0 ; //
53 while (!st.empty())
54 {
55 i = st.top();
56 st.pop();
57 cout << g.adjList[i].data << ' ';
58 count ++;
59 for (p = g.adjList[i].firstarc ; p ; p=p->nextarc)
60 {
61 // I 1
62 int k = p->adjvex;
63 if (!(--indegree[k]))
64 st.push(k); // 1 0，
65 }
66 }
67 if (count < g.vexnum)
68 return -1;
69 else
70 return 1;
71 } 1 int ve[MAXSIZE]; //
2 int vl[MAXSIZE]; //
3
4 /*
5 1. ve
6 2. T
7 3. S
8 4. G ， T G
9 */
10 int topoLogicalOrder(ALGraph &g,stack<int> &t)
11 {
12 findInDegree(g,indegree);
13 stack<int> s;
14 for (int i = 0;i)
15 {
16 if (!indegree[i])
17 s.push(i);
18 }
19 int count = 0;
20 for (int i=0;i)
21 ve[i] = 0;
22 while (!s.empty())
23 {
24 int j = s.top();
25 s.pop();
26 t.push(j);
27 count ++ ;
28 for (arcNode *p = g->adjList[j].firstarc ; p ; p = p->nextarc)
29 {
30 int k = p->adjvex;
31 if (!(--indegree[k]))
32 s.push(k);
33 if (ve[j]+*(p->info) > ve[k])
34 ve[k] = ve[j] + *(p->info);
35 }
36 }
37 if (count <g.vexnum)
38 return -1;
39 else return 1;
40 }
41
42 //
43 int criticalPath(ALGraph &g)
44 {
45 // ： G
46 stack<int> t;
47 arcNode *p;
48 if (!topoLogicalOrder(g,t))
49 return -1;
50 for (int i=0;i)
51 vl[i] = ve[g.vexnum-1] ; //
52 while (!t.empty())
53 {
54 int j = t.top();
55 t.pop();
56 for (p = g.adjList[j].firstarc ; p ; p= p->nextarc)
57 {
58 int k = p->adjvex;
59 dut = *(p->info);
60 if (vl[k]-dut < vl[j])
61 vl[j] = vl[k] - dut;
62 }
63 }
64 for (j = 0;j)
65 {
66 for (p = g.adjList[i].firstarc ; p;p=p->nextarc)
67 {
68 int k = p->adjvex;
69 dut = *(p->info);
70 int ee = ve[j];
71 el = vl[k] - dut;
72 tag = (ee == el) >
73
74 }
75 }
76
77
78
79 } 最短経路-ディジェストラ
1 /*
2 1. A B ， ， B
3 2. -- --
4 3. v0 v P[v] d[v]
5 4. p[v][w] == true, w v0 - v ， v0 v\
6 5. final[v]
7 */
8 bool p[MAXSIZE][MAXSIZE];
9 int d[MAXSIZE];
10 bool final[MAXSIZE];
11
12 void shortestPath(MGraph &g,int v0)
13 {
14
15 for (int i=0;i)
16 {
17 final[i] = false;
18 d[i] = g.arc[v0][i].adj;
19 for (int j = 0;j)
20 p[i][j] = false;
21
22 if (d[i]!=INFINITY)
23 {
24 p[i][i] = true;
25 p[i][v0] = true;
26 }
27 }
28 final[v0] = true;
29 d[v0] = 0;
30 int v;
31 int min = INFINITY;
32 for (int i=1;i < g.vexnum;i++)
33 { // g.vexnum - 1 ， final
34 min = INFINITY;
35 for (int j=0;j)
36 if (!final[j])
37 if (d[j] < min)
38 {
39 min = d[j];
40 v = j; // v
41 }
42 final[v] = true;
43 //
44 for (int j = 0;j)
45 {
46 if (!final[j] && d[j] > (g.arc[v][j].adj + min)) // INFINIT + INT INFINIT，
47 {
48 d[j] = min + g.arc[v][j].adj;
49 for (int k = 0;k)
50 p[j][k] = p[v][k];
51 p[j][j] = true;
52 }
53 }
54 }
55 }
56
57 void printShortestPath(MGraph &g)
58 {
59 int i;
60 for (i = 1;i)
61 {
62 cout << g.vex[i] << "\t"<<'(';
63 for (int j = 0;j)
64 if (p[i][j])
65 cout << g.vex[j] <<' ' ;
66 cout << ')'<<"\t" ;
67 cout << d[i] <<endl;
68 }
69 } テストデータ
//迪杰特斯1 6 8 0 ABCDEF A 10 A E 30 A F 100 B C 5 C D 50 E D 20 E F 60 D F 10
転載先:https://www.cnblogs.com/twomeng/p/9509532.html