【正文】 ge[pos1][pos2]。 if (pos1 == 1 || pos2 == 1) { cerr GetWeight: a vertex is not in the graph. endl。 vertex1, const Tamp。 } return pos。 } if (( )) { cerr GetVertex: the vertex is not in the graph. endl。 ( ) != vertex) { pos++。 while(!( ) amp。 vertex) { SeqListIteratorT liter(vertexList)。 } template class T int GraphT::GraphEmpty(void) const { return graphsize == 0。 } ( )。 f weight。 i++) { f S1。 for (i = 0。 InsertVertex(S1)。 i nvertices。 } f nvertices。 if(!f){ cerr Cannot open filename endl。 ifstream f。 T S1, S2。 (“”)。 graphsize = 0。 j MaxGraphSize。 i MaxGraphSize。 }。 sVertex, const Tamp。 beginVertex)。 SeqListTamp。 DepthFirstSearch(const Tamp。 DFS(const int v, int *visited)。 DFS( )。 // utility methods void ReadGraph(char *filename)。 vertex1, const Tamp。 vertex)。 vertex2, int weight)。 void InsertEdge(const Tamp。 // graph modification methods void InsertVertex(const Tamp。 int GetFirstNeighbor(const int v)。 GetNeighbors(const Tamp。 vertex2)。 int GetWeight(const Tamp。 int GraphFull(void) const。 A B public: ALGraph(void)。 int GetVertexPos(const Tamp。L, const Tamp。 int vexNum, edgeNum。 EdgeT *firstedge。} }。 EdgeT *next。 template class T struct Edge //邊的類 第一個頂點是隱式的 { int adjvex。 }。 eVertex)。 int MinimumPath(const Tamp。 BreadthFirstSearch(const Tamp。 beginVertex)。 SeqListTamp。 SeqListTamp。 SeqListTamp。 vertex2)。 void DeleteEdge(const Tamp。 void DeleteVertex(const Tamp。 vertex1, const Tamp。 vertex)。 int GetNextNeighbor(const int v1, const int v2)。 vertex)。 SeqListTamp。 vertex1, const Tamp。 int NumberOfVertices(void) const。 int GraphEmpty(void) const。 vertex)。 vertex)。 int FindVertex(SeqListT amp。 int edge [MaxGraphSize][MaxGraphSize]。 template class T class VertexIterator。 二、圖的存儲結(jié)構(gòu) 用矩陣表示圖的頂點之間的相鄰關(guān)系。 有向樹 有向圖連通圖恰有一個頂點的入度為 0， 其余頂點的入度都是 1。 連通圖的 生成樹 含有所有頂點的極小 連通圖 n個頂點盡可能少邊的連通圖有 n1條邊。 連通分量 一個圖的極大連通子圖。 稀疏圖 |E|nlog n 稠密圖 |E|nlog n 帶權(quán)邊 具有邊長的邊 有權(quán)圖 圖的所有邊都是帶權(quán)邊。 v5 v1 v3 v2 v4 v5 v1 v3 v2 v4 弱連通 強連通 強連通分量：彼此強連通的頂點的子集 A C B D I E G F H ABC D EFG H I 完全圖 任意兩點間都有邊相關(guān)聯(lián)的圖。v j, 以 vi為起點 vj為終點的頂點序列。 圖的基本概念 路徑 vi ID(vi): 入度 ，以 vi為終點的邊的數(shù)目。,vn} 頂點 集 E={ (vi, vj) | vi,vj∈ V, vi≠vj} 邊 集 無向圖 E={vi, vj|vi , vj∈ V}有向邊 集 有向圖 有向邊 vi, vj ， vi起點 弧尾， vj終點 弧頭 TD(vi): 一個頂點的 度 ,以 vi為端點的邊的數(shù)目。 簡單圖 沒有自身環(huán)，兩點間至多一條邊 v5 v1 v1 v3 v2 v3 v4 v4 v2 無向圖 有向圖 圖的基本概念 G=V, E V={v1,v2,? 圖 ? 圖的存儲表示 ? 圖的遍歷 ? 無向圖的連通分量和生成樹 ? 最短路徑 ? 拓撲排序 一、圖 圖 應用最廣泛的數(shù)據(jù)結(jié)構(gòu)。 不同于樹的另一種 非線性結(jié)構(gòu) 每個頂點可以與 多個 其他頂點相關(guān)聯(lián)，各頂 點之間的關(guān)系是 任意 的。 OD(vi): 出度 , 以 vi為起點的邊的數(shù)目。 TD(vi)= OD(vi)+ ID(vi) OD=ID, TD=2|E|， |E| =1/2*TD TD OD ID 為整個圖的總度 ,出度 ,入度數(shù)。 路徑的長 路徑上邊的數(shù)目， 簡單路徑 頂點都不重復的路徑， 回路 環(huán) 首尾相接的路徑， 簡單回路 除第一個和最后一個頂點以外都不重 復的路徑， vivj連通 有路徑 viv j， 連通圖 任意兩點都連通， 有向圖 vivj強連通 vivj連通 vjvi也連通， 強連通圖 任意兩點都強連通。 無向完全圖 共有邊 1/2(n*(n1)) 條 , 有向完全圖 共有邊 n(n1) 條。 網(wǎng)絡(luò) 有權(quán)圖 子圖 G=(V, E), G?=(V?, E?) 如果 V? V, E? E , 就稱 G?是 G的子圖。 強連通分量 一個圖的極大強連通子圖。 非連通圖的 生成森林： 所有 k個連通分支的生成樹組成生成森林，共有 nk條邊。 有向圖的 生成森林： 有向圖的一個子圖，含有所有頂點，構(gòu)成若干互不相交的有向樹，叫做生成森林。 A[i,j]=1 (vi,vj)∈ E =0 . v5 v1 v3 v2 v4 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 無向圖的鄰接矩陣是對稱矩陣 TD(vi)=ΣA[i,j] i行數(shù)字的和等于 vi的度 v5 v1 v3 v2 v4 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 j=1 n |E|=1/2 ΣΣA[i,j] 全部數(shù)字的和等于邊數(shù) *2 i=1 n j=1 n 有向圖的鄰接矩陣 A[i,j]=1 vi,vj∈ E =0 . v1 v3 v4 v2 0 1 1 0 0 0 0 1 1 0 0 0 1 0 0 0 OD(vi)=ΣA[i,j] i行數(shù)字的和等于 vi的出度 j=1 n |E|= ΣΣA[i,j] 全部數(shù)字的和等于邊數(shù) i=1 n j=1 n 網(wǎng)的鄰接矩陣 A[i,j]=wi (vi,vj)∈ E 權(quán)為 wi =∞ . v5 v1 v6 v2 v4 v3 ∞ 5 ∞ 7 ∞ ∞ ∞ ∞ 4 ∞ ∞ ∞ 8 ∞ ∞ ∞ ∞ 9 ∞ ∞ 5 ∞ ∞ 6 ∞ ∞ ∞ 5 ∞ ∞ 3 ∞ ∞ ∞ 1 ∞ 5 4 8 9 5 7 3 1 5 6 ifndef GRAPH_CLASS define GRAPH_CLASS include include include include include include const int MaxGraphSize = 25。 template class T class Graph { SeqListT vertexList。 int graphsize。L, const Tamp。 int GetVertexPos(const Tamp。 public: Graph(void)。 int GraphFull(void) const。 int GetWeight(const Tamp。 vertex2)。 GetNeighbors(const Tamp。 int GetFirstNeighbor(const int v)。 // graph modification methods void InsertVertex(const Tamp。 void InsertEdge(const Tamp。 vertex2, int weight)。 vertex)。 vertex1, const Tamp。 // utility methods void ReadGraph(char *filename)。 DFS( )。 DFS(const int v, int *visited)。 DepthFirstSearch(const Tamp。 SeqListTamp。 beginVertex)。 sVertex, const Tamp。 // iterator used to scan the vertices friend class VertexI