數據結構第5章圖

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

2、向圖：圖中的每條邊沒有方向的圖。 邊的兩個頂點沒有次序關系，無向圖用邊(u , v)表示對稱弧和； 在無向圖中弧和弧表示相同的邊(u , v)。 例如右圖G2是無向圖，G2=( V2, E2)， 其中： V2= v1 , v2, v3, v4, v5 E2=( v1 , v2), ( v1 , v4), ( v2, v3), ( v2 , v4), ( v3, v5), ( v4, v5) 名詞和術語 權：若圖中的邊或弧上附加有數量信息，如用于表示從一個頂點到另一個頂點的距離、耗費的代價、所需的時間、次數等，這種可反映邊或弧某種特征的數據稱為權。 有向網：帶權的有向圖。 無向網：帶權的無向圖。

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

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

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

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

7、G, / 有向圖 DN, / 有向網 UDG, / 無向圖 UDN / 無向網;#define MAX_VERTEX_NUM 20 /最大頂點個數template class ALGraph public: /圖的基本操作private: int numVertices; / 頂點個數 int numEdges; / 邊或弧的條數 GraphStyle style; / 圖的類型VertexType verticesMAX_VERTEX_NUM; / 鄰接矩陣，對無權圖，/用1或0表示相鄰否；對帶權圖，則為權值類型，方便起見，設權為整型int adjMatrixMAX_VERTEX_NUMMA

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

9、eight表示該邊或弧的權值，如果不是網，可以省略該數據項；next指針指示下一條邊或弧的結點。 此外，每個鏈表上附設一個表頭結點，data表示頂點vi的數據信息，edgeList指向鏈表中的第一個結點。 無向網的鄰接表例如：右圖無向網N2的鄰接表如下圖所示。有向網的鄰接表例如：右圖有向網N1的鄰接表如下圖所示。有向網的逆鄰接表例如：右圖有向網N1的逆鄰接表如下圖所示。鄰接表表結點的存儲結構/ 定義鄰接表的表結點class EdgeNodepublic:EdgeNode(int=-1, int=0); / 默認參數的構造函數int adjVertex; / 該邊或弧關聯的頂點在圖中的序號int

10、 weight; / 該邊或弧的權值EdgeNode *next; / 指向下一條邊或弧的指針;EdgeNode構造函數 / 構造這個頂點的鄰接表（用參數初始化表對數據成員初始化）/ 參數a為鄰接頂點的序號；參數w為邊的權值，默認權值為0EdgeNode:EdgeNode(int a, int w):adjVertex(a), weight(w), next(NULL)鄰接表頭結點的存儲結構/ 定義鄰接表的頭結點template class VertexNodepublic: void ClearEdgeList(); / 刪除這個頂點的鄰接表 bool AppendEdge(int, int

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

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

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

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

15、是否相等template class ALGraph public: enum GraphStyle / 圖的類型 DG, / 有向圖 DN, / 有向網 UDG, / 無向圖 UDN / 無向網 ;圖的鄰接表類（續(xù) 1） ALGraph(int = 0, GraphStyle = UDG); / 構造函數，默認圖的類型為無向圖 ALGraph(); int LocateVertex(const VertexType&); / 根據頂點的數據，找到頂點在頂點表中的序號 inline int GetNumVertices(); / 取得圖中的頂點數目 bool GetVertex(int

16、, VertexType&); / 根據序號，取得頂點的數據 bool SetVertex(int, const VertexType&); / 根據序號，設置頂點的數據 bool InsertVertex(const VertexType&); / 插入一個頂點 bool DeleteVertex(const VertexType&); / 刪除一個頂點 bool Insertedge(const VertexType&, const VertexType&, int = 0); / 插入一條邊 bool Deleteedge(const Ve

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

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

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

20、個鏈接，用以鏈表以頂點vi為頭的弧。5.2.3 十字鏈表表示法 十字鏈表表示法是有向圖的另一種鏈式存儲結構，可以看成將有向圖的鄰接表和逆鄰接表相結合所得到的一種鏈表。 在十字鏈表中，對應于有向圖中每一條弧有一個結點。其中，tailVertex和headVertex分別表示該弧的弧尾和弧頭各自在圖中的位置；weight表示該弧的權值；tailNext指向下一條與tailVertex（弧尾）相關聯的弧，headNext指向下一條與headVertex（弧頭）相關聯的弧。 類似地，對應于圖中的每個頂點也設一個頭結點。其中，data表示頂點的數據，firstIn指針指向以該頂點為弧頭的第一個弧結點，f

21、irstOut指針指向以該頂點為弧尾的第一個弧結點。 十字鏈表弧結點的存儲結構/ 定義十字鏈表的弧節(jié)點結構class EdgeNodepublic: int tailVertex, headVertex; / 該弧中的弧尾和弧頭各自在圖中的序號 int weight; / 該弧的權值 EdgeNode *tailNext,*headNext;十字鏈表頭結點的存儲結構/ 定義頭節(jié)點template class VertexNodepublic: VertexType data; / 頂點的數據 EdgeNode *firstIn, *firstOut; / firstIn表示以該頂點為弧頭的第一

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

23、是相同的。5.2.4 鄰接多重表 鄰接多重表表示法是無向圖的另一種鏈式存儲結構。如果每條邊只用一個表結點表示，且同時位于這條邊所關聯的兩個頂點的鏈表中，這樣的存儲結構稱為鄰接多重表。 每條邊的結點結構中adjVertex1和adjVertex2表示該邊的兩個鄰接頂點各自在圖中的位置；weight表示該邊的權值；next1指向下一條與頂點adjVertex1相關聯的邊；next2指向下一條與頂點adjVertex2相關聯的邊；visited表示在遍歷時是否訪問過的標志。 每個頂點也用一個結點表示，在頭結點中，data表示頂點的數據信息，edgeList表示指向第一條依附于該結點的邊的指針。鄰接多

24、重表表結點的存儲結構/ 定義鄰接多重表的表結點class EdgeNodepublic: EdgeNode(int=-1, int=-1, int=0, int=0); / 構造函數 int adjVertex1, adjVertex2 ; / 該邊關聯的鄰接頂點在圖中的序號 int weight; / 該邊的權值 EdgeNode *next1,*next2; bool visited; / 在遍歷時存放是否訪問過的標志;鄰接多重表頭結點的存儲結構/ 定義頭結點template class VertexNodepublic: VertexType data; / 頂點的數據 EdgeNode

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

26、造一個最多含s個頂點，類型為gs的圖G。參數s為該圖最多可存放的頂點個數，gs為圖的類型，如末說明，則默認為無向圖UDG；如果頂點個數s0，則申請s個鄰接表的頭結點空間。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，逐個刪除頂點的表結點，最后刪除鄰接表。template ALGraph(Ve

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

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

29、ata域為該頂點數據，edgeList域為NULL，并將頂點個數numVertices加1。/ 參數vex為要插入的頂點數據template bool ALGraph:InsertVertex(const VertexType &vex) / 如果存在的頂點個數已達最大值，則返回 if(numVertices=maxVertices) return false; / 判斷相同的頂點是否存在，如存在，則返回 for(int i=0; inumVertices; i+) if(verticesi.data=vex) return false;InsertVertex函數（續(xù)） / 增加一個

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

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

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

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

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

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

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

37、ge(v1); numEdges-; return true;Getedge函數/ / 根據頂點序號，取得兩頂點之間的邊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函數 / / 取得圖中第v個頂點的第一個鄰接頂點序號 template int ALGraph:GetFirstAdjVex(int v) if (v = numVertices) return -1; if (verticesv.edgeList = NULL) return -1; else return verticesv.edgeList-adjVertex; GetNextAdjVex函數 / 根據序號，取得v(相對于w)的下一個鄰接頂點序號 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 圖的遍歷 圖的遍歷是指從圖中某個頂點出發(fā)，按某一規(guī)則訪問圖中的每個頂點，且每個頂點僅被訪問一次。 與樹的遍歷一樣，圖的遍歷具有十分重要的作用，是圖問題中最基本和最重要的操作，圖的許多其他操作都與遍歷相關。

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

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

42、點，該鄰接頂點的序號為w， 對w遞歸調用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)先遍歷 首先將圖中每個頂點的訪問標志設為 FALSE, 之后搜索圖中每個頂點，如果未被訪問，則以該頂點為起始點，進行深度優(yōu)先搜索遍歷，否則繼續(xù)檢查下一頂點。非連通圖的深度優(yōu)先遍歷算法/ 以深度優(yōu)先的方法遍歷圖，參數Visit是遍歷到每個頂點時調用的函數template void ALGraph

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

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

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

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

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

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

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

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

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

52、下列在生成樹的構造過程中，圖中 n 個頂點分屬兩個集合：已落在生成樹上的頂點集 U 和尚未落在生成樹上的頂點集V-U ，則應在所有連通U中頂點和V-U中頂點的邊中選取權值最小的邊。abcdegf例如例如: :195141827168213ae12dcbgf7148531621所得生成樹權值和所得生成樹權值和= 14+8+3+5+16+21 = 67Prim算法程序實現 設兩個輔助數組U 和lowcost，數組U 用于記錄形成最小生成樹過程中集合U 的頂點，數組lowcost 用于記錄集合U 中每個頂點在加入集合U 時所關聯的最小代價的邊的權值（此時該邊兩個頂點中的一個在集合U 中，另一個在集合

53、V-U 中）。Prim算法程序實現/ 返回給定數組中，非0 最小元素的下標值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算法程序實現（續(xù)1）/ Prim算法，從第0個頂點出發(fā),計算并打印網g的最小生成樹template void Prim(ALGraph& g) if(g.GetNumVertices()=0) cout圖中無頂點!endl; return; int i, j,

54、k=0;/從第K個頂點出發(fā) VertexType vex; EdgeNode *edge=NULL; int *lowcost=new intg.GetNumVertices(); VertexType *U=new VertexTypeg.GetNumVertices();Prim算法程序實現（續(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算法程序實現（續(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算法的基本思想 考慮問題的出發(fā)點: 為使生成樹上邊的權值之和達到最小，則應使生成樹

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

57、向無環(huán)圖 假設以有向圖表示一個工程的施工圖或程序的數據流圖，則圖中不允許出現回路。 一個無環(huán)的有向圖叫有向無環(huán)圖（Directed Acyclic Graph），簡稱DAG。 有向樹、有向圖、有向無環(huán)圖的區(qū)別5.5.2 拓撲排序 檢查有向圖中是否存在回路的方法之一，是對有向圖進行拓撲排序。 什么叫拓撲排序？ 對有向圖進行如下操作：按照有向圖給出的次序關系，將圖中頂點排成一個線性序列，對于有向圖中沒有限定次序關系的頂點，則可以人為加上任意的次序關系。由此所得頂點的線性序列稱之為拓撲有序序列例：可求得拓撲有序序列： a, b, d, f, c, e, g 和a, b, c, d, e, f, g，

58、 還有其他的序列。如何進行拓撲排序1、從有向圖中選取一個沒有前驅的頂點，并輸出之；2、從有向圖中刪去此頂點以及所有以它為尾的弧； 重復上述兩步，直至圖空，或者圖不空但找不到無前驅的頂點為止。 在算法中需要用定量的描述替代定性的概念 沒有前驅的頂點 = 入度為零的頂點 刪除頂點及以它為尾的弧 = 弧頭頂點的入度減1 為了方便找到尚未輸出的無前驅頂點，而且為了避免每次選入度為0的頂點時掃描整個存儲空間，可設一個?；蜿犃袝捍嫠腥攵葹?的頂點。拓撲排序算法/ 對圖g中的各頂點求入度，存入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); 拓撲排序算法（續(xù)1）/ 拓撲排序。若有向圖g中無回路，此函數通過topoArr返回一個頂點序號的拓/撲序列，并返回true；否則返回false。toppArr存放拓撲次序templatebool TopologicalSort(ALGraph& g, int* topoAr

60、r) queue q; / 存放度為0的頂點的序號 VertexType vex; int count=0; int i; int w; int* inDegree=new intg.GetNumVertices(); / 存放頂點的入度 FindInDegree(g, inDegree); / 計算所有頂點的入度 for(i=0; ig.GetNumVertices(); i+) / 入度為0的頂點進隊列 if(inDegreei=0) q.push(i); i=0;拓撲排序算法（續(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