數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)課件：Data Structure --Graph

1、n圖的基本概念圖的基本概念n圖的存儲(chǔ)表示圖的存儲(chǔ)表示n圖的遍歷與連通性圖的遍歷與連通性 n最小生成樹最小生成樹n最短路徑最短路徑 n活動(dòng)網(wǎng)絡(luò)活動(dòng)網(wǎng)絡(luò) (vertex)： 。class Graph public: Graph ( ); void InsertVertex ( const Type & vertex ); void InsertEdge ( const int v1, const int v2, int weight ); void RemoveVertex ( const int v ); void RemoveEdge ( const int v1, const int

2、 v2 ); int IsEmpty ( ); Type GetWeight ( const int v1, const int v2 ); int GetFirstNeighbor ( const int v ); int GetNextNeighbor ( const int v1, const int v2 ); , ),( , , .否則否則如果如果01AEjiEjijiEdge或者 ),( , ,),( .jijiEjiEjijijiWjiEdge=! !0=A對(duì)角線但是否則,或且如果template class Graph private: SeqList VerticesList

3、 (MaxVertices); DistType EdgeMaxVerticesMaxVertices; int numVertex, numEdge; int FindVertex ( SeqList & L; const NameType &vertex ) return L.Find (vertex); int GetVertexPos ( Const NameType &vertex ) return FindVertex (VerticesList, vertex ); public: Graph ( const int sz=MaxNumEdges ); i

4、nt GraphEmpty ( )const return VerticesList.IsEmpty ( ); int GraphFull( ) const return VerticesList.IsFull( ) | numEdges =MaxEdges; int NumberOfVertices ( ) return numVertex; int NumberOfEdges ( ) return numEdges; NameType GetValue ( const int i ) return i = 0 & i VerticesList.length-1 ? Vertices

5、List.Elemi : NULL; int GetWeight ( const int v1, const int v2 ); int GetFirstNeighbor ( const int v ); int GetNextNeighbor ( const int v1, const int v2 ); void InsertVertex ( const NameType & vertex ); void InsertEdge ( const int v1, const int v2, DistType weight ); void RemoveVertex ( const int

6、 v ); void RemoveEdge ( const int v1, const int v2 );template Graph:Graph(const int sz)/構(gòu)造函數(shù)構(gòu)造函數(shù) for ( int i = 0; i sz; i+ ) for ( int j = 0; j sz; j+ ) Edgeij = 0; numVertex=numEdges = 0;template DistType Graph:GetWeight( const int v1, const int v2 ) /給出以頂點(diǎn)給出以頂點(diǎn) v1 和和 v2 為兩端點(diǎn)的邊上的權(quán)值為兩端點(diǎn)的邊上的權(quán)值 if ( v

7、1 != -1 & v2 != -1 ) return Edgev1v2; else return 0;template int Graph:GetFirstNeighbor ( const int v ) /給出頂點(diǎn)位置為給出頂點(diǎn)位置為 v 的第一個(gè)鄰接頂點(diǎn)的位置的第一個(gè)鄰接頂點(diǎn)的位置 if ( v != -1 ) for ( int col = 0; col 0 ) return col; return -1; template int Graph:GetNextNeighbor ( const int v1, const int v2 ) /給出頂點(diǎn)給出頂點(diǎn)v1的某鄰接頂點(diǎn)的某鄰

8、接頂點(diǎn)v2的下一個(gè)鄰接頂點(diǎn)的下一個(gè)鄰接頂點(diǎn) if ( v1 != -1 & v2 != -1 ) for ( int col = v2+1; col 0 ) return col; return -1; template class Graph;template struct Edge int dest; DistType cost; Edge *link; Edge ( ) Edge ( int D, DistType C ) : dest (D), cost (C), link (NULL) int operator != ( const Edge &E ) const r

9、eturn dest != E.dest; template struct Vertex NameType data; Edge *adj;template class Graph friend class vertex ;friend class Edge;private: Vertex *NodeTable; int NumVertices; int MaxVertices; int NumEdges; int GetVertexPos ( const Type & vertex );public: Graph ( int sz ); Graph ( ); int GraphEmp

10、ty ( ) const return NumVertices = 0; int GraphFull ( ) const return NumVertices = MaxVertices | NumEdges =MaxEdges; NameType GetValue ( const int i ) return i = 0 & i NumVertices ? NodeTablei.data : NULL; int NumberOfVertices ( ) return NumVertices; int NumberOfEdges ( ) return NumEdges; void In

11、sertVertex ( const NameType & vertex ); void RemoveVertex ( const int v ); void InsertEdge ( const int v1, const int v2, const DistType weight ); void RemoveEdge ( const int v1, const int v2 ); DistType GetWeight ( const int v1, const int v2 ); int GetFirstNeighbor ( const int v ); int GetNextNe

12、ighbor ( const int v1, const int v2 );template Graph:Graph ( const int sz = DefaultSize ) : NumVertices (0), MaxVertices (sz), NumEdges (0) int n, e, k, j; NameType name, tail, head; DistType weight; NodeTable = /創(chuàng)建頂點(diǎn)表創(chuàng)建頂點(diǎn)表 new VertexMaxVertices; cin n; /輸入頂點(diǎn)個(gè)數(shù)輸入頂點(diǎn)個(gè)數(shù) for ( int i = 0; i name; InserVe

13、rtex ( name ); cin e; /輸入邊條數(shù)輸入邊條數(shù) for ( i =0; i tail head weight; k = GetVertexPos ( tail ); j = GetVertexPos ( head ); InsertEdge ( k, j, weight ); template Graph:Graph ( ) for ( int i = 0; i NumVertices; i+ ) Edge *p = NodeTablei.adj; while ( p != NULL ) /逐條邊釋放逐條邊釋放 NodeTablei.adj = plink; delete

14、p; p = NodeTablei.adj; delete NodeTable; /釋放頂點(diǎn)表釋放頂點(diǎn)表template int Graph:GetVertexPos ( Const NameType & vertex ) /根據(jù)頂點(diǎn)名根據(jù)頂點(diǎn)名vertex查找該頂點(diǎn)在鄰接表中的位置查找該頂點(diǎn)在鄰接表中的位置 for ( int i =0; i NumVertices; i+ ) if ( NodeTablei.data = vertex ) return i; return -1;template int Graph:GetFirstNeighbor ( const int v )

15、/查找頂點(diǎn)查找頂點(diǎn) v 的第一個(gè)鄰接頂點(diǎn)在鄰接表中的位置的第一個(gè)鄰接頂點(diǎn)在鄰接表中的位置 if ( v != -1 ) /若頂點(diǎn)存在若頂點(diǎn)存在 Edge *p = NodeTablev.adj; if ( p != NULL ) return pdest; return -1; /若頂點(diǎn)不存在若頂點(diǎn)不存在template int Graph: GetNextNeighbor ( const int v1, const int v2 ) /查找頂點(diǎn)查找頂點(diǎn) v1 在鄰接頂點(diǎn)在鄰接頂點(diǎn) v2 后下一個(gè)鄰接頂點(diǎn)后下一個(gè)鄰接頂點(diǎn) if ( v1 != -1 ) Edge *p = NodeTablev

16、1.adj; while ( p != NULL ) if ( pdest = v2 & plink != NULL ) return plinkdest; /返回下一個(gè)鄰接頂點(diǎn)在鄰接表中的位置返回下一個(gè)鄰接頂點(diǎn)在鄰接表中的位置 else p = plink; return -1; /沒有查到下一個(gè)鄰接頂點(diǎn)返回沒有查到下一個(gè)鄰接頂點(diǎn)返回- -1template DistType Graph:GetWeight ( const int v1, const int v2) /取兩端點(diǎn)為取兩端點(diǎn)為 v1 和和 v2 的邊上的權(quán)值的邊上的權(quán)值 if ( v1 != -1 & v2 !=

17、 -1 ) Edge *p = NodeTablev1.adj; while ( p != NULL ) if ( pdest = v2 ) return pcost; else p = plink; return 0; mark vertex1 vertex2 path1 path2 data Firstout mark vertex1 vertex2 path1 path2 data Firstin Firstoutvoid Graph:DFS ( ) visited = new int n; /創(chuàng)建數(shù)組創(chuàng)建數(shù)組 visited for ( int i = 0; i n; i+ ) vis

18、ited i = 0; /訪問標(biāo)記數(shù)組訪問標(biāo)記數(shù)組 visited 初始化初始化 for(int i=0; in;i+)if(visitedi=0) DFS(i,visited); delete visited; /釋放釋放 visited viod Graph:DFS ( const int v, int visited ) cout GetValue (v) ; /訪問頂點(diǎn)訪問頂點(diǎn) v visitedv = 1; /頂點(diǎn)頂點(diǎn) v 作訪問標(biāo)記作訪問標(biāo)記 int w = GetFirstNeighbor (v); /取取 v 的第一個(gè)鄰接頂點(diǎn)的第一個(gè)鄰接頂點(diǎn) w while ( w != -1

19、 ) /若鄰接頂點(diǎn)若鄰接頂點(diǎn) w 存在存在 if ( !visitedw ) DFS ( w, visited ); /若若頂點(diǎn)頂點(diǎn) w 未訪問過未訪問過, , 遞歸訪問頂點(diǎn)遞歸訪問頂點(diǎn) w w = GetNextNeighbor ( v, w ); /取頂點(diǎn)取頂點(diǎn) v 的排在的排在 w 后面的下一個(gè)鄰接頂點(diǎn)后面的下一個(gè)鄰接頂點(diǎn) void Graph : BFS ( const int v ) visited = new intNumCertices; /創(chuàng)建創(chuàng)建 visited for ( int i = 0; i NumVertices; i+ ) visitedi = 0; /visit

20、ed 初始化初始化 cout GetValue (v) ; visitedv = 1; Queue q; q.EnQueue (v); /訪問訪問 v, 進(jìn)隊(duì)列進(jìn)隊(duì)列 while ( !q.IsEmpty ( ) ) /隊(duì)空搜索結(jié)束隊(duì)空搜索結(jié)束 v = q.DeQueue ( ); /不空不空, 出隊(duì)列出隊(duì)列 int w = GetFirstNeighbor (v); /取頂點(diǎn)取頂點(diǎn) v 的的第一個(gè)鄰接頂點(diǎn)第一個(gè)鄰接頂點(diǎn) w while ( w != -1 ) /若鄰接頂點(diǎn)若鄰接頂點(diǎn) w 存在存在 if ( !visitedw ) /若該鄰接頂點(diǎn)未訪問過若該鄰接頂點(diǎn)未訪問過 cout GetV

21、alue (w) ; /訪問訪問 visitedw = 1; q.EnQueue (w); /進(jìn)隊(duì)進(jìn)隊(duì) w = GetNextNeighbor (v, w); /取頂點(diǎn)取頂點(diǎn) v 的排在的排在 w 后面的下一鄰接頂點(diǎn)后面的下一鄰接頂點(diǎn) /重復(fù)檢測重復(fù)檢測 v 的所有鄰接頂點(diǎn)的所有鄰接頂點(diǎn) delete visited; void Graph:Components ( ) visited = new intNumCertices; /創(chuàng)建創(chuàng)建visited for ( int i = 0; i NumVertices; i+ ) visitedi = 0; /visited 初始化初始化 for

22、 ( i = 0; i NumVertices; i+ ) if ( !visitedi ) /檢測所有頂點(diǎn)是否訪問過檢測所有頂點(diǎn)是否訪問過 DFS ( i, visited ); /從未訪問的頂點(diǎn)出發(fā)訪問從未訪問的頂點(diǎn)出發(fā)訪問 OutputNewComponent ( ); /輸出一個(gè)連通分量輸出一個(gè)連通分量 delete visited; /釋放釋放visitedlowu = min dfnu, min loww | w 是是 u 的一個(gè)子女的一個(gè)子女 , min dfnx | (u, x) 是一條回邊是一條回邊 計(jì)算計(jì)算dfn與與low的算法的算法 (1)void Graph:DfnLo

23、w ( const int x ) /公有函數(shù)：從頂點(diǎn)公有函數(shù)：從頂點(diǎn)x開始深度優(yōu)先搜索開始深度優(yōu)先搜索 int num = 1; / num是訪問計(jì)數(shù)器是訪問計(jì)數(shù)器 dfn = new intNumVertices; low = new intNumVertices; /dfn是深度優(yōu)先數(shù)是深度優(yōu)先數(shù), low是最小祖先訪問順序號(hào)是最小祖先訪問順序號(hào) for ( int i = 0; i NumVertices; i+ ) dfni = lowi = 0; /給予訪問計(jì)數(shù)器給予訪問計(jì)數(shù)器num及及dfnu, lowu初值初值 DfnLow ( x, -1 ); /從根從根x開始開始 dele

24、te dfn; delete low;計(jì)算計(jì)算dfn與與low的算法的算法 (2)void Graph:DfnLow ( const int u, const int v ) /私有函數(shù)：從頂點(diǎn)私有函數(shù)：從頂點(diǎn) u 開始深度優(yōu)先搜索計(jì)算開始深度優(yōu)先搜索計(jì)算dfn/ 和和low。在產(chǎn)生的生成樹中。在產(chǎn)生的生成樹中 v 是是 u 的雙親。的雙親。 dfnu = lowu = num+; int w = GetFirstNeighbor (u); while ( w != -1 ) /對(duì)對(duì)u所有鄰接頂點(diǎn)所有鄰接頂點(diǎn)w循環(huán)循環(huán) if ( dfnw = 0 ) /未訪問過未訪問過, w是是u的孩子的孩子

25、 DfnLow ( w, u ); /從從w遞歸深度優(yōu)先搜索遞歸深度優(yōu)先搜索 lowu = min2 ( lowu, loww ); /子女子女w的的loww先求出先求出, 再求再求lowu else if ( w != v ) /w訪問過且訪問過且w不是不是v，是回邊是回邊 lowu = min2 ( lowu, dfnw ); /根據(jù)回邊另一頂點(diǎn)根據(jù)回邊另一頂點(diǎn)w調(diào)整調(diào)整lowu w = GetNextNeighbor (u, w); /找頂點(diǎn)找頂點(diǎn)u在在w后面后面的下一個(gè)鄰接頂點(diǎn)的下一個(gè)鄰接頂點(diǎn) void Graph:Biconnected ( ) /公有函數(shù)：從頂點(diǎn)公有函數(shù)：從頂點(diǎn)0開

26、始深度優(yōu)先搜索開始深度優(yōu)先搜索 int num = 1; /訪問計(jì)數(shù)器訪問計(jì)數(shù)器num dfn = new intNumVertices; /dfn是深度優(yōu)先數(shù)是深度優(yōu)先數(shù) low = new intNumVertices; /low是最小祖先號(hào)是最小祖先號(hào) for ( int i = 0; i NumVertices; i+ ) dfni = lowi = 0; DfnLow ( 0, -1 ); /從頂點(diǎn)從頂點(diǎn) 0 開始開始 delete dfn; delete low;void Graph:Biconnected ( const int u, const int v ) /私有函數(shù)：計(jì)算

27、私有函數(shù)：計(jì)算dfn與與low, 根據(jù)其重連通分量輸根據(jù)其重連通分量輸/出出Graph的邊。在產(chǎn)生的生成樹中的邊。在產(chǎn)生的生成樹中, v 是是 u 的雙親的雙親/結(jié)點(diǎn)結(jié)點(diǎn), S 是一個(gè)初始為空的棧，應(yīng)聲明為圖的數(shù)是一個(gè)初始為空的棧，應(yīng)聲明為圖的數(shù)/據(jù)成員。據(jù)成員。 int x, y, w; dfnu = lowu = num+; w = GetFirstNeighbor (u); /找頂點(diǎn)找頂點(diǎn)u的第一個(gè)鄰接頂點(diǎn)的第一個(gè)鄰接頂點(diǎn)w while ( w != - 1 ) if ( v != w & dfnw = dfnu ) /無回邊無回邊, 原來的重連通分量結(jié)束原來的重連通分量結(jié)束 c

28、out “新重連通分量新重連通分量: ” end1; do (x, y) = S.Pop ( ); cout x , y endl; while ( (x, y) 與與 (u, w) 不是同一條邊不是同一條邊 ); /輸出該重連通分量的各邊輸出該重連通分量的各邊 else if ( w != v ) /有回邊有回邊, ,計(jì)算計(jì)算 lowu = min2 ( lowu, dfnw ); /根據(jù)回邊另一頂點(diǎn)根據(jù)回邊另一頂點(diǎn)w調(diào)整調(diào)整lowu w = GetNextNeighbor (u, w); /找頂點(diǎn)找頂點(diǎn)u的鄰接頂點(diǎn)的鄰接頂點(diǎn)w的下一個(gè)鄰接頂點(diǎn)的下一個(gè)鄰接頂點(diǎn) 471592(a) (b) (

29、c) (d)n最小生成樹最小生成樹:圖圖G中中 最小權(quán)值最小權(quán)值(成本成本)的生成的生成樹。樹。通訊網(wǎng)絡(luò) 交通網(wǎng)絡(luò)n最小生成樹算法最小生成樹算法:貪婪算法（貪婪算法（greedy algorithms）u度量標(biāo)準(zhǔn)：選擇使得迄今為止所記入度量標(biāo)準(zhǔn)：選擇使得迄今為止所記入的那些邊的成本的和數(shù)有的那些邊的成本的和數(shù)有最小增量最小增量的的那條邊。那條邊。（1）Prims Algorithm（2）Kruskals Algorithmconst int MAXINT = 機(jī)器可表示的機(jī)器可表示的, , 問題中不可能出現(xiàn)的大數(shù)問題中不可能出現(xiàn)的大數(shù)class MinSpanTree;class MSTEdg

30、eNode /生成樹邊結(jié)點(diǎn)類定義生成樹邊結(jié)點(diǎn)類定義friend class MinSpanTree;private: int tail, head;/生成樹各邊的兩頂點(diǎn)生成樹各邊的兩頂點(diǎn) int cost; /生成樹各邊的代價(jià)生成樹各邊的代價(jià);class MinSpanTree /生成樹的類定義生成樹的類定義public: MinSpanTree ( int sz = MaxEdges -1 ) : MaxSize (sz), n (0) edgevalue = new MSTEdgeNodeMaxSize; int Insert ( MSTEdgeNode &item ); /將將i

31、tem加到最小生成樹中加到最小生成樹中protected: MSTEdgeNode *edgevalue;/邊值數(shù)組邊值數(shù)組 int MaxSize, n; /最大邊數(shù)最大邊數(shù),當(dāng)前邊數(shù)當(dāng)前邊數(shù);繼續(xù)重復(fù)得：繼續(xù)重復(fù)得：頂點(diǎn)頂點(diǎn)5加入生成樹頂點(diǎn)集合：加入生成樹頂點(diǎn)集合：v = 5v = 4(0, 5, 10), (5, 4, 25), (4, 3, 22),(3, 2, 12), (2, 1, 16), (1, 6, 14)void Graph:Prim ( MinSpanTree &T ) int NumVertices = VerticesList.last; /圖中頂點(diǎn)數(shù)圖中頂點(diǎn)

32、數(shù) lowcost = new intNumVertices; nearvex = new intNumVertices; for ( int i = 1; i NumVertices; i+ ) lowcosti = Edge0i; /頂點(diǎn)頂點(diǎn)0到各邊的代價(jià)到各邊的代價(jià) nearvexi = 0; /及最短帶權(quán)路徑及最短帶權(quán)路徑 nearvex0 = -1; /頂點(diǎn)頂點(diǎn)0加到生成樹頂點(diǎn)集合加到生成樹頂點(diǎn)集合 MSTEdgeNode e; /最小生成樹結(jié)點(diǎn)輔助單元最小生成樹結(jié)點(diǎn)輔助單元 for ( i = 1; i NumVertices; i+ ) /循環(huán)循環(huán)n-1次次, 加入加入n-1條邊

33、條邊 int min = MAXINT; int v = 0; for ( int j = 0; j NumVertices; j+ ) if ( nearvexj != -1 & lowcostj min ) v = j; min = lowcostj; /求生成樹外頂點(diǎn)到生成樹內(nèi)頂點(diǎn)具有最小求生成樹外頂點(diǎn)到生成樹內(nèi)頂點(diǎn)具有最小 /權(quán)值的邊權(quán)值的邊, v是是當(dāng)前具最小權(quán)值的邊的位置當(dāng)前具最小權(quán)值的邊的位置 if ( v ) /v=0表示再也找不到要求的頂點(diǎn)了表示再也找不到要求的頂點(diǎn)了 e.tail = nearvexv; e.head = v; e.cost = lowcostv;

34、T.Insert (e); /選出的邊加入生成樹選出的邊加入生成樹 nearvexv = -1; /作該邊已加入生成樹標(biāo)記作該邊已加入生成樹標(biāo)記 for ( j = 1; j NumVertices; j+ ) if ( nearvexj != -1 & /j不在生成樹中不在生成樹中 Edgevj lowcostj ) /需要修改需要修改 lowcostj = Edgevj; nearvexj = v; tail head cost 邊的兩個(gè)頂點(diǎn)位置邊的兩個(gè)頂點(diǎn)位置 邊的權(quán)值邊的權(quán)值void Graph:Kruskal ( MinSpanTree &T ) MSTEdgeNod

35、e e; /邊結(jié)點(diǎn)輔助單元邊結(jié)點(diǎn)輔助單元 MinHeap H(CurrentEdges); int NumVertices = VerticesList.numVex;/頂點(diǎn)個(gè)數(shù)頂點(diǎn)個(gè)數(shù) UFSets F (NumVertices); /并查集并查集F 并初始化并初始化 for ( int u = 0; u NumVertices; u+ ) /鄰接矩陣鄰接矩陣 for ( int v = u+1; v NumVertices; v+ ) if ( Edgeuv != MAXINT ) /檢出所有邊檢出所有邊 e.tail = u; e.head = v; e.cost = w; H.Inse

36、rt (e); /插入最小堆插入最小堆 int count = 1; /最小生成樹加入邊數(shù)的計(jì)數(shù)最小生成樹加入邊數(shù)的計(jì)數(shù) while ( count NumVertices ) / e = H.RemoveMin ( ); /從堆中退出一條邊從堆中退出一條邊 u = F.Find ( e.tail ); /檢測兩端點(diǎn)的根檢測兩端點(diǎn)的根v = F.Find ( e.head );if ( u != v ) /根不同根不同, 不在同一連通分量上不在同一連通分量上 F.Union ( u, v ); /合并合并 T.Insert ( e ); /該邊存入最小生成樹該邊存入最小生成樹 T 中中 cou

37、nt+; 源 點(diǎn) 終 點(diǎn) 最 短 路 徑路 徑 長 度 v0 v1(v0, v1)10 v2 (v0, v1, v2) (v0, v3, v2) 60 50 v3(v0, v3)30 v4(v0, v4)(v0, v3, v4) (v0, v3, v2, v4)100 90 60const int NumVertices = 6; /圖中最大頂點(diǎn)個(gè)數(shù)圖中最大頂點(diǎn)個(gè)數(shù)class Graph /圖的類定義圖的類定義 private: int EdgeNumVerticesNumVertices; /鄰接矩陣鄰接矩陣 int distNumVertices; /最短路徑長度數(shù)組最短路徑長度數(shù)組 in

38、t pathNumVertices; /最短路徑數(shù)組最短路徑數(shù)組 int SNumVertices; /最短路徑頂點(diǎn)集最短路徑頂點(diǎn)集public: void ShortestPath ( const int, const int ); int choose ( const int ); void Graph:ShortestPath ( const int n, const int v )/Graph是一個(gè)具有是一個(gè)具有n個(gè)頂點(diǎn)的帶權(quán)有向圖個(gè)頂點(diǎn)的帶權(quán)有向圖, 各邊上各邊上/的權(quán)值由的權(quán)值由Edgeij給出。本算法建立起一個(gè)數(shù)給出。本算法建立起一個(gè)數(shù)/組組: distj, 0 j n, 是當(dāng)前

39、求到的從頂點(diǎn)是當(dāng)前求到的從頂點(diǎn)v到頂點(diǎn)到頂點(diǎn)/j的最短路徑長度的最短路徑長度, 同時(shí)用數(shù)組同時(shí)用數(shù)組pathj, 0 j n, 存存/放求到的最短路徑。放求到的最短路徑。 for ( int i = 0; i n; i+) disti = Edgevi; /dist數(shù)組初始化數(shù)組初始化 Si = 0; if ( i != v & disti MAXINT ) pathi = v; else pathi = -1; /path數(shù)組初始化數(shù)組初始化 Sv = 1; distv = 0;/頂點(diǎn)頂點(diǎn)v加入頂點(diǎn)集合加入頂點(diǎn)集合 /選擇當(dāng)前不在集合選擇當(dāng)前不在集合S中具有最短路徑的頂點(diǎn)中具有最短路

40、徑的頂點(diǎn)u for ( i = 0; i n-1; i+ ) int min = MAXINT; int u = v; for ( int j = 0; j n; j+ ) if ( !Sj & distj min ) u = j; min = distj; Su = 1; /將頂點(diǎn)將頂點(diǎn)u加入集合加入集合S for ( int w = 0; w n; w+ ) /修改修改 if ( !Sw & Edgeuw MAXINT & distu + Edgeuw distw ) distw = distu + Edgeuw; pathw = u; 選 取 頂點(diǎn)1 頂點(diǎn)2 頂點(diǎn)

41、3 頂點(diǎn)4 終 點(diǎn) S1 d1 p1 S2 d2 p2 S3 d3 p3 S4 d4 p4 0 0 10 0 0 0 0 30 0 0 100 0 1 1 10 0 0 60 1 0 30 0 0 100 0 3 1 10 0 0 50 3 1 30 0 0 90 3 2 1 10 0 1 50 3 1 30 0 0 60 2 4 1 10 0 1 50 3 1 30 0 1 60 2 如何從表中讀取源點(diǎn)如何從表中讀取源點(diǎn)0到終到終點(diǎn)點(diǎn)v的最短路徑？舉頂點(diǎn)的最短路徑？舉頂點(diǎn)4為例為例 path4 = 2 path2 = 3 path3 = 0，反過來排列，反過來排列，得到路徑得到路徑0, 3,

42、 2, 4，這就是源，這就是源點(diǎn)點(diǎn)0到終點(diǎn)到終點(diǎn)4的最短路徑。的最短路徑。Dijkstras AlgorithmnExample:nStep 0Dijkstras AlgorithmnExample:nStep 1Dijkstras AlgorithmnExample:nStep 2Dijkstras AlgorithmnExample:nStep 3Dijkstras AlgorithmnExample:nStep 4Dijkstras AlgorithmnExample:nStep 5Dijkstras AlgorithmnExample:nStep 6void Graph:AllLeng

43、ths ( const int n ) for ( int i = 0; i n; i+ ) /矩陣矩陣a與與path初始化初始化 for ( int j = 0; j n; j+ ) aij = Edgeij; if ( i j & aij MAXINT ) pathij = i; / i 到到 j 有路徑有路徑 else pathij = 0; / i 到到 j 無路徑無路徑 for ( int k = 0; k n; k+ ) /產(chǎn)生產(chǎn)生a(k)及及path(k) for ( i = 0; i n; i+ ) for ( j = 0; j n; j+ ) if ( aik + a

44、kj aij ) aij = aik + akj; pathij = pathkj; /縮短路徑長度縮短路徑長度, 繞過繞過 k 到到 j A(-1) A(0) A(1) A(2) A(3) 0 1 2 3 0 1 2 3 0 1 2 3 0 1 2 3 0 1 2 3 0 0 1 4 0 1 4 0 1 10 3 0 1 10 3 0 1 9 3 1 0 9 2 0 9 2 0 9 2 12 0 9 2 11 0 8 2 2 3 5 0 8 3 4 0 7 3 4 0 6 3 4 0 6 3 4 0 6 3 6 0 6 0 6 0 9 10 6 0 9 10 6 0 Path(-1) Pat

45、h(0) Path(1) Path(2) Path(3) 0 1 2 3 0 1 2 3 0 1 2 3 0 1 2 3 0 1 2 3 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 1 1 0 0 3 1 1 0 0 1 1 0 0 1 1 0 0 1 1 2 0 1 1 2 0 3 1 2 2 2 0 2 2 0 0 0 2 0 0 1 2 0 0 1 2 0 0 1 3 0 0 3 0 0 0 3 0 0 0 3 0 2 0 3 0 2 0 3 0學(xué)生課程學(xué)習(xí)工程圖學(xué)生課程學(xué)習(xí)工程圖 Indegreeclass Graph /friend class Vertex;friend class Edge;private: Vertex *NodeTable; int * n; Stack T; public: Graph ( const int vertices = 0 ) : n ( vertices ) NodeTable = new vertexn; Indegree = new intn; ; Bool TopologicalOrder ( ); Bool CriticalPath( ); Bool Graph:TopologicalSort ( ) Stack S; for ( int i = 0; i n; i+ ) /入