데이터 구조 (엄판) 교과서 코드 재 검토 - 제7 장

116563 단어
데이터 구조 제7 장 그림
네 가지 기본 저장 구조의 인접 행렬 표현법
  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 C A F A L A B B M D E G H G K G I H K J L J M 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 0 ABCDEF A B 6 A D 5 A C 1 B C 5 B E 3 C D 5 C E 6 C F 4 D F 2 E F 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 6080 ABCDEF A C 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

좋은 웹페이지 즐겨찾기