【正文】 berOfVertices(void) const。 SeqListTamp。 int GetNextNeighbor(const int v1, const int v2)。 vertex1, const Tamp。 void DeleteEdge(const Tamp。 SeqListTamp。 SeqListTamp。 BreadthFirstSearch(const Tamp。 eVertex)。 i++) for (int j = 0。 } 圖的輸入格式 頂點數(shù) 頂點序列 邊數(shù) 邊序列 A C B D 0 1 1 0 0 1 0 0 1 1 1 0 0 0 1 0 1 0 0 0 0 1 1 0 0 E 5 A B C D E 5 A B 1 A C 1 B D 1 B E 1 C E 1 GraphcharG。 int weight。 exit(1)。 i++) { f S1。 i nedges。 InsertEdge(S1,S2, weight)。 } template class T int GraphT::GetVertexPos(const Tamp。amp。 pos = 1。 vertex2) { int pos1=GetVertexPos(vertex1), pos2=GetVertexPos(vertex2)。 } template class T SeqListTamp。 L = new SeqListT。 } for (int i = 0。 } return *L。 i graphsize。 return 1。 return 1。 } (vertex)。 template class T void GraphT::InsertEdge(const Tamp。 return。 vertex) { int pos = GetVertexPos(vertex)。 } (vertex)。 row++) for (col = pos + 1。row graphsize。 for (row = pos + 1。 col++) edge[row1][col] = edge[row][col]。 if (pos1 == 1 || pos2 == 1) { cerr DeleteEdge: a vertex is not in the graph. endl。L, const Tamp。 break。 G)。 GraphT::DFS( ) { int *visited=new int[graphsize]。 SeqListT *L=new SeqListT。 } template class T SeqListTamp。 visited[v]=1。 } return *L； } SeqListT L。 beginVertex) { StackT S。 L = new SeqListT。 adjL = GetNeighbors(vertex)。( )) if (!FindVertex(*L,( ))) (( ))。 BF A Q L AB FCH ABF CHE ABFC HED ABFCH EDI ABFCHEDI template class T SeqList T amp。 SeqListIterator T iteradjL(adjL)。 // initialize the queue while (!( )) { vertex = ( )。 for(( )。 } 四、無向圖的連通分量和生成樹 一個圖中互相連通的點的極大子集叫 連通分量 。L) { SeqListIteratorT liter(L)。 } template class T int PathConnect (GraphT amp。 else return 0。 for (( )。 SeqListIteratorT liter(L)。 PrintList(L)。 重復(fù)著一過程，直到取遍所有頂點。 for (( )。 SeqListIteratorT liter(L)。 (( ))。 Prim 普里姆算法 設(shè) G=V,E, 1. 令 U={v0}, T={ }. 2. 對任意 u∈ U, v∈ VU, (u,v)∈ E, 找到權(quán)最小的邊 (u1,v1), 令 U=U∪ {v1}, T=T∪ {(u1,v1)} 3. 重復(fù) 2，直至 U=V. 得到 T就是最小生成樹。 template class T int operator(MiniCostEdgeInfoT a, MiniCostEdgeInfoT b) { return 。 int min=i。amp。 if(pos0||pos=n) {cerrThere are not so many vertices!。 while(!( ) amp。 } return ( )。 T s,w, v=GetVertex(G,0)。i++)//初始化 closeEdge數(shù)組 { w=GetVertex(G,i)。 else closeEdge[i].lowcost=maxint。 //確定 closeEdge中最小值 v=closeEdge[k].adjvex。 closeEdge[k].lowcost=0。 l=(w,v)。 closeEdge[j].adjvex=w。 MiniSpanTreePrim(G)。 T 就是最小生成樹 C B E A F D 6 5 3 6 4 5 2 1 5 6 C B E A F D 6 5 3 6 4 5 2 1 5 6 C B E A F D T={ (A,C), (D,F), (B,E) } T={ (A,C), (D,F), (B,E), (C,F) } T={ (A,C), (D,F), (B,E) (C,F), (B,C) } Kruskal 克魯斯卡爾算法 把所有邊都放進(jìn)優(yōu)先隊列。根結(jié)點的雙親為 1。 C B E A F D G H 問題 ？ 將第二個分支與第三個分支連起來，只要讓結(jié)點D的雙親由 1改為指向 A。 將 C連到 A,即 C點的雙親改為 0，就可以。 int n。 T PTreeDelete(int i)。 int FindRoot(T item)。in。 } template class T int MFSet T ::FindRoot(int i) { if(i0||i=n)return 1。 } template class T int MFSet T ::FindRoot(T item) { int i=Find(item)。 } include include define maxint 32767 template class T struct EdgeInfo { T beginVex, endVex。 template class T void MiniSpanTreeKruskal(Graph T G) { int i, j, l, n=( )。 PQueueEI L。 (item,1)。 for(j=0。 if(l!=MaxIntamp。 =l。 i=()。 count++。 coutendl。 從根 A到 B的路徑就是邊數(shù)最少的路徑，也就是中轉(zhuǎn)次數(shù)最少的路徑。 第一步 取 D[i]為 v0到 vi的邊的權(quán)值 ，無邊時取值 ∞， 取一個最小值 D[j1]=min{D[i], in} D[j1]是 v0到 vj1的最短路徑的長度。,jk } 則 D[jk+1]是 v0到 vjk+1的最短路徑的長 . v3 v0 v5 v2 v4 50 v1 5 30 60 100 10 10 1 2 3 4 5 L D[i] 0 10 (v0,v2) 30 (v0,v4) 100 (v0,v5) 2 D[i] 0 60 (v0,v2,v3) 4 D[i] 50 (v0,v4,v3) 0 90 (v0,v4,v5) 3 D[i] 0 60 (v0,v4,v3,v5) 5 20 迪克斯特拉 Dijkstra算法 L={v0,v2,v4,v3,v5} 時間復(fù)雜性 O(n2) 令 L={vj1 ,vj2 否則設(shè) v0到 vjk的路徑中有一個不在 S中出現(xiàn)的頂點 vp，但是路徑 v0v p的最短路徑，以歸納假設(shè) vp應(yīng)當(dāng)已經(jīng)出現(xiàn)于 L中。 template class T int operator = (const PathInfo T amp。 sVertex, const T amp。 SeqListIterator T adjLiter(adjL)。 = sVertex。 ev = 。 sv = ev。!( )。 = mincost+GetWeight(sv,ev)。 } templateclass T T GetVertex(GraphT G,int pos) { int i, n=( )。 i = 0。 ( )。 u=GetVertex(G,v0)。i++) { final[i]=0。j++)P[i][j]=0。} // p[i][j]=1 iff vertex j is in the path from v0 to i } D[v0]=0。i++) { min=MaxInt。 min=D[j]。jn。amp。 } } } } void main( ) { Graphchar G。 int **P=new (int**[n])[n]。i++) { coutP[i]={ 。j++) cout,P[i][j]。如果不經(jīng)過頂點 k，則最短路徑保持 k1path不變。 Dk[i][j]=min{Dk1[i][j], Dk1[i][k]+ Dk1[k][j]} include define MaxInt 32767 typedef int** DistanceMatrix。 D) { int n=( )。in。j++) { v=GetVertex(G,j)。 for(k=0。P[i][j][j]=1。in。 for(t=