數(shù)據(jù)結(jié)構(gòu)第5章圖

1、 數(shù) 據(jù) 結(jié) 構(gòu) 第 5 章圖的結(jié)構(gòu)定義圖的結(jié)構(gòu)定義: 圖圖是由一個(gè)是由一個(gè)頂點(diǎn)集頂點(diǎn)集 V 和一個(gè)和一個(gè)邊邊集集 R構(gòu)成的數(shù)據(jù)結(jié)構(gòu)。構(gòu)成的數(shù)據(jù)結(jié)構(gòu)。 Graph = (V , R ) 其中，VR| v,wV 且 P(v,w) 謂詞 P(v,w) 定義了 的意義或信息。名詞和術(shù)語(yǔ) 有向圖：圖中的每條邊都有方向的圖。 邊的兩個(gè)頂點(diǎn)有次序關(guān)系，有向邊稱為從頂點(diǎn)u到頂點(diǎn)v的一條弧，u稱為弧尾（或始點(diǎn)），v稱為弧頭（或終點(diǎn)）； 有向圖中弧和弧表示不同的二條邊。 例如右圖G1是有向圖，G1=( V1, E1)， 其中： V1= v1 , v2, v3, v4, v5 E1=, , , , 名詞和術(shù)語(yǔ) 無(wú)

2、向圖：圖中的每條邊沒(méi)有方向的圖。 邊的兩個(gè)頂點(diǎn)沒(méi)有次序關(guān)系，無(wú)向圖用邊(u , v)表示對(duì)稱弧和； 在無(wú)向圖中弧和弧表示相同的邊(u , v)。 例如右圖G2是無(wú)向圖，G2=( V2, E2)， 其中： V2= v1 , v2, v3, v4, v5 E2=( v1 , v2), ( v1 , v4), ( v2, v3), ( v2 , v4), ( v3, v5), ( v4, v5) 名詞和術(shù)語(yǔ) 權(quán)：若圖中的邊或弧上附加有數(shù)量信息，如用于表示從一個(gè)頂點(diǎn)到另一個(gè)頂點(diǎn)的距離、耗費(fèi)的代價(jià)、所需的時(shí)間、次數(shù)等，這種可反映邊或弧某種特征的數(shù)據(jù)稱為權(quán)。 有向網(wǎng)：帶權(quán)的有向圖。 無(wú)向網(wǎng)：帶權(quán)的無(wú)向圖。

3、 例如下圖分別為有向網(wǎng)和無(wú)向網(wǎng)名詞和術(shù)語(yǔ) 假設(shè)圖中有 n 個(gè)頂點(diǎn)，e 條邊，則 完全圖：含有 e=n(n-1)/2 條邊的無(wú)向圖。 有向完全圖：含有 e=n(n-1) 條弧的有向圖。 若邊或弧的個(gè)數(shù) enlogn，則稱作稀疏圖，否則稱作稠密圖。 鄰接-假若頂點(diǎn)v 和頂點(diǎn)w 之間存在一條邊，則稱頂點(diǎn)v 和w 互為鄰接點(diǎn)。 關(guān)聯(lián)-邊(v,w) 和頂點(diǎn)v 和w 相關(guān)聯(lián)。 圈：圖中連接同一個(gè)頂點(diǎn)的邊叫圈。 平行邊：圖中兩個(gè)頂點(diǎn)之間若有兩條或兩條以上的邊，稱這些邊為平行邊。 簡(jiǎn)單圖：沒(méi)有圈也沒(méi)有平行邊的圖。名詞和術(shù)語(yǔ) 頂點(diǎn)的度：和頂點(diǎn)v 關(guān)聯(lián)的邊的數(shù)目定義為點(diǎn)v的度，記為d(v)。 頂點(diǎn)的出度：在有向圖

4、中， 以頂點(diǎn)v為弧尾的弧的數(shù)目，記為d+(v) 。 頂點(diǎn)的入度：在有向圖中，以頂點(diǎn)v為弧頭的弧的數(shù)目，記為d-(v) 。 頂點(diǎn)的度d(v)= d+(v) + d-(v) 。 例如在圖G2 中，頂點(diǎn)v4 的度d(v4)=3，頂點(diǎn)v5 的度d(v5)=2；而在圖G1中，頂點(diǎn)v4的入度d-(v4)= 1，v4 的出度d+ ( v4)=3，v4 的度d(v4)=4。名詞和術(shù)語(yǔ) 路徑：從頂點(diǎn)u 到頂點(diǎn)v 的路徑是指一個(gè)頂點(diǎn)序列(u=v1, v2, , vn=v) 。 路徑長(zhǎng)度：路徑上邊的數(shù)目。 簡(jiǎn)單路徑：序列中頂點(diǎn)不重復(fù)出現(xiàn)的路徑。 簡(jiǎn)單回路：序列中第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)相同的路徑。 子圖：G=(V,

5、 E)及G1=(V1, E1)是兩個(gè)圖，若滿足V1 V 且E1 E，則稱G1 是G 的子圖，記為G1 G。 生成子圖：若G1 G 且V1=V，則稱G1 是G 的生成子圖。名詞和術(shù)語(yǔ) 連通：若存在從頂點(diǎn)u 到v 的路徑，則稱u和v是連通的。 連通圖：無(wú)向圖 中的任意兩個(gè)頂點(diǎn)u、v 都是連通的。 連通分量：若無(wú)向圖為非連通圖，則圖中各個(gè)極大連通子圖稱作此圖的連通分量。 強(qiáng)連通圖：有向圖中的每一對(duì)頂點(diǎn)u , v都存在從u 到v 和從v 到u的路徑。 強(qiáng)連通分量:非強(qiáng)連通圖中的極大強(qiáng)連通子圖。 生成樹(shù)：一個(gè)連通圖G 的生成樹(shù)是一個(gè)極小連通生成子圖，它含有圖中全部頂點(diǎn)， 但只有足以構(gòu)成一棵樹(shù)的n-1條邊

6、。 有向樹(shù)：如果一個(gè)有向圖恰有一個(gè)頂點(diǎn)的入度為0，其余頂點(diǎn)的入度均為1，則是一棵有向樹(shù)。5.2 圖的存儲(chǔ)結(jié)構(gòu) 常用的有如下四種表示方法：一、鄰接矩陣表示法二、鄰接表表示法三、有向圖的十字鏈表表示法 四、無(wú)向圖的鄰接多重表表示法5.2.1 鄰接矩陣表示法 定義：矩陣的元素 鄰接矩陣AG=(aij) nn 是n 階方陣（nn 的二維數(shù)組）其中例1，其它0E(G)v,v或)v,(v若1,jijiija0v11v22v33v44v5鄰接矩陣表示法例2 有向圖的鄰接矩陣為非對(duì)稱矩陣，而無(wú)向圖的鄰接矩陣為對(duì)稱矩陣。0v11v22v33v44v5鄰接矩陣表示法enum GraphStyle / 圖的類(lèi)型 D

7、G, / 有向圖 DN, / 有向網(wǎng) UDG, / 無(wú)向圖 UDN / 無(wú)向網(wǎng);#define MAX_VERTEX_NUM 20 /最大頂點(diǎn)個(gè)數(shù)template class ALGraph public: /圖的基本操作private: int numVertices; / 頂點(diǎn)個(gè)數(shù) int numEdges; / 邊或弧的條數(shù) GraphStyle style; / 圖的類(lèi)型VertexType verticesMAX_VERTEX_NUM; / 鄰接矩陣，對(duì)無(wú)權(quán)圖，/用1或0表示相鄰否；對(duì)帶權(quán)圖，則為權(quán)值類(lèi)型，方便起見(jiàn)，設(shè)權(quán)為整型int adjMatrixMAX_VERTEX_NUMMA

8、X_VERTEX_NUM;鄰接矩陣表示法的優(yōu)缺點(diǎn) 一個(gè)鄰接矩陣需要的存儲(chǔ)空間是O(n2)（需存放n個(gè)頂點(diǎn)和n2條邊的信息量）。顯然，鄰接矩陣的存儲(chǔ)空間與其邊或弧的數(shù)目無(wú)關(guān)，因此這種存儲(chǔ)結(jié)構(gòu)適用于稠密圖，但對(duì)于稀疏圖而言，存儲(chǔ)密度較低。 鄰接矩陣可以較方便地求各鄰接點(diǎn)的位置，但不宜于頂點(diǎn)的插入和刪除操作。 5.2.2 鄰接表表示法 鄰接表是圖的一種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。在鄰接表表示法中，對(duì)圖中每個(gè)頂點(diǎn)建立一個(gè)鄰接表（一般采用單鏈表結(jié)構(gòu)），第i個(gè)鄰接表中的每個(gè)結(jié)點(diǎn)表示與頂點(diǎn)vi相關(guān)聯(lián)的邊（對(duì)有向圖是以頂點(diǎn)vi為尾的?。?每個(gè)結(jié)點(diǎn)由3個(gè)域組成，其中，adjVertex表示與頂點(diǎn)vi鄰接的點(diǎn)在圖中的位置；w

9、eight表示該邊或弧的權(quán)值，如果不是網(wǎng)，可以省略該數(shù)據(jù)項(xiàng)；next指針指示下一條邊或弧的結(jié)點(diǎn)。 此外，每個(gè)鏈表上附設(shè)一個(gè)表頭結(jié)點(diǎn)，data表示頂點(diǎn)vi的數(shù)據(jù)信息，edgeList指向鏈表中的第一個(gè)結(jié)點(diǎn)。 無(wú)向網(wǎng)的鄰接表例如：右圖無(wú)向網(wǎng)N2的鄰接表如下圖所示。有向網(wǎng)的鄰接表例如：右圖有向網(wǎng)N1的鄰接表如下圖所示。有向網(wǎng)的逆鄰接表例如：右圖有向網(wǎng)N1的逆鄰接表如下圖所示。鄰接表表結(jié)點(diǎn)的存儲(chǔ)結(jié)構(gòu)/ 定義鄰接表的表結(jié)點(diǎn)class EdgeNodepublic:EdgeNode(int=-1, int=0); / 默認(rèn)參數(shù)的構(gòu)造函數(shù)int adjVertex; / 該邊或弧關(guān)聯(lián)的頂點(diǎn)在圖中的序號(hào)int

10、 weight; / 該邊或弧的權(quán)值EdgeNode *next; / 指向下一條邊或弧的指針;EdgeNode構(gòu)造函數(shù) / 構(gòu)造這個(gè)頂點(diǎn)的鄰接表（用參數(shù)初始化表對(duì)數(shù)據(jù)成員初始化）/ 參數(shù)a為鄰接頂點(diǎn)的序號(hào)；參數(shù)w為邊的權(quán)值，默認(rèn)權(quán)值為0EdgeNode:EdgeNode(int a, int w):adjVertex(a), weight(w), next(NULL)鄰接表頭結(jié)點(diǎn)的存儲(chǔ)結(jié)構(gòu)/ 定義鄰接表的頭結(jié)點(diǎn)template class VertexNodepublic: void ClearEdgeList(); / 刪除這個(gè)頂點(diǎn)的鄰接表 bool AppendEdge(int, int

11、=0); / 在這個(gè)頂點(diǎn)的鄰接表中加入一條邊 bool RemoveEdge(int); / 在這個(gè)頂點(diǎn)的鄰接表中刪除一條邊 VertexType data; / 頂點(diǎn)的數(shù)據(jù)信息 EdgeNode *edgeList; / 指向第一條依附該頂點(diǎn)的邊的指針;ClearEdgeList函數(shù) /刪除這個(gè)頂點(diǎn)的鄰接表。清空這個(gè)頂點(diǎn)的鄰接表中的各結(jié)點(diǎn)，并把頭結(jié)點(diǎn)的edgeList值設(shè)為空。templatevoid VertexNode:ClearEdgeList() EdgeNode *p, *q; p=edgeList; while(p!=NULL) q=p-next; delete p; p=q;

12、edgeList=NULL;AppendEdge 函數(shù)/在這個(gè)頂點(diǎn)的鄰接表的最后加入一條邊，若發(fā)現(xiàn)鄰接表中已存在這條邊，則返回值為false。/ 參數(shù)v 為加入邊中鄰接頂點(diǎn)序號(hào)，wgh 為加入邊的權(quán)值templatebool VertexNode:AppendEdge(int v, int wgh) EdgeNode *p=edgeList; EdgeNode *q=NULL;/ 找到鏈接表中末結(jié)點(diǎn)，末結(jié)點(diǎn)的指針賦值給q。如果發(fā)現(xiàn)有一個(gè)結(jié)點(diǎn)的adjVex 的值與v 相同，則返回false while(p!=NULL) if(p-adjVertex=v) return false;AppendE

13、dge 函數(shù)（續(xù)） q=p; p=p-next; / 在鄰接表的最后加上一條邊 p=new EdgeNode(v, wgh); if(q=NULL) edgeList=p； else q-next=p; return true;RemoveEdge 函數(shù)/在這個(gè)頂點(diǎn)的鄰接表中刪除一條邊。在遍歷鄰接表過(guò)程中若發(fā)現(xiàn)這條邊，則刪除該邊的表結(jié)點(diǎn)。/ 參數(shù)v 為要?jiǎng)h除邊的鄰接頂點(diǎn)序號(hào)template bool VertexNode:RemoveEdge(int v) EdgeNode *p=edgeList; EdgeNode *q=NULL; / 遍歷鄰接表，如果發(fā)現(xiàn)這條邊，則刪除 while(p!=

14、NULL) if(p-adjVertex=v) if(p=edgeList) edgeList=p-next; else q-next=p-next;RemoveEdge 函數(shù)（續(xù)） delete p; return true; q=p; p=p-next; return false;RemoveEdge 函數(shù)（續(xù)） delete p; return true; q=p; p=p-next; return false;圖的鄰接表類(lèi)（存儲(chǔ)結(jié)構(gòu)）/ VertexType是頂點(diǎn)的數(shù)據(jù)類(lèi)型，如果VertexType不是簡(jiǎn)單的數(shù)據(jù)類(lèi)型，在定義VertexType時(shí)，必須重載=運(yùn)算符，用于判斷兩個(gè)頂點(diǎn)數(shù)據(jù)

15、是否相等template class ALGraph public: enum GraphStyle / 圖的類(lèi)型 DG, / 有向圖 DN, / 有向網(wǎng) UDG, / 無(wú)向圖 UDN / 無(wú)向網(wǎng) ;圖的鄰接表類(lèi)（續(xù) 1） ALGraph(int = 0, GraphStyle = UDG); / 構(gòu)造函數(shù)，默認(rèn)圖的類(lèi)型為無(wú)向圖 ALGraph(); int LocateVertex(const VertexType&); / 根據(jù)頂點(diǎn)的數(shù)據(jù)，找到頂點(diǎn)在頂點(diǎn)表中的序號(hào) inline int GetNumVertices(); / 取得圖中的頂點(diǎn)數(shù)目 bool GetVertex(int

16、, VertexType&); / 根據(jù)序號(hào)，取得頂點(diǎn)的數(shù)據(jù) bool SetVertex(int, const VertexType&); / 根據(jù)序號(hào)，設(shè)置頂點(diǎn)的數(shù)據(jù) bool InsertVertex(const VertexType&); / 插入一個(gè)頂點(diǎn) bool DeleteVertex(const VertexType&); / 刪除一個(gè)頂點(diǎn) bool Insertedge(const VertexType&, const VertexType&, int = 0); / 插入一條邊 bool Deleteedge(const Ve

17、rtexType&, const VertexType&); / 刪除一條邊圖的鄰接表類(lèi)（續(xù) 2） int GetFirstAdjVex(int); / 根據(jù)序號(hào)，取得頂點(diǎn)的第一個(gè)鄰接頂點(diǎn)的序號(hào)int GetNextAdjVex(int v, int w); / 根據(jù)序號(hào)，取得v(相對(duì)于w)的下一個(gè)鄰接頂點(diǎn)序號(hào)bool Getedge(int, int,edgeNode*&); / 根據(jù)頂點(diǎn)序號(hào)，取得兩頂點(diǎn)之間的邊 inline int GetNumedges(); / 取得圖中的邊數(shù) void DFSTraverse(void (*Visit)(const Verte

18、xType&); / 深度優(yōu)先遍歷圖 void BFSTraverse(void (*Visit)(const VertexType&); / 廣度優(yōu)先遍歷圖圖的鄰接表類(lèi)（續(xù) 3） private: void DFS(void (*Visit)(const VertexType&), int); / 從一個(gè)頂點(diǎn)出發(fā)深度優(yōu)先遍歷圖 VertexNode *vertices; / 頂點(diǎn)表 int numVertices; / 頂點(diǎn)個(gè)數(shù) int numedges; / 邊數(shù) int maxVertices; / 最多可存放的頂點(diǎn)個(gè)數(shù) GraphStyle style; / 圖

19、的類(lèi)型 bool *visited; / 在遍歷時(shí)存放是否訪問(wèn)過(guò)的標(biāo)志;鄰接表表示法的優(yōu)缺點(diǎn) 若無(wú)向圖（或網(wǎng)）中有n個(gè)頂點(diǎn)、e條邊，則它的鄰接表需n個(gè)頭結(jié)點(diǎn)和2e個(gè)表結(jié)點(diǎn)。顯然，針對(duì)稀疏圖而言，用鄰接表表示法比鄰接矩陣表示法節(jié)省存儲(chǔ)空間。鄰接表中頂點(diǎn)vi的度恰為第i個(gè)鏈表中的結(jié)點(diǎn)數(shù)。 若有向圖（或網(wǎng)）中有n個(gè)頂點(diǎn)、e條弧，則它的鄰接表需n個(gè)頭結(jié)點(diǎn)和e個(gè)表結(jié)點(diǎn)。頂點(diǎn)vi的出度為第i個(gè)鏈表中的結(jié)點(diǎn)數(shù)，但要計(jì)算這個(gè)頂點(diǎn)的入度則需遍歷所有鄰接表。 有時(shí)為了便于求一個(gè)頂點(diǎn)的入度，或者如果需要反復(fù)訪問(wèn)一個(gè)頂點(diǎn)的直接前驅(qū)（即關(guān)聯(lián)該頂點(diǎn)的弧的弧尾），可以建立一個(gè)有向圖（或網(wǎng)）的逆鄰接表，即對(duì)每個(gè)頂點(diǎn)vi建立一

20、個(gè)鏈接，用以鏈表以頂點(diǎn)vi為頭的弧。5.2.3 十字鏈表表示法 十字鏈表表示法是有向圖的另一種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，可以看成將有向圖的鄰接表和逆鄰接表相結(jié)合所得到的一種鏈表。 在十字鏈表中，對(duì)應(yīng)于有向圖中每一條弧有一個(gè)結(jié)點(diǎn)。其中，tailVertex和headVertex分別表示該弧的弧尾和弧頭各自在圖中的位置；weight表示該弧的權(quán)值；tailNext指向下一條與tailVertex（弧尾）相關(guān)聯(lián)的弧，headNext指向下一條與headVertex（弧頭）相關(guān)聯(lián)的弧。 類(lèi)似地，對(duì)應(yīng)于圖中的每個(gè)頂點(diǎn)也設(shè)一個(gè)頭結(jié)點(diǎn)。其中，data表示頂點(diǎn)的數(shù)據(jù)，firstIn指針指向以該頂點(diǎn)為弧頭的第一個(gè)弧結(jié)點(diǎn)，f

21、irstOut指針指向以該頂點(diǎn)為弧尾的第一個(gè)弧結(jié)點(diǎn)。 十字鏈表弧結(jié)點(diǎn)的存儲(chǔ)結(jié)構(gòu)/ 定義十字鏈表的弧節(jié)點(diǎn)結(jié)構(gòu)class EdgeNodepublic: int tailVertex, headVertex; / 該弧中的弧尾和弧頭各自在圖中的序號(hào) int weight; / 該弧的權(quán)值 EdgeNode *tailNext,*headNext;十字鏈表頭結(jié)點(diǎn)的存儲(chǔ)結(jié)構(gòu)/ 定義頭節(jié)點(diǎn)template class VertexNodepublic: VertexType data; / 頂點(diǎn)的數(shù)據(jù) EdgeNode *firstIn, *firstOut; / firstIn表示以該頂點(diǎn)為弧頭的第一

22、個(gè)弧結(jié)點(diǎn)， / firstOut表示以該頂點(diǎn)為弧尾的第一個(gè)弧結(jié)點(diǎn);圖的十字鏈表的存儲(chǔ)結(jié)構(gòu)/ 圖的十字鏈表定義template class ALGraph.private: VertexNode *vertices; / 頂點(diǎn)表 int numVertices; / 頂點(diǎn)個(gè)數(shù) int numEdges; / 弧數(shù) int maxVertices; / 最多可存放的頂點(diǎn)個(gè)數(shù);十字鏈表圖例例如：右圖有向圖G1的十字鏈表如下圖所示。十字鏈表表示法的優(yōu)缺點(diǎn) 在十字鏈表中既容易找到以頂點(diǎn)vi為尾的的弧，也容易找到以頂點(diǎn)vi為頭的弧，因此可容易求出每個(gè)頂點(diǎn)的出度和入度。 建立十字鏈表的時(shí)間復(fù)雜度和建立鄰接表

23、是相同的。5.2.4 鄰接多重表 鄰接多重表表示法是無(wú)向圖的另一種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。如果每條邊只用一個(gè)表結(jié)點(diǎn)表示，且同時(shí)位于這條邊所關(guān)聯(lián)的兩個(gè)頂點(diǎn)的鏈表中，這樣的存儲(chǔ)結(jié)構(gòu)稱為鄰接多重表。 每條邊的結(jié)點(diǎn)結(jié)構(gòu)中adjVertex1和adjVertex2表示該邊的兩個(gè)鄰接頂點(diǎn)各自在圖中的位置；weight表示該邊的權(quán)值；next1指向下一條與頂點(diǎn)adjVertex1相關(guān)聯(lián)的邊；next2指向下一條與頂點(diǎn)adjVertex2相關(guān)聯(lián)的邊；visited表示在遍歷時(shí)是否訪問(wèn)過(guò)的標(biāo)志。 每個(gè)頂點(diǎn)也用一個(gè)結(jié)點(diǎn)表示，在頭結(jié)點(diǎn)中，data表示頂點(diǎn)的數(shù)據(jù)信息，edgeList表示指向第一條依附于該結(jié)點(diǎn)的邊的指針。鄰接多

24、重表表結(jié)點(diǎn)的存儲(chǔ)結(jié)構(gòu)/ 定義鄰接多重表的表結(jié)點(diǎn)class EdgeNodepublic: EdgeNode(int=-1, int=-1, int=0, int=0); / 構(gòu)造函數(shù) int adjVertex1, adjVertex2 ; / 該邊關(guān)聯(lián)的鄰接頂點(diǎn)在圖中的序號(hào) int weight; / 該邊的權(quán)值 EdgeNode *next1,*next2; bool visited; / 在遍歷時(shí)存放是否訪問(wèn)過(guò)的標(biāo)志;鄰接多重表頭結(jié)點(diǎn)的存儲(chǔ)結(jié)構(gòu)/ 定義頭結(jié)點(diǎn)template class VertexNodepublic: VertexType data; / 頂點(diǎn)的數(shù)據(jù) EdgeNode

25、 *edgeList; / 指向第一條依附于該結(jié)點(diǎn)的邊的指針;圖的鄰接多重表的存儲(chǔ)結(jié)構(gòu)/ 圖的鄰接多重表定義template class ALGraph.private: VertexNode *vertices; / 頂點(diǎn)表 int numVertices; / 頂點(diǎn)個(gè)數(shù) int numedges; / 邊數(shù) int maxVertices; / 最多可存放的頂點(diǎn)個(gè)數(shù);鄰接多重表圖例例如：右圖無(wú)向圖G2的鄰接多重表如下圖所示。5.3 圖的基本操作 本節(jié)以鄰接表作存儲(chǔ)結(jié)構(gòu)，來(lái)介紹圖的一些基本操作。 主要內(nèi)容： 介紹一組圖中有關(guān)頂點(diǎn)的基本操作。 介紹圖中的一些基本操作。 圖的遍歷圖的構(gòu)造函數(shù)/構(gòu)

26、造一個(gè)最多含s個(gè)頂點(diǎn)，類(lèi)型為gs的圖G。參數(shù)s為該圖最多可存放的頂點(diǎn)個(gè)數(shù)，gs為圖的類(lèi)型，如末說(shuō)明，則默認(rèn)為無(wú)向圖UDG；如果頂點(diǎn)個(gè)數(shù)s0，則申請(qǐng)s個(gè)鄰接表的頭結(jié)點(diǎn)空間。template ALGraph(VertexType):ALGraph(int s, GraphStyle gs): numVertices(0),numEdges(0), maxVertices(s), style(gs) if(s0) vertices=new VertexNode(VertexType)s;5.3.1圖的析構(gòu)函數(shù)/用于銷(xiāo)毀圖G，逐個(gè)刪除頂點(diǎn)的表結(jié)點(diǎn)，最后刪除鄰接表。template ALGraph(Ve

27、rtexType):ALGraph() for (int i=0; inumVertices; i+) verticesi.ClearedgeList(); if (maxVertices!=0) delete vertices;GetVertex函數(shù)/根據(jù)序號(hào)，取得頂點(diǎn)vex的數(shù)據(jù)/ 參數(shù)v為頂點(diǎn)序號(hào)；參數(shù)vex用于返回頂點(diǎn)數(shù)據(jù)template(class VertexType)bool ALGraph(VertexType):GetVertex(int v, VertexType&vex) if(v=numVertices) return false; vex=verticesv.

28、data; return true;SetVertex函數(shù)/根據(jù)頂點(diǎn)的序號(hào)，設(shè)置頂點(diǎn)vex的數(shù)據(jù)/ 參數(shù)v為頂點(diǎn)序號(hào)；參數(shù)vex用于設(shè)臵的頂點(diǎn)數(shù)據(jù)template(class VertexType)bool ALGraph(VertexType):SetVertex(int v, const VertexType &vex) if(v=numVertices) return false; verticesv.data=vex; return true;InsertVertex函數(shù)/在圖中插入一個(gè)頂點(diǎn)。如果存在的頂點(diǎn)個(gè)數(shù)或者鄰接表的頭結(jié)點(diǎn)中已有該頂點(diǎn)，則返回；否則增加鄰接表的頭結(jié)點(diǎn)，其d

29、ata域?yàn)樵擁旤c(diǎn)數(shù)據(jù)，edgeList域?yàn)镹ULL，并將頂點(diǎn)個(gè)數(shù)numVertices加1。/ 參數(shù)vex為要插入的頂點(diǎn)數(shù)據(jù)template bool ALGraph:InsertVertex(const VertexType &vex) / 如果存在的頂點(diǎn)個(gè)數(shù)已達(dá)最大值，則返回 if(numVertices=maxVertices) return false; / 判斷相同的頂點(diǎn)是否存在，如存在，則返回 for(int i=0; inumVertices; i+) if(verticesi.data=vex) return false;InsertVertex函數(shù)（續(xù)） / 增加一個(gè)

30、頭頂點(diǎn) verticesnumVertices.data=vex; verticesnumVertices+.edgeList=NULL; return true;DeleteVertex函數(shù)/在圖中刪除一個(gè)頂點(diǎn)。首先在鄰接表中找到要?jiǎng)h除的頂點(diǎn)的序號(hào)，若未找到則返回；然后遍歷鄰接表中的其他頂點(diǎn)，如果這些頂點(diǎn)的鏈表中包含了要?jiǎng)h除的頂點(diǎn)，則把相應(yīng)的邊結(jié)點(diǎn)刪除，邊數(shù)減1；最后，在鄰接表中刪除該頂點(diǎn)的頭結(jié)點(diǎn)，頂點(diǎn)數(shù)減1，并將序號(hào)大于要?jiǎng)h除的頂點(diǎn)序號(hào)的每個(gè)頂點(diǎn)其序號(hào)都減1。/ 參數(shù)vex為欲刪除頂點(diǎn)的值template bool ALGraph:DeleteVertex(const VertexType

31、 &vex) int i; int v; / 在鄰接表中找到要?jiǎng)h除頂點(diǎn)的序號(hào)，如果沒(méi)找到，則返回 if(v=LocateVertex(vex)=-1) return false;DeleteVertex函數(shù)（續(xù)1） / 遍歷其他頂點(diǎn)，如果這些頂點(diǎn)的鏈表中包含了要?jiǎng)h除的頂點(diǎn)， 則移除 for(i=0; inumVertices; i+) if(i!=v) if(verticesi.RemoveEdge(v) numEdges-; / 在頂點(diǎn)表中刪除序號(hào)為v的頂點(diǎn) verticesv.ClearEdgeList(); for(i=v; inumVertices-1; i+) vertice

32、si=verticesi+1; numVertices-;DeleteVertex函數(shù)（續(xù)2） / 如果在所有的鄰接邊表中的頂點(diǎn)序號(hào)大于要?jiǎng)h除的頂點(diǎn)序號(hào)， 但將頂點(diǎn)序號(hào)減1 EdgeNode *p; for (i=0; iadjVertexv) p-adjVertex-; / 如果v，則將頂點(diǎn)號(hào)減1 p=p-next; return true;LocateVertex函數(shù)/根據(jù)頂點(diǎn)的數(shù)據(jù)，找到頂點(diǎn)在鄰接表中的序號(hào)，如未找到，則返回值為1。/ 參數(shù)vex為頂點(diǎn)的數(shù)據(jù)/ 返回值為頂點(diǎn)的序號(hào)；如返回-1，未找到相關(guān)的頂點(diǎn)template int ALGraph:LocateVertex(const

33、VertexType & vex) for(int i=0; inumVertices; i+) if(verticesi.data=vex) return i; return -1;InsertEdge函數(shù)/在圖中插入一條邊(vex1 , vex2)。先找到給出的兩個(gè)頂點(diǎn)vex1、vex2在鄰接表中的序號(hào)，在第一個(gè)頂點(diǎn)vex1的鏈表中插入邊( vex1 , vex2)，若該圖是無(wú)向圖，則同樣在vex2的鏈表中插入邊( vex2, vex1)，最后邊數(shù)加1。/ 參數(shù)vex1、vex2為要插入弧的兩個(gè)頂點(diǎn)的值；參數(shù)wgh為欲插入邊的權(quán)值，默認(rèn)值為0template bool ALGrap

34、h:InsertEdge(const VertexType &vex1,const VertexType &vex2, int wgh) / 找到兩個(gè)頂點(diǎn)在鄰接表中的序號(hào)，分別賦值給v1、v2 / 兩個(gè)頂點(diǎn)中只要有一個(gè)在圖的頂點(diǎn)表中未找到，則返回 int v1=LocateVertex(vex1); int v2=LocateVertex(vex2);InsertEdge函數(shù)（續(xù)） if(v1=-1 | v2=-1) return false; / 為第一個(gè)頂點(diǎn)的鄰接表中增加一條弧 verticesv1.AppendEdge(v2, wgh); / 如果為無(wú)向圖，則必須在另一頂

35、點(diǎn)的鄰接表中增加一條弧 if(style=UDG | style=UDN) verticesv2.AppendEdge(v1, wgh); numEdges+; return true;DeleteEdge函數(shù)/在圖中刪除一條邊。先找到給出的兩個(gè)頂點(diǎn)vex1、vex2在鄰接表中的序號(hào)，在第一個(gè)頂點(diǎn)vex1的鏈表中刪除邊(vex1, vex2)，若該圖是無(wú)向圖，則同樣在vex2的鏈表中刪除邊(vex2, vex1)，最后邊數(shù)減1。/ 參數(shù)vex1、vex2為要?jiǎng)h除邊的兩個(gè)頂點(diǎn)數(shù)據(jù)template bool ALGraph:DeleteEdge(const VertexType &vex1

36、,const VertexType &vex2) / 找到兩個(gè)頂點(diǎn)在頂點(diǎn)表中的序號(hào)，分別賦值給v1、v2 / 兩個(gè)頂點(diǎn)中只要有一個(gè)在圖的頂點(diǎn)表中未找到，則返回 int v1=LocateVertex(vex1); int v2=LocateVertex(vex2); if(v1=-1 | v2=-1) return false;DeleteEdge函數(shù)（續(xù)） / 為第一個(gè)頂點(diǎn)的鄰接表中刪除該邊 verticesv1.RemoveEdge(v2); / 如果為無(wú)向圖，則必須在另一頂點(diǎn)的鏈表中刪除邊 if(style=UDG | style=UDN) verticesv2.RemoveEd

37、ge(v1); numEdges-; return true;Getedge函數(shù)/ / 根據(jù)頂點(diǎn)序號(hào)，取得兩頂點(diǎn)之間的邊template bool ALGraph:Getedge(int v, int w,edgeNode*& edge) if(v = numVertices) return false; if(w = numVertices) return false; edge = verticesv.edgeList; while (edge!= NULL) if ( edge - adjVertex = w) break; edge = edge-next; return ed

38、ge != NULL;GetFirstAdjVex函數(shù) / / 取得圖中第v個(gè)頂點(diǎn)的第一個(gè)鄰接頂點(diǎn)序號(hào) template int ALGraph:GetFirstAdjVex(int v) if (v = numVertices) return -1; if (verticesv.edgeList = NULL) return -1; else return verticesv.edgeList-adjVertex; GetNextAdjVex函數(shù) / 根據(jù)序號(hào)，取得v(相對(duì)于w)的下一個(gè)鄰接頂點(diǎn)序號(hào) template int ALGraph:GetNextAdjVex(int v, int

39、w) if(v = numVertices) return -1; edgeNode *p = verticesv.edgeList; while (p != NULL) if (p-adjVertex = w) break; p = p-next; if (p = NULL | p-next = NULL) return -1; return p-next-adjVertex; 5.3.2 圖的遍歷 圖的遍歷是指從圖中某個(gè)頂點(diǎn)出發(fā)，按某一規(guī)則訪問(wèn)圖中的每個(gè)頂點(diǎn)，且每個(gè)頂點(diǎn)僅被訪問(wèn)一次。 與樹(shù)的遍歷一樣，圖的遍歷具有十分重要的作用，是圖問(wèn)題中最基本和最重要的操作，圖的許多其他操作都與遍歷相關(guān)。

40、 兩條遍歷圖的路徑：深度優(yōu)先遍歷和廣度優(yōu)先遍歷5.3.2 深度優(yōu)先遍歷 深度優(yōu)先搜索首先選擇圖中某個(gè)頂點(diǎn)u作為起始點(diǎn)進(jìn)行訪問(wèn)，然后依次從u的未被訪問(wèn)的鄰接點(diǎn)v出發(fā)深度優(yōu)先搜索遍歷圖，直至圖中所有和u有路徑相通的頂點(diǎn)都被訪問(wèn)到；若圖中還有頂點(diǎn)未被訪問(wèn)到，則另選圖中一個(gè)未被訪問(wèn)的頂點(diǎn)作為起始點(diǎn)，重復(fù)上述過(guò)程，直至所有頂點(diǎn)都被訪問(wèn)到為止。連通圖的深度優(yōu)先遍歷 W1、W2和W3 均為 V 的鄰接點(diǎn)，SG1、SG2 和 SG3 分別為含頂點(diǎn)W1、W2和W3 的子圖。 訪問(wèn)頂點(diǎn) V ：for (W1、W2、W3 ) 若該鄰接點(diǎn)W未被訪問(wèn)， 則從它出發(fā)進(jìn)行深度 優(yōu)先搜索遍歷。Vw1SG1SG2SG3w2w3

41、w2連通圖的深度優(yōu)先遍歷1. 從深度優(yōu)先搜索遍歷連通圖的過(guò)程類(lèi)似于樹(shù)的先根遍歷；2. 如何判別V的鄰接點(diǎn)是否被訪問(wèn)？ 解決的辦法是：為每個(gè)頂點(diǎn)設(shè)立一個(gè) “訪問(wèn)標(biāo)志visitedw”。連通圖的深度優(yōu)先遍歷算法/ 從某一頂點(diǎn)出發(fā)，遞歸地以深度優(yōu)先的方法遍歷圖，參數(shù)v是出發(fā)頂點(diǎn)在頂點(diǎn)表的序號(hào)template void ALGraph:DFS(void (*Visit)(const VertexType&), int v) / 設(shè)置序號(hào)為v的頂點(diǎn)的訪問(wèn)標(biāo)志，并調(diào)用Visit函數(shù)訪問(wèn)它 visitedv=true; Visit(verticesv.data); / 查找序號(hào)為v的頂點(diǎn)的所有鄰接頂

42、點(diǎn)，該鄰接頂點(diǎn)的序號(hào)為w， 對(duì)w遞歸調(diào)用DFS EdgeNode *p=verticesv.edgeList; 連通圖的深度優(yōu)先遍歷算法（續(xù)） while(p!=NULL) int w=p-adjVertex; if(!visitedw) DFS(Visit, w); p=p-next; 非連通圖的深度優(yōu)先遍歷 首先將圖中每個(gè)頂點(diǎn)的訪問(wèn)標(biāo)志設(shè)為 FALSE, 之后搜索圖中每個(gè)頂點(diǎn)，如果未被訪問(wèn)，則以該頂點(diǎn)為起始點(diǎn)，進(jìn)行深度優(yōu)先搜索遍歷，否則繼續(xù)檢查下一頂點(diǎn)。非連通圖的深度優(yōu)先遍歷算法/ 以深度優(yōu)先的方法遍歷圖，參數(shù)Visit是遍歷到每個(gè)頂點(diǎn)時(shí)調(diào)用的函數(shù)template void ALGraph

43、:DFSTraverse(void (*Visit) (const VertexType &) int v; / 每個(gè)頂點(diǎn)的訪問(wèn)標(biāo)志置為false visited=new boolnumVertices; for(v=0; vnumVertices; v+) visitedv=false; / 以頂點(diǎn)表中的每個(gè)未訪問(wèn)過(guò)的頂點(diǎn)出發(fā)進(jìn)行遍歷 for (v=0; vw1, V-w2, V-w8 的路徑長(zhǎng)度為的路徑長(zhǎng)度為1；V-w7, V-w3, V-w5 的的路徑長(zhǎng)度為路徑長(zhǎng)度為2；V-w6, V-w4 的路徑長(zhǎng)度為的路徑長(zhǎng)度為3。w1Vw2w7w6w3w8w5w4廣度優(yōu)先遍歷算法/ 以廣度

44、優(yōu)先的方法遍歷圖，參數(shù)Visit是遍歷到每個(gè)頂點(diǎn)時(shí)調(diào)用的函數(shù)template void ALGraph:BFSTraverse(void (*Visit) (const VertexType &) int v; std:queue vertexQueue; / 輔助隊(duì)列 EdgeNode *p; / 每一頂點(diǎn)的訪問(wèn)標(biāo)志置為false visited=new boolnumVertices; for(v=0; vnumVertices; v+) visitedv=false;廣度優(yōu)先遍歷算法（續(xù)1） / 以頂點(diǎn)表中的每個(gè)未訪問(wèn)過(guò)的頂點(diǎn)出發(fā)進(jìn)行遍歷 for(v=0; vadjVertex;

45、 if(!visitedw) visitedw=true; Visit(verticesw.data); vertexQueue.push(w); p=p-next; delete visited;廣度優(yōu)先遍歷例子 訪問(wèn)順序： v1 v2 v3 v4 v5 v6 v7 v8V1V2V4V5V3V7V6V85.3.2遍歷應(yīng)用舉例求一條從頂點(diǎn)v 到頂點(diǎn) s 的簡(jiǎn)單路徑圖的點(diǎn)著色問(wèn)題求從頂點(diǎn) v 到頂點(diǎn) s的簡(jiǎn)單路徑例如：求從頂點(diǎn) b 到頂點(diǎn) k 的一條簡(jiǎn)單路徑。從頂點(diǎn) b 出發(fā)進(jìn)行深度優(yōu)先搜索遍歷。 假設(shè)找到的第一個(gè)鄰接點(diǎn)是c， 則可能得到的結(jié)點(diǎn)訪問(wèn)序列為: b c h d a e k 假設(shè)找到的

46、第一個(gè)鄰接點(diǎn)是a， 則可能得到的結(jié)點(diǎn)訪問(wèn)序列為: b a e k結(jié)論1. 從頂點(diǎn) v 到頂點(diǎn) s ,若存在路徑，則從頂點(diǎn)v 出發(fā)進(jìn)行深度優(yōu)先搜索，必能搜索到頂點(diǎn) s 。2. 遍歷過(guò)程中搜索到的頂點(diǎn)不一定是路徑上的頂點(diǎn)。3. 由它出發(fā)進(jìn)行的深度優(yōu)先遍歷已經(jīng)完成的頂點(diǎn)不是路徑上的頂點(diǎn)。abchdekfg求路徑長(zhǎng)度最短的路徑可以基于廣度優(yōu)先求路徑長(zhǎng)度最短的路徑可以基于廣度優(yōu)先搜索遍歷進(jìn)行，但需要修改鏈隊(duì)列的搜索遍歷進(jìn)行，但需要修改鏈隊(duì)列的結(jié)點(diǎn)結(jié)構(gòu)及其入隊(duì)列和出隊(duì)列的算法。結(jié)點(diǎn)結(jié)構(gòu)及其入隊(duì)列和出隊(duì)列的算法。求下圖中頂點(diǎn)求下圖中頂點(diǎn) 3 至頂點(diǎn)至頂點(diǎn) 5 的一條最短路徑。的一條最短路徑。鏈隊(duì)列的狀態(tài)鏈隊(duì)

47、列的狀態(tài)如下所示如下所示: 3 1 2 4 7 5 Q.front Q.rear321475689圖的點(diǎn)著色問(wèn)題 問(wèn)題描述：如果要給一幅地圖著色時(shí)，具有公共邊界的兩個(gè)區(qū)域要涂上不同的顏色。要確保兩個(gè)相鄰的區(qū)域永遠(yuǎn)沒(méi)有相同的顏色，一種方法是對(duì)每個(gè)區(qū)域使用不同的顏色，不過(guò)這是一種低效的方法，而且在具有許多區(qū)域的地圖上，可能難以區(qū)分相似的顏色。替代的方法是盡量使用不多的顏色來(lái)填充地圖。于是，提出這樣的問(wèn)題，給一幅地圖著色需要的最小顏色數(shù)目是多少？ 如果把地圖的每個(gè)區(qū)域都表示成一個(gè)頂點(diǎn)，若兩個(gè)頂點(diǎn)所表示的區(qū)域具有公共邊界，則用邊連接這兩個(gè)頂點(diǎn)，因此給地圖填充顏色的問(wèn)題變轉(zhuǎn)化為圖的點(diǎn)著色問(wèn)題了。 對(duì)簡(jiǎn)單

48、圖G的每個(gè)頂點(diǎn)涂上一種顏色，使相鄰的頂點(diǎn)涂不同的顏色，稱為對(duì)圖G的一種點(diǎn)著色。若能用k種顏色給G點(diǎn)著色，就稱G是k點(diǎn)可著色的。若G是k點(diǎn)可著色的，但不是k-1點(diǎn)可著色的，就稱G的點(diǎn)色數(shù)為k。 圖的點(diǎn)著色問(wèn)題 解決方法：圖的點(diǎn)著色問(wèn)題的解決，在這兒需要借助廣度優(yōu)先搜索遍歷的方法。首先，計(jì)算出圖中每個(gè)頂點(diǎn)的度，并以度遞減的順序列出頂點(diǎn)序列v1，v2，vn，使得d(v1)d(v2)d(vn)。把顏色1指定給v1和序列中與v1不相鄰的下一個(gè)頂點(diǎn)（若存在這樣的頂點(diǎn)），并且繼續(xù)指定給每個(gè)在序列中與已經(jīng)指定了顏色1的頂點(diǎn)不相鄰的頂點(diǎn)。然后把顏色2指定給序列中還沒(méi)有著色的第一個(gè)頂點(diǎn)，并繼續(xù)把顏色2指定給那些在

49、序列中還沒(méi)有著色且與已經(jīng)指定了顏色2的頂點(diǎn)不相鄰的頂點(diǎn)。若還有未著色的頂點(diǎn)，則指定顏色3給序列中還沒(méi)有著色的第一個(gè)頂點(diǎn)，并繼續(xù)把顏色3指定給那些在序列中還沒(méi)有著色且與已經(jīng)指定了顏色3的頂點(diǎn)不相鄰的頂點(diǎn)。繼續(xù)這個(gè)過(guò)程，直至所有的頂點(diǎn)都有著色為止。 5.3.3圖的連通性 如果G是無(wú)向圖，對(duì)于連通圖，從圖中任一頂點(diǎn)出發(fā)，通過(guò)調(diào)用DFS或者BFS，可訪問(wèn)到圖中所有頂點(diǎn)。因此，可通過(guò)此種方法檢查是否有未被訪問(wèn)的頂點(diǎn)，從而判斷圖G的連通性。對(duì)于非連通圖，其連通分量可以通過(guò)還未被訪問(wèn)的頂點(diǎn)v反復(fù)調(diào)用DFS(v)或者BFS(v)來(lái)得到，每次從新的起點(diǎn)v出發(fā)搜索得到的頂點(diǎn)訪問(wèn)序列恰為其各個(gè)連通分量中的頂點(diǎn)集，這

50、些頂點(diǎn)集分別加上原圖中所有關(guān)聯(lián)這些頂點(diǎn)的邊，便構(gòu)成了非連通圖的各個(gè)連通分量。 生成樹(shù)：如果G是無(wú)向連通圖，顯然，從圖中任一頂點(diǎn)出發(fā)遍歷圖時(shí)，遍歷過(guò)程中經(jīng)過(guò)的所有的邊和圖G中所有頂點(diǎn)一起構(gòu)成連通圖G的極小連通子圖。 深度優(yōu)先生成樹(shù)：由深度優(yōu)先搜索得到的生成樹(shù)。 廣度優(yōu)先生成樹(shù)：由廣度優(yōu)先搜索得到的生成樹(shù)。 5.4 最小生成樹(shù) 問(wèn)題：假設(shè)要在 n 個(gè)城市之間建立通訊聯(lián)絡(luò)網(wǎng)，則連通 n 個(gè)城市只需要修建 n-1條線路，如何在最節(jié)省經(jīng)費(fèi)的前提下建立這個(gè)通訊網(wǎng)？ 該問(wèn)題等價(jià)于：構(gòu)造網(wǎng)的一棵最小生成樹(shù)，即：在 e 條帶權(quán)的邊中選取 n-1 條邊（不構(gòu)成回路），使“權(quán)值之和”為最小。 二種算法： 算法一：P

51、rim（普里姆）算法 算法二：Kruskal（克魯斯卡爾）算法最小生成樹(shù)的性質(zhì) MST 性質(zhì)：設(shè)G=(V, E)是一個(gè)連通網(wǎng)，U 是頂點(diǎn)集V 的一個(gè)非空子集。若(u, v)是具有最小權(quán)值的邊，其中uU，vV-U，則必存在一棵包含邊(u, v)的最小生成樹(shù)。Prim算法 基本思想： 取圖中任意一個(gè)頂點(diǎn) v 作為生成樹(shù)的根，之后往生成樹(shù)上添加新的頂點(diǎn) w。在添加的頂點(diǎn) w 和已經(jīng)在生成樹(shù)上的頂點(diǎn)v 之間必定存在一條邊，并且該邊的權(quán)值在所有連通頂點(diǎn) v 和 w 之間的邊中取值最小。之后繼續(xù)往生成樹(shù)上添加頂點(diǎn)，直至生成樹(shù)上含有 n-1 個(gè)頂點(diǎn)為止。Prim算法 處理過(guò)程： 一般情況下所添加的頂點(diǎn)應(yīng)滿足

52、下列在生成樹(shù)的構(gòu)造過(guò)程中，圖中 n 個(gè)頂點(diǎn)分屬兩個(gè)集合：已落在生成樹(shù)上的頂點(diǎn)集 U 和尚未落在生成樹(shù)上的頂點(diǎn)集V-U ，則應(yīng)在所有連通U中頂點(diǎn)和V-U中頂點(diǎn)的邊中選取權(quán)值最小的邊。abcdegf例如例如: :195141827168213ae12dcbgf7148531621所得生成樹(shù)權(quán)值和所得生成樹(shù)權(quán)值和= 14+8+3+5+16+21 = 67Prim算法程序?qū)崿F(xiàn) 設(shè)兩個(gè)輔助數(shù)組U 和lowcost，數(shù)組U 用于記錄形成最小生成樹(shù)過(guò)程中集合U 的頂點(diǎn)，數(shù)組lowcost 用于記錄集合U 中每個(gè)頂點(diǎn)在加入集合U 時(shí)所關(guān)聯(lián)的最小代價(jià)的邊的權(quán)值（此時(shí)該邊兩個(gè)頂點(diǎn)中的一個(gè)在集合U 中，另一個(gè)在集合

53、V-U 中）。Prim算法程序?qū)崿F(xiàn)/ 返回給定數(shù)組中，非0 最小元素的下標(biāo)值int Minimum(int arr, int n) int i; int min=0; for(i=1; i0) min=i; break; for(i=min; i0 & arriarrmin) min=i; return min;Prim算法程序?qū)崿F(xiàn)（續(xù)1）/ Prim算法，從第0個(gè)頂點(diǎn)出發(fā),計(jì)算并打印網(wǎng)g的最小生成樹(shù)template void Prim(ALGraph& g) if(g.GetNumVertices()=0) cout圖中無(wú)頂點(diǎn)!endl; return; int i, j,

54、k=0;/從第K個(gè)頂點(diǎn)出發(fā) VertexType vex; EdgeNode *edge=NULL; int *lowcost=new intg.GetNumVertices(); VertexType *U=new VertexTypeg.GetNumVertices();Prim算法程序?qū)崿F(xiàn)（續(xù)2） for(i=0; ig.GetNumVertices(); i+) lowcosti=INT_MAX; for(i=0; iweight; g.GetVertex(k, Ui); g.GetVertex(k, Uk); lowcostk=0;Prim算法程序?qū)崿F(xiàn)（續(xù)3） for(i=1; ig

55、.GetNumVertices(); i+) k=Minimum(lowcost, g.GetNumVertices(); g.GetVertex(k,vex); coutUk vex : lowcostkendl; lowcostk=0; for(j=0; jweightweight; g.GetVertex(k, Uj); delete lowcost; delete U;abcdegf195141827168213ae12dcb7aaa19141814e12ee8168d3dd7213c5 5Kruskal算法的基本思想 考慮問(wèn)題的出發(fā)點(diǎn): 為使生成樹(shù)上邊的權(quán)值之和達(dá)到最小，則應(yīng)使生成樹(shù)

56、中每一條邊的權(quán)值盡可能地小。 具體做法:設(shè)G =(V,E)是一個(gè)連通網(wǎng)，網(wǎng)中共有n個(gè)頂點(diǎn)。最小生成樹(shù)的初始狀態(tài)為只有n個(gè)頂點(diǎn)而無(wú)邊的非連通圖T=(V,)，圖中每個(gè)頂點(diǎn)自成一個(gè)連通分量。在E中選擇代價(jià)最小的邊，若該邊依附的頂點(diǎn)落在T中不同的連通分量上，則將此邊加入到T中，否則舍去此邊而選擇下一條代價(jià)最小的邊，直至T中所有頂點(diǎn)都在同一連通分量上為止。 abcdegf195141827168213ae12dcbgf7148531621例如例如: :7121819二種算法比較算法名算法名普里姆算法普里姆算法克魯斯卡爾算法克魯斯卡爾算法時(shí)間復(fù)雜度O(n2)O(eloge)適用范圍稠密圖稀疏圖5.5.1有

57、向無(wú)環(huán)圖 假設(shè)以有向圖表示一個(gè)工程的施工圖或程序的數(shù)據(jù)流圖，則圖中不允許出現(xiàn)回路。 一個(gè)無(wú)環(huán)的有向圖叫有向無(wú)環(huán)圖（Directed Acyclic Graph），簡(jiǎn)稱DAG。 有向樹(shù)、有向圖、有向無(wú)環(huán)圖的區(qū)別5.5.2 拓?fù)渑判?檢查有向圖中是否存在回路的方法之一，是對(duì)有向圖進(jìn)行拓?fù)渑判颉?什么叫拓?fù)渑判颍?對(duì)有向圖進(jìn)行如下操作：按照有向圖給出的次序關(guān)系，將圖中頂點(diǎn)排成一個(gè)線性序列，對(duì)于有向圖中沒(méi)有限定次序關(guān)系的頂點(diǎn)，則可以人為加上任意的次序關(guān)系。由此所得頂點(diǎn)的線性序列稱之為拓?fù)溆行蛐蛄欣嚎汕蟮猛負(fù)溆行蛐蛄校?a, b, d, f, c, e, g 和a, b, c, d, e, f, g，

58、 還有其他的序列。如何進(jìn)行拓?fù)渑判?、從有向圖中選取一個(gè)沒(méi)有前驅(qū)的頂點(diǎn)，并輸出之；2、從有向圖中刪去此頂點(diǎn)以及所有以它為尾的弧； 重復(fù)上述兩步，直至圖空，或者圖不空但找不到無(wú)前驅(qū)的頂點(diǎn)為止。 在算法中需要用定量的描述替代定性的概念 沒(méi)有前驅(qū)的頂點(diǎn) = 入度為零的頂點(diǎn) 刪除頂點(diǎn)及以它為尾的弧 = 弧頭頂點(diǎn)的入度減1 為了方便找到尚未輸出的無(wú)前驅(qū)頂點(diǎn)，而且為了避免每次選入度為0的頂點(diǎn)時(shí)掃描整個(gè)存儲(chǔ)空間，可設(shè)一個(gè)棧或隊(duì)列暫存所有入度為0的頂點(diǎn)。拓?fù)渑判蛩惴? 對(duì)圖g中的各頂點(diǎn)求入度，存入inArrTemplate void FindInDegree( ALGraph& g, int inAr

59、r) int i,v; for(i=0; ig.GetNumVertices(); i+) inArri=0; for(i=0; ig.GetNumVertices(); i+) v=g.GetFirstAdjVex(i); while(v!=-1) inArrv+; v=g.GetNextAdjVex(i,v); 拓?fù)渑判蛩惴ǎɡm(xù)1）/ 拓?fù)渑判颉Ｈ粲邢驁Dg中無(wú)回路，此函數(shù)通過(guò)topoArr返回一個(gè)頂點(diǎn)序號(hào)的拓/撲序列，并返回true；否則返回false。toppArr存放拓?fù)浯涡騮emplatebool TopologicalSort(ALGraph& g, int* topoAr

60、r) queue q; / 存放度為0的頂點(diǎn)的序號(hào) VertexType vex; int count=0; int i; int w; int* inDegree=new intg.GetNumVertices(); / 存放頂點(diǎn)的入度 FindInDegree(g, inDegree); / 計(jì)算所有頂點(diǎn)的入度 for(i=0; ig.GetNumVertices(); i+) / 入度為0的頂點(diǎn)進(jìn)隊(duì)列 if(inDegreei=0) q.push(i); i=0;拓?fù)渑判蛩惴ǎɡm(xù)2） while( !q.empty() topoArri+=q.front(); for(w=g.GetFirstAdjVex(q.front(); w!=-1; w=g.GetNextAdjVex(q.front(),w) if(-inDegreew=0) q.push(w); q.pop(); count+; delete i