Unit09圖的遍歷TraversalofGraph學(xué)校放假，某同學(xué)回家看望奶奶，奶奶很高興，準(zhǔn)備帶孫子一塊出門去公園，卻忘記了鑰匙放在哪個房間了，為了不讓老人著急，請幫助這位同學(xué)設(shè)計一個高效找鑰匙的策略。奶奶家的房屋結(jié)構(gòu)如圖所示，是兩室兩廳一廚一衛(wèi)一陽臺。①理解和運用線性表、順序表、鏈表、數(shù)組、棧、隊列和圖等。②認識、理解和運用深度優(yōu)先搜索和廣度優(yōu)先搜索算法遍歷圖。③運用大O表示法分析遍歷圖的時間復(fù)雜度。隊列（Queue）隊列又稱為先進先出線性表，它只允許在表的前端（隊頭front）進行刪除操作，而在表的后端（隊尾rear）進行插入操作，所以隊列和棧一樣，是一種操作受限制的線性表，如圖所示。不含任何數(shù)據(jù)元素的隊列稱為空隊列（EmptyQueue）。1．順序隊列（SequentialQueue）隊列的順序存儲結(jié)構(gòu)是把隊列中數(shù)據(jù)元素按照其邏輯次序依次存放在一組地址連續(xù)的存儲單元（數(shù)組）里的結(jié)構(gòu)，采用這種存儲結(jié)構(gòu)的隊列稱為順序隊列。圖中所示，隊列為空時rear=front。入隊操作相對于追加元素。不需要移動元素；但是出隊操作時，為了保證隊列能充分利用空間，就必須通過移動數(shù)據(jù)元素，把隊列中數(shù)據(jù)元素依次移動一位。當(dāng)然也可以不移動元素，出隊時，移動front隊頭指針就可以。但這樣又會帶來由于不斷出隊，front指針不斷增加，造成數(shù)組低端存在大量空閑空間，而入隊到達數(shù)組中最大的位置后，出現(xiàn)隊列空間被耗盡的“假溢出”現(xiàn)象。為解決這個問題，可以通過數(shù)學(xué)上的取模操作實現(xiàn)這種邏輯上的首尾相連的循環(huán)結(jié)構(gòu)，這種順序存儲結(jié)構(gòu)稱為循環(huán)隊列（CircularQueue）。設(shè)存儲循環(huán)隊列的數(shù)組長度為QueueSize，隊列的長度公式： Queuelength=(rear-front+QueueSize)%QueueSize （9-1）入隊操作時，隊尾指針公式：

rear=(rear+1)%QueueSize （9-2）出隊操作時，隊頭指針公式：

front=(front+1)%QueueSize （9-3）隊空的判定條件：

rear=front （9-4）隊滿的判定條件也是rear=front，為了區(qū)分，把隊滿的判定條件設(shè)為隊滿的臨界狀態(tài)：

（rear+1）%QueueSize=front （9-5）2．鏈隊列（LinkedQueue）隊列的鏈?zhǔn)酱鎯Y(jié)構(gòu)是把隊列中各個數(shù)據(jù)元素獨立存儲，依靠指針鏈接建立相鄰的邏輯次序的結(jié)構(gòu)稱為隊列的鏈?zhǔn)酱鎯Y(jié)構(gòu)，簡稱鏈隊列。一般鏈隊列采用單鏈表實現(xiàn)，為了操作上的方便，通常使用帶表頭的單鏈表，設(shè)置鏈隊列頭指針指向表頭節(jié)點，表頭節(jié)點的指針域指針指向隊列第一個數(shù)據(jù)元素，尾指針指向最后一個節(jié)點。圖（Graph）圖是一種復(fù)雜的非線性結(jié)構(gòu)，它的二元組定義：圖G是一個有序二元組，表示為G(V,E)，其中V稱為頂集（VerticesSet），E稱為邊集（EdgesSet），E與V不相交。它們也可寫成V(G)和E(G)。其中，頂集的元素被稱為頂點（Vertex），邊集的元素被稱為邊（Edge），E的元素都是二元組，用(x,y)表示，其中x,y∈V。1、圖的基本概念頂點之間的邊沒有方向，或者是雙向的，則稱該邊為無向邊，用無序偶對(vi,vj)表示，其中，vi,vj屬于頂點的集合，該圖稱為無向圖（UndirectedGraph）。頂點之間的邊有方向。則稱該邊為有向邊，或稱弧，用有序偶對<vi,vj>表示，vi稱為弧尾，vj稱為弧頭，該圖稱為有向圖（DirectedGraph）。頂點之間的邊賦予了權(quán)值（Weight），則該圖稱為有權(quán)圖，或者稱網(wǎng)（Network）。在無向圖中，頂點v的度（Degree）指的是依附于該頂點的邊的個數(shù)。在有向圖中，頂點v的度為入度（In-Degree）和出度（Out-Degree）之和，入度指的是以該頂點為弧頭的弧的個數(shù)，出度指的是以該頂點為弧尾的弧的個數(shù)。在圖G(V,E)中，頂點vi到vj（i≠j）的頂點序列稱為路徑（Path），路徑上邊（或?。┑臄?shù)目稱為路徑長度（PathLength）。顯然，路徑可能不唯一。如果路徑最終回到了起點，即第一個頂點和最后一個頂點相同，則該路徑為環(huán)（Ring）或回路（Circuit）。如果在路徑序列中，頂點不重復(fù)出現(xiàn)的路徑稱為簡單路徑（SimplePath）。除去第一個和最后一個頂點外，其他頂點不重復(fù)出現(xiàn)的回路稱為簡單回路（SimpleCircuit）。在無向圖中，兩頂點之間存在路徑，說明是連通的，若任意兩頂點vi和vj（i≠j）之間存在路徑，則稱該圖為連通圖（ConnectedGraph），在有向圖中，這種圖稱為強連通圖（StronglyConnectedGraph）。2．圖的存儲結(jié)構(gòu)（1）圖的鄰接矩陣存儲，也稱為數(shù)組表示法用一個一維數(shù)組存儲圖中頂點的信息，一個二維數(shù)組存儲圖中的邊（或?。┑男畔ⅲǜ黜旤c之間的鄰接關(guān)系），該二維數(shù)組稱為圖的鄰接矩陣（AdjacencyMatrix）。如果圖G(V,E)有n個頂點，則鄰接矩陣是一個n階方陣，定義為如果是網(wǎng)，則上述公式定義為（2）圖的鄰接表存儲。對于圖中每一個頂點建立一個鏈表，用一個一維數(shù)組存儲鏈表的表頭節(jié)點，鏈表中的表節(jié)點表示依附于該頂點的邊（或弧）。采用這種存儲結(jié)構(gòu)的圖稱為鄰接表（AdjacencyList），其中，表頭節(jié)點由兩個域組成，頂點域（Vex）存放圖中頂點的信息，指針域（Firstedge）指向第一條依附于該頂點的邊（或弧）。表節(jié)點由兩個域組成，鄰接點域（Adjvex）指示與表頭節(jié)點相鄰接的頂點在圖中的位置，鏈域（Nextedge）指向與表頭節(jié)點相鄰接的下一條邊（或弧）；如果圖是有權(quán)圖（或網(wǎng)），還需加一個權(quán)值域（Weight）用于存放有權(quán)圖中邊（或弧）的權(quán)值所示。3．圖的遍歷通常圖的遍歷（TraversalofGraph）有兩種方式：廣度優(yōu)先搜索算法和深度優(yōu)先搜索。廣度優(yōu)先搜索是以層次方式進行，需要隊列保存已經(jīng)訪問的頂點；而深度優(yōu)先搜索是以遞歸方式進行的，所以需要棧記錄訪問的路線。為了區(qū)分頂點是否被訪問，都需要設(shè)置一個標(biāo)志數(shù)組來記錄頂點的訪問情況。（1）廣度優(yōu)先搜索算法（BreadthFirstSearch）又稱寬度優(yōu)先搜索，是圖的搜索算法之一，又稱為BFS算法，屬于一種盲目搜尋方法，它并不考慮結(jié)果的可能位置，而是通過系統(tǒng)地展開并檢查圖中的所有頂點，徹底地搜索整張圖，從而解決以下兩個問題。圖中兩頂點之間是否有路徑相連。如果有路徑，那條路徑是最短的。算法設(shè)計如下：訪問標(biāo)志數(shù)組closed[]賦初值0（0表示沒有訪問過，1表示已經(jīng)訪問過）。初始化循環(huán)隊列open（記錄訪問的頂點）。從指定的頂點開始，訪問入隊并置訪問標(biāo)志為1。出隊，訪問出隊頂點，將該頂點的鄰居頂點（即與之有邊或弧連接的頂點）依次入隊，并置訪問標(biāo)志為1；重復(fù)第（4）步操作，直到隊列為空，完成整張圖的搜索。（2）深度優(yōu)先搜索算法深度優(yōu)先搜索算法（DepthFirstSearch）也是一種盲目搜索方法，用于圖的遍歷，又叫DFS算法。沿著圖中某一頂點v（也被稱為源頂點）出發(fā)，盡可能深地搜索v的分支。當(dāng)該v的所在邊都已被探尋過，搜索將回溯到發(fā)現(xiàn)頂點v的那條邊的起始頂點。這一過程一直進行到已發(fā)現(xiàn)從源頂點可達的所有頂點為止。如果還存在未被發(fā)現(xiàn)的頂點，則選擇其中一個作為源頂點并重復(fù)以上過程，整個進程反復(fù)進行直到所有節(jié)點都被訪問為止。算法設(shè)計如下。訪問頂點v（源頂點）。依次從v未被訪問的鄰居頂點出發(fā)，對圖進行深度優(yōu)先搜索；直至圖中和v有路徑相通的頂點都被訪問。若此時圖中尚有頂點未被訪問，則從一個未被訪問的頂點出發(fā)，重新進行深度優(yōu)先搜索，直到圖中所有頂點均被訪問過為止。深度優(yōu)先搜索算法的遞歸條件遞歸條件（RecursiveCase）：只要鄰居頂點未被訪問，調(diào)用DFS。基線條件（BaseCase）：圖中頂點均已訪問（標(biāo)記數(shù)組closed的值都為1）。我們通過一個例子來詳細分析。例題09-01對圖所示的五岳三山無向圖G(V，E)，采用鄰接矩陣存儲，請用深度優(yōu)先搜索算法編寫代碼實現(xiàn)從任意指定起始頂點出發(fā)游歷三山五岳的路徑。圖中各個字母分別代表山脈：a—西岳華山，b—北岳恒山，c—東岳泰山，d—中岳嵩山，e—南岳衡山，f—黃山，g—廬山，h—雁蕩山。對例題09-01對圖所示的五岳三山無向圖G(V，E)，采用鄰接矩陣存儲，請用廣度優(yōu)先搜索算法編寫代碼實現(xiàn)從任意指定起始頂點出發(fā)游歷三山五岳的路徑。圖中各個字母分別代表山脈：a—西岳華山，b—北岳恒山，c—東岳泰山，d—中岳嵩山，e—南岳衡山，f—黃山，g—廬山，h—雁蕩山。算法分析廣度優(yōu)先搜索算法以一種系統(tǒng)的方式從圖G(V，E)中指定頂點出發(fā)，探尋它所能到達的所有頂點，并計算出該頂點到所有頂點的距離（最少邊數(shù)）。顯然，所有頂點都要被訪問1次，那么怎樣確定從指定頂點出發(fā)，依次訪問其余頂點呢？這就需要注意以下兩個關(guān)鍵點：openclosed（1）頂點的訪問次序通過被稱為open的容器（循環(huán)隊列）來存放尚未被訪問鄰居頂點。從指定頂點開始，訪問該頂點，將其加入open隊列，再出隊，然后依次訪問出隊頂點的未被訪問鄰居頂點，逐一加入隊列。重復(fù)上述過程，直到隊列空為止，出隊的序列就是頂點訪問次序。（2）頂點不重復(fù)訪問為了保證訪問的頂點是沒有被訪問過的，通過使用一個被稱為closed的容器（標(biāo)記數(shù)組）存儲頂點是否被訪問的信息。以下是使用黑、白、灰三種顏色著色頂點方法來模擬整個搜索過程。為每個頂點著色（白色、灰色或黑色），白色代表沒有被訪問的頂點，黑色代表已經(jīng)訪問過的頂點，灰色代表著已訪問和未訪問頂點之間的邊界。廣度優(yōu)先搜索算法過程及循環(huán)隊列open和標(biāo)記數(shù)組close的變化情況見圖所示。1、根據(jù)任務(wù)要求和算法分析設(shè)計程序；2、編碼、調(diào)試、運行；3、做好記錄；4、總結(jié)。圖的深度優(yōu)先遍歷類似于樹的先序遍歷，需要用到棧結(jié)構(gòu)。圖是一種復(fù)雜的非線性結(jié)構(gòu)，可以通過遍歷等方法簡化為線性結(jié)構(gòu)。圖的存儲有鄰接矩陣和鄰接表兩種。圖的廣度優(yōu)先遍歷類似于樹的層序遍歷，需要用到隊列結(jié)構(gòu)。單元數(shù)據(jù)結(jié)構(gòu)算法講解實操01線性表順序表數(shù)組順序查找二分查找二分查找02順序表數(shù)組鏈表簡單選擇排序簡單選擇排序03線性表順序表鏈表棧遞歸算法遞歸算法04線性表順序表數(shù)組鏈表快速排序快速排序05線性表順序表數(shù)組鏈表散列表散列表查找算法散列表查找