【正文】 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 //邊的類 第一個(gè)頂點(diǎn)是隱式的 { 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。 二、圖的存儲(chǔ)結(jié)構(gòu) 用矩陣表示圖的頂點(diǎn)之間的相鄰關(guān)系。 有向樹 有向圖連通圖恰有一個(gè)頂點(diǎn)的入度為 0， 其余頂點(diǎn)的入度都是 1。 連通圖的 生成樹 含有所有頂點(diǎn)的極小 連通圖 n個(gè)頂點(diǎn)盡可能少邊的連通圖有 n1條邊。 連通分量 一個(gè)圖的極大連通子圖。 稀疏圖 |E|nlog n 稠密圖 |E|nlog n 帶權(quán)邊 具有邊長的邊 有權(quán)圖 圖的所有邊都是帶權(quán)邊。 v5 v1 v3 v2 v4 v5 v1 v3 v2 v4 弱連通 強(qiáng)連通 強(qiáng)連通分量：彼此強(qiáng)連通的頂點(diǎn)的子集 A C B D I E G F H ABC D EFG H I 完全圖 任意兩點(diǎn)間都有邊相關(guān)聯(lián)的圖。v j, 以 vi為起點(diǎn) vj為終點(diǎn)的頂點(diǎn)序列。 圖的基本概念 路徑 vi ID(vi): 入度 ，以 vi為終點(diǎn)的邊的數(shù)目。,vn} 頂點(diǎn) 集 E={ (vi, vj) | vi,vj∈ V, vi≠vj} 邊 集 無向圖 E={vi, vj|vi , vj∈ V}有向邊 集 有向圖 有向邊 vi, vj ， vi起點(diǎn) 弧尾， vj終點(diǎn) 弧頭 TD(vi): 一個(gè)頂點(diǎn)的 度 ,以 vi為端點(diǎn)的邊的數(shù)目。 簡單圖 沒有自身環(huán)，兩點(diǎn)間至多一條邊 v5 v1 v1 v3 v2 v3 v4 v4 v2 無向圖 有向圖 圖的基本概念 G=V, E V={v1,v2,? 圖 ? 圖的存儲(chǔ)表示 ? 圖的遍歷 ? 無向圖的連通分量和生成樹 ? 最短路徑 ? 拓?fù)渑判? 一、圖 圖 應(yīng)用最廣泛的數(shù)據(jù)結(jié)構(gòu)。 不同于樹的另一種 非線性結(jié)構(gòu) 每個(gè)頂點(diǎn)可以與 多個(gè) 其他頂點(diǎn)相關(guān)聯(lián)，各頂 點(diǎn)之間的關(guān)系是 任意 的。 OD(vi): 出度 , 以 vi為起點(diǎn)的邊的數(shù)目。 TD(vi)= OD(vi)+ ID(vi) OD=ID, TD=2|E|， |E| =1/2*TD TD OD ID 為整個(gè)圖的總度 ,出度 ,入度數(shù)。 路徑的長 路徑上邊的數(shù)目， 簡單路徑 頂點(diǎn)都不重復(fù)的路徑， 回路 環(huán) 首尾相接的路徑， 簡單回路 除第一個(gè)和最后一個(gè)頂點(diǎn)以外都不重 復(fù)的路徑， vivj連通 有路徑 viv j， 連通圖 任意兩點(diǎn)都連通， 有向圖 vivj強(qiáng)連通 vivj連通 vjvi也連通， 強(qiáng)連通圖 任意兩點(diǎn)都強(qiáng)連通。 無向完全圖 共有邊 1/2(n*(n1)) 條 , 有向完全圖 共有邊 n(n1) 條。 網(wǎng)絡(luò) 有權(quán)圖 子圖 G=(V, E), G?=(V?, E?) 如果 V? V, E? E , 就稱 G?是 G的子圖。 強(qiáng)連通分量 一個(gè)圖的極大強(qiáng)連通子圖。 非連通圖的 生成森林： 所有 k個(gè)連通分支的生成樹組成生成森林，共有 nk條邊。 有向圖的 生成森林： 有向圖的一個(gè)子圖，含有所有頂點(diǎn)，構(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 無向圖的鄰接矩陣是對(duì)稱矩陣 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