解決圖的編程問題PPT課件

1、2021/3/91解決圖的編程問題數(shù)據(jù)結(jié)構(gòu)(C#語(yǔ)言版)解決圖的編程問題解決圖的編程問題數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)(C#語(yǔ)言版語(yǔ)言版)2021/3/92目標(biāo)目標(biāo) 在本章中,你將學(xué)到: 在圖中存儲(chǔ)數(shù)據(jù) 圖的深度優(yōu)先搜索和廣度優(yōu)先搜索算法 最小生成樹 圖的最短路徑 解決圖的編程問題解決圖的編程問題數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)(C#語(yǔ)言版語(yǔ)言版)2021/3/93學(xué)習(xí)情境學(xué)習(xí)情境用圖高速公路交通網(wǎng)的編程用圖高速公路交通網(wǎng)的編程 問題描述問題描述 一個(gè)地區(qū)由許多城市組成，為實(shí)現(xiàn)城市間的高速運(yùn)輸，需要在這些城市間鋪設(shè)高速公路，以達(dá)到任意兩個(gè)城市間高速運(yùn)輸?shù)哪康?。?jīng)過考察和預(yù)算，鋪設(shè)的高速公路交通網(wǎng)如圖9.1所示。其中每個(gè)頂點(diǎn)

2、代表一個(gè)城市，頂點(diǎn)間的連線代表兩個(gè)城市間鋪設(shè)的高速公路，而線上的數(shù)字表示兩個(gè)城市間的距離（單位：公理）。如圖所示。請(qǐng)根據(jù)上面的描述，解決下面的問題： 用C#編寫一程序來存儲(chǔ)該高速公路交通網(wǎng)的信息 。 從任何一個(gè)城市出發(fā)，訪問所有的城市，給出訪問城市的順序。 如果想從一個(gè)城市到另一個(gè)城市旅行，給出最短的旅行路線。 解決圖的編程問題解決圖的編程問題數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)(C#語(yǔ)言版語(yǔ)言版)2021/3/94 圖是一系列頂點(diǎn)（結(jié)點(diǎn)）和描述頂點(diǎn)之間的關(guān)系邊（?。┙M成。圖是數(shù)據(jù)元素的集合，這些數(shù)據(jù)元素被相互連接以形成網(wǎng)絡(luò)。其形式化定義為： G=（V，E） V=Vi | Vi某個(gè)數(shù)據(jù)元素集合 E=(Vi,Vj)

3、 | Vi,VjVP(Vi,Vj) 認(rèn)識(shí)圖認(rèn)識(shí)圖圖的定義和術(shù)語(yǔ)圖的定義和術(shù)語(yǔ)1. 圖的定義圖的定義 其中，G表示圖，V是頂點(diǎn)的集合，E是邊或弧的集合。在集合E中，P(Vi,Vj)表示頂點(diǎn)Vi和頂點(diǎn)Vj之間有邊或弧相連。解決圖的編程問題解決圖的編程問題數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)(C#語(yǔ)言版語(yǔ)言版)2021/3/95認(rèn)識(shí)圖認(rèn)識(shí)圖圖的定義和術(shù)語(yǔ)圖的定義和術(shù)語(yǔ)2. 圖的術(shù)語(yǔ)圖的術(shù)語(yǔ)頂點(diǎn)集：圖中具有相同特性的數(shù)據(jù)元素的集合稱為頂點(diǎn)集邊（?。哼吺且粚?duì)頂點(diǎn)間的路徑，通常帶箭頭的邊稱為弧弧頭：每條箭頭線的頭頂點(diǎn)表示構(gòu)成弧的有序?qū)χ械暮笠粋€(gè)弧尾：每條箭頭線的尾頂點(diǎn)表示構(gòu)成弧的有序?qū)χ械那耙粋€(gè)頂點(diǎn)，稱為弧尾或始點(diǎn)。度：在

4、無向圖中的頂點(diǎn)的度是指連那個(gè)頂點(diǎn)的邊的數(shù)量。在有向圖中，每個(gè)頂點(diǎn)有兩種類的的度：出度和入度。 入度：頂點(diǎn)的入度是指向那個(gè)頂點(diǎn)的邊的數(shù)量。 出度：頂點(diǎn)的出度是由那個(gè)頂點(diǎn)出發(fā)的邊的數(shù)量。 權(quán)：有些圖的邊（或?。└綆в幸恍?shù)據(jù)信息，這些數(shù)據(jù)信息稱為邊（或弧）的權(quán)（weigh）.解決圖的編程問題解決圖的編程問題數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)(C#語(yǔ)言版語(yǔ)言版)2021/3/96認(rèn)識(shí)圖認(rèn)識(shí)圖圖的定義和術(shù)語(yǔ)圖的定義和術(shù)語(yǔ)3. 圖的分類圖的分類有向圖：在一個(gè)圖中，如果任意兩頂點(diǎn)構(gòu)成的偶對(duì)（Vi,Vj）是有序的，那么稱該圖為有向圖。這里Vi是弧尾，Vj是弧頭。這表示有一個(gè)從頂點(diǎn)Vi到頂點(diǎn) Vj的路徑。但是從Vj到Vi是不可

5、能的 無向圖：在一個(gè)圖中，如果有任意兩頂點(diǎn)構(gòu)成的邊（Vi,Vj），（Vi,Vj）和（Vj ，Vi）是相同的 在一個(gè)無向圖中，如果任意兩個(gè)頂點(diǎn)之間都有邊相連，則稱該圖為無向完全圖。無向完全圖又稱完全圖 在一個(gè)有向圖，如果任意兩個(gè)頂點(diǎn)之間都是弧相連，則稱該圖為有向完全圖。 有很少條邊或弧的圖稱為稀疏圖，反之稱為稠密圖。 解決圖的編程問題解決圖的編程問題數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)(C#語(yǔ)言版語(yǔ)言版)2021/3/97 SetNode()：在圖中增加一個(gè)新的頂點(diǎn) GetNode()：獲取圖中指定頂點(diǎn) SetEdge()：在兩個(gè)頂點(diǎn)之間添加指定權(quán)值的邊或弧 GetEdge()：獲取兩個(gè)頂點(diǎn)之間的邊 DelEdge

6、()：刪除兩個(gè)頂點(diǎn)之間的邊或弧 GetNumOfVertex()：獲取鄰接矩陣頂點(diǎn)數(shù) GetNumOfEdge()：獲取鄰接矩陣邊或弧的數(shù)目 GetIndex()：獲取指定頂點(diǎn)在數(shù)組中的索引 IsEdge()：判斷兩個(gè)頂點(diǎn)之間是否存在邊或弧 IsNode()：判斷指定結(jié)點(diǎn)是否是圖的頂點(diǎn)認(rèn)識(shí)圖認(rèn)識(shí)圖識(shí)別圖的基本操作識(shí)別圖的基本操作圖的基本操作有以下幾種：圖的基本操作有以下幾種：解決圖的編程問題解決圖的編程問題數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)(C#語(yǔ)言版語(yǔ)言版)2021/3/98鄰接矩陣(Adjacentcy Matrix)是用兩個(gè)數(shù)組來表示圖，一個(gè)數(shù)組是一維數(shù)組，存儲(chǔ)圖中的頂點(diǎn)信息，一個(gè)數(shù)組是二維數(shù)組，即矩陣，

7、存儲(chǔ)頂點(diǎn)之間相鄰的信息，也就是邊（或?。┑男畔?。如果圖中有n個(gè)頂點(diǎn)，你需要大小為nn的二維數(shù)組來表示圖。用C#語(yǔ)言表示鄰接矩陣的代碼 參見P190頁(yè)用鄰接矩陣解決圖的編程問題用鄰接矩陣解決圖的編程問題 用鄰接矩陣表示圖用鄰接矩陣表示圖 對(duì)鄰接矩陣進(jìn)行操作參見P191頁(yè)代碼。解決圖的編程問題解決圖的編程問題數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)(C#語(yǔ)言版語(yǔ)言版)2021/3/99鄰接表的存儲(chǔ)方法是一種順序存儲(chǔ)與鏈?zhǔn)酱鎯?chǔ)相結(jié)合的存儲(chǔ)方法，順序存儲(chǔ)部分用來保存圖中頂點(diǎn)的信息，鏈?zhǔn)酱鎯?chǔ)部分用來保存圖中邊（或?。┑男畔?。具體的做法是：使用一個(gè)一維數(shù)組，其中每個(gè)數(shù)組元素包含兩個(gè)域，其結(jié)構(gòu)如右圖所示。 其中 頂點(diǎn)域（data）

8、：存放與頂點(diǎn)有關(guān)的信息；頭指針域（firstadj）：存放與該頂點(diǎn)相鄰接的所有頂點(diǎn)組成的單鏈表的頭指針 用鄰接表解決圖的編程問題用鄰接表解決圖的編程問題 用鄰接表表示圖用鄰接表表示圖 鄰接單鏈表中每個(gè)結(jié)點(diǎn)表示依附于該頂點(diǎn)的一條邊，稱作邊結(jié)點(diǎn)，邊結(jié)點(diǎn)的結(jié)構(gòu)如右圖所示。 其中鄰接點(diǎn)域(adjvex)：指示與頂點(diǎn)鄰接點(diǎn)在圖中的位置，對(duì)應(yīng)著一維數(shù)組中的序號(hào)，對(duì)于有向圖，存放的是該邊結(jié)點(diǎn)所表示的弧的弧頭頂點(diǎn)在一維數(shù)組中的序號(hào)；數(shù)據(jù)域(info)：存儲(chǔ)邊或弧相關(guān)的信息，如權(quán)值等，當(dāng)圖中邊（或?。┎缓行畔r(shí)，該域可以省略。鏈域(nextadj)：指向依附于該頂點(diǎn)的下一個(gè)邊結(jié)點(diǎn)的指針。無向圖鄰接表的鄰接表結(jié)

9、點(diǎn)類的代碼參見P197頁(yè) 。解決圖的編程問題解決圖的編程問題數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)(C#語(yǔ)言版語(yǔ)言版)2021/3/910用鄰接表解決圖的編程問題用鄰接表解決圖的編程問題 用鄰接表表示圖用鄰接表表示圖 （舉例）（舉例）對(duì)鄰接表進(jìn)行操作的代碼參見P199頁(yè) 。解決圖的編程問題解決圖的編程問題數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)(C#語(yǔ)言版語(yǔ)言版)2021/3/9119.4解決圖的遍歷問題解決圖的遍歷問題深度優(yōu)先搜索深度優(yōu)先搜索 1.理解深度優(yōu)先搜索算法理解深度優(yōu)先搜索算法 從圖的某一頂點(diǎn)x出發(fā)，訪問x，然后遍歷任何一個(gè)與x相鄰的未被訪問的頂點(diǎn)y，再遍歷任何一個(gè)與y相鄰的未被訪問的頂點(diǎn)z，如此下去，直到到達(dá)一個(gè)所有鄰接點(diǎn)都

10、被訪問的頂點(diǎn)為止。然后依次回退到尚有鄰接點(diǎn)未被訪問過的頂點(diǎn)，重復(fù)上述過程，直到圖中的全部頂點(diǎn)都被訪問過為止。 對(duì)圖進(jìn)行深度優(yōu)先遍歷。深度優(yōu)先遍歷背后基于堆棧，有2種形式: 第一種是程序中顯示構(gòu)造堆棧，利用壓棧出棧操作實(shí)現(xiàn);第二種是利用遞歸函數(shù)調(diào)用，基于遞歸程序棧實(shí)現(xiàn)。本章介紹壓棧和出棧的操作。解決圖的編程問題解決圖的編程問題數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)(C#語(yǔ)言版語(yǔ)言版)2021/3/912v1 將起始頂點(diǎn)v1壓入棧。9.4解決圖的遍歷問題解決圖的遍歷問題深度優(yōu)先搜索深度優(yōu)先搜索 解決圖的編程問題解決圖的編程問題數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)(C#語(yǔ)言版語(yǔ)言版)2021/3/913v1將頂點(diǎn)v1彈出棧訪問 v1在棧中壓

11、入所有與v1相鄰接的未訪問頂點(diǎn)v1Visited:9.4解決圖的遍歷問題解決圖的遍歷問題深度優(yōu)先搜索深度優(yōu)先搜索 解決圖的編程問題解決圖的編程問題數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)(C#語(yǔ)言版語(yǔ)言版)2021/3/914v4從棧中彈出頂點(diǎn) v1訪問 v1在棧中壓入所有與v1相鄰接的未訪問頂點(diǎn)v1Visited:v29.4解決圖的遍歷問題解決圖的遍歷問題深度優(yōu)先搜索深度優(yōu)先搜索 解決圖的編程問題解決圖的編程問題數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)(C#語(yǔ)言版語(yǔ)言版)2021/3/915Visited:從棧中彈出頂點(diǎn) v2訪問 v2在棧中壓入所有與v2相鄰接的未訪問頂點(diǎn)v1 v2v4v29.4解決圖的遍歷問題解決圖的遍歷問題深度優(yōu)先搜

12、索深度優(yōu)先搜索 解決圖的編程問題解決圖的編程問題數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)(C#語(yǔ)言版語(yǔ)言版)2021/3/916Visited:從棧中彈出頂點(diǎn) v2訪問 v2在棧中壓入所有與v2相鄰接的未訪問頂點(diǎn)v1 v2v3v6v49.4解決圖的遍歷問題解決圖的遍歷問題深度優(yōu)先搜索深度優(yōu)先搜索 解決圖的編程問題解決圖的編程問題數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)(C#語(yǔ)言版語(yǔ)言版)2021/3/917Visited:從棧中彈出頂點(diǎn) v3訪問v3在棧中壓入所有與v3相鄰接的未訪問頂點(diǎn)v1 v2 v3有與v3相鄰接的未訪問頂點(diǎn)v6v3v49.4解決圖的遍歷問題解決圖的遍歷問題深度優(yōu)先搜索深度優(yōu)先搜索 解決圖的編程問題解決圖的編程問題數(shù)據(jù)結(jié)

13、構(gòu)數(shù)據(jù)結(jié)構(gòu)(C#語(yǔ)言版語(yǔ)言版)2021/3/918Visited:從棧中彈出頂點(diǎn) v3訪問v3在棧中壓入所有與v3相鄰接的未訪問頂點(diǎn)v1 v2 v3有與v3相鄰接的未訪問頂點(diǎn)v6v5v49.4解決圖的遍歷問題解決圖的遍歷問題深度優(yōu)先搜索深度優(yōu)先搜索 解決圖的編程問題解決圖的編程問題數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)(C#語(yǔ)言版語(yǔ)言版)2021/3/919Visited:從棧中彈出頂點(diǎn) v5訪問v5在棧中壓入所有與v5相鄰接的未訪問頂點(diǎn)v1 v2 v3v5v6v49.4解決圖的遍歷問題解決圖的遍歷問題深度優(yōu)先搜索深度優(yōu)先搜索 v5解決圖的編程問題解決圖的編程問題數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)(C#語(yǔ)言版語(yǔ)言版)2021/3/9

14、20Visited:從棧中彈出頂點(diǎn) v6訪問v6在棧中壓入所有與v6相鄰接的未訪問頂點(diǎn)v1 v2 v3 v5 v6v6v49.4解決圖的遍歷問題解決圖的遍歷問題深度優(yōu)先搜索深度優(yōu)先搜索 解決圖的編程問題解決圖的編程問題數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)(C#語(yǔ)言版語(yǔ)言版)2021/3/921Visited:從棧中彈出頂點(diǎn) v4訪問v4在棧中壓入所有與v4相鄰接的未訪問頂點(diǎn)v1 v2 v3 v5 v6 v4v49.4解決圖的遍歷問題解決圖的遍歷問題深度優(yōu)先搜索深度優(yōu)先搜索 解決圖的編程問題解決圖的編程問題數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)(C#語(yǔ)言版語(yǔ)言版)2021/3/922Visited:?，F(xiàn)在是空的因此，遍歷完成v1 v2

15、v3 v5 v6 v49.4解決圖的遍歷問題解決圖的遍歷問題深度優(yōu)先搜索深度優(yōu)先搜索 解決圖的編程問題解決圖的編程問題數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)(C#語(yǔ)言版語(yǔ)言版)2021/3/923盡管上述算法提供了一個(gè)簡(jiǎn)單和常用的方法來遍歷圖，但是，如果圖不是連接的，算法將不能正確工作。在這樣的情況下，你將不能夠從單個(gè)起始頂點(diǎn)開始遍歷所有頂點(diǎn)。 9.4解決圖的遍歷問題解決圖的遍歷問題深度優(yōu)先搜索深度優(yōu)先搜索 解決圖的編程問題解決圖的編程問題數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)(C#語(yǔ)言版語(yǔ)言版)2021/3/924為了解決這個(gè)問題，你需要對(duì)圖中所有未訪問頂點(diǎn)重復(fù)執(zhí)行上述算法。 對(duì)圖中每個(gè)頂點(diǎn)v重復(fù)步驟2 如果v未被訪問： a. 調(diào)用

16、DFS(v)9.4解決圖的遍歷問題解決圖的遍歷問題深度優(yōu)先搜索深度優(yōu)先搜索 解決圖的編程問題解決圖的編程問題數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)(C#語(yǔ)言版語(yǔ)言版)2021/3/9259.4解決圖的遍歷問題解決圖的遍歷問題廣度優(yōu)先搜索廣度優(yōu)先搜索 2.理解廣度優(yōu)先搜索算法理解廣度優(yōu)先搜索算法 圖的廣度優(yōu)先搜索是從圖的某個(gè)頂點(diǎn)x出發(fā)，訪問x。然后訪問與x相鄰接的所有未被訪問的頂點(diǎn)x1,x2,.,xn；接著再依次訪問與x1,x2,.,xn相鄰接的未被訪問過的所有頂點(diǎn)。依此類推，直至圖的每個(gè)頂點(diǎn)都被訪問。解決圖的編程問題解決圖的編程問題數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)(C#語(yǔ)言版語(yǔ)言版)2021/3/926訪問 v1將v1 插入隊(duì)列v

17、1v19.4解決圖的遍歷問題解決圖的遍歷問題廣度優(yōu)先搜索廣度優(yōu)先搜索 解決圖的編程問題解決圖的編程問題數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)(C#語(yǔ)言版語(yǔ)言版)2021/3/927從隊(duì)列中刪除頂點(diǎn) v1 訪問與v1相鄰接的所有未訪問頂點(diǎn)并將它們插入隊(duì)列v1v1Visited:9.4解決圖的遍歷問題解決圖的遍歷問題廣度優(yōu)先搜索廣度優(yōu)先搜索 解決圖的編程問題解決圖的編程問題數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)(C#語(yǔ)言版語(yǔ)言版)2021/3/928從隊(duì)列中刪除頂點(diǎn) v1 訪問與v1相鄰接的所有未訪問頂點(diǎn)并將它們插入隊(duì)列v2v1 v2 v4v49.4解決圖的遍歷問題解決圖的遍歷問題廣度優(yōu)先搜索廣度優(yōu)先搜索 解決圖的編程問題解決圖的編程問題數(shù)

18、據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)(C#語(yǔ)言版語(yǔ)言版)2021/3/929從隊(duì)列中刪除頂點(diǎn) v2訪問與v2相鄰接的所有未訪問頂點(diǎn)并將它們插入隊(duì)列v2v1 v2 v4v49.4解決圖的遍歷問題解決圖的遍歷問題廣度優(yōu)先搜索廣度優(yōu)先搜索 解決圖的編程問題解決圖的編程問題數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)(C#語(yǔ)言版語(yǔ)言版)2021/3/930從隊(duì)列中刪除頂點(diǎn) v4 訪問與v4相鄰接的所有未訪問頂點(diǎn)并將它們插入隊(duì)列v1 v2 v4v4v3v3v6v6v5v59.4解決圖的遍歷問題解決圖的遍歷問題廣度優(yōu)先搜索廣度優(yōu)先搜索 解決圖的編程問題解決圖的編程問題數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)(C#語(yǔ)言版語(yǔ)言版)2021/3/931從隊(duì)列中刪除頂點(diǎn) v3 訪問與v

19、3相鄰接的所有未訪問頂點(diǎn)并將它們插入隊(duì)列v1 v2 v4 v3v3v6v6v5v5v3沒有任何未訪問的鄰接頂點(diǎn)9.4解決圖的遍歷問題解決圖的遍歷問題廣度優(yōu)先搜索廣度優(yōu)先搜索 解決圖的編程問題解決圖的編程問題數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)(C#語(yǔ)言版語(yǔ)言版)2021/3/932從隊(duì)列中刪除頂點(diǎn) v6 訪問與v6相鄰接的所有未訪問頂點(diǎn)并將它們插入隊(duì)列v1 v2 v4 v3v6v6v5v5v3沒有任何未訪問的鄰接頂點(diǎn)9.4解決圖的遍歷問題解決圖的遍歷問題廣度優(yōu)先搜索廣度優(yōu)先搜索 解決圖的編程問題解決圖的編程問題數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)(C#語(yǔ)言版語(yǔ)言版)2021/3/933從隊(duì)列中刪除頂點(diǎn) v5 訪問與v5相鄰接的所有未

20、訪問頂點(diǎn)并將它們插入隊(duì)列v1 v2 v4 v3v6 v5v5v6沒有任何未訪問的鄰接頂點(diǎn)9.4解決圖的遍歷問題解決圖的遍歷問題廣度優(yōu)先搜索廣度優(yōu)先搜索 解決圖的編程問題解決圖的編程問題數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)(C#語(yǔ)言版語(yǔ)言版)2021/3/934隊(duì)列現(xiàn)在是空的因此，遍歷完成v1 v2 v4 v3v6 v5v5沒有任何未訪問的鄰接頂點(diǎn)9.4解決圖的遍歷問題解決圖的遍歷問題廣度優(yōu)先搜索廣度優(yōu)先搜索 解決圖的編程問題解決圖的編程問題數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)(C#語(yǔ)言版語(yǔ)言版)2021/3/935盡管上述算法提供了一個(gè)簡(jiǎn)單和方便的遍歷圖的方法，但是，如果圖不是連接的，算法將不能正確工作。在這樣的情況中，你將不能從單

21、個(gè)開始頂點(diǎn)遍歷所有頂點(diǎn)。9.4解決圖的遍歷問題解決圖的遍歷問題廣度優(yōu)先搜索廣度優(yōu)先搜索 解決圖的編程問題解決圖的編程問題數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)(C#語(yǔ)言版語(yǔ)言版)2021/3/936為了解決這個(gè)問題，你需要對(duì)圖中的未訪問頂點(diǎn)重復(fù)執(zhí)行這個(gè)算法。 為圖中每個(gè)頂點(diǎn)V重復(fù)步驟2。 如果 v 未被訪問： a. 調(diào)用BFS(v)9.4解決圖的遍歷問題解決圖的遍歷問題廣度優(yōu)先搜索廣度優(yōu)先搜索 解決圖的編程問題解決圖的編程問題數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)(C#語(yǔ)言版語(yǔ)言版)2021/3/937圖的最短路徑問題圖的最短路徑問題 Dijkstra算法的引入算法的引入 Dijkstra算法的基本思想是：算法的基本思想是： 設(shè)置兩個(gè)頂

22、點(diǎn)集合T和S，集合S中存放己經(jīng)找到最短路徑的頂點(diǎn)，集合T中存放當(dāng)前還未找到最短路徑的頂點(diǎn)。初始狀態(tài)時(shí)，集合S中只包含源點(diǎn)v0，然后不斷從集合T中選取到源點(diǎn)v0路徑長(zhǎng)度最短的頂點(diǎn)w加入集合S，集合S中每加入一個(gè)新的頂點(diǎn)w，都要修改頂點(diǎn)v0到集合T中剩余頂點(diǎn)的最短路徑長(zhǎng)度值，集合T中各頂點(diǎn)新的最短路徑長(zhǎng)度值為原來最短路徑長(zhǎng)度值與頂點(diǎn)w的最短路徑長(zhǎng)度加上w到該頂點(diǎn)的路徑長(zhǎng)度值中的較小值。此過程不斷重復(fù)，直到集合T的頂點(diǎn)全部加入集合S為止。解決圖的編程問題解決圖的編程問題數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)(C#語(yǔ)言版語(yǔ)言版)2021/3/938圖的最短路徑問題圖的最短路徑問題 分析高速公路交通網(wǎng)的最短路徑分析高速公路交

23、通網(wǎng)的最短路徑 下面用Dijkstra算法解決高速公路最短路徑的問題?，F(xiàn)在假設(shè)高速公路交通網(wǎng)采用鄰接矩陣作為存儲(chǔ)結(jié)構(gòu)。若鄰接矩陣為matrix，并規(guī)定：用Dijkstra算法來確定從城市A到其他城市的最短踐離。Dijkstra算法的步驟 參見教材P212頁(yè)解決圖的編程問題解決圖的編程問題數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)(C#語(yǔ)言版語(yǔ)言版)2021/3/939finaldistance110000090150180圖的最短路徑問題圖的最短路徑問題 分析高速公路交通網(wǎng)的最短路徑分析高速公路交通網(wǎng)的最短路徑 ABCDEF012345解決圖的編程問題解決圖的編程問題數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)(C#語(yǔ)言版語(yǔ)言版)2021/3/9

24、40finaldistance110000090150140180圖的最短路徑問題圖的最短路徑問題 分析高速公路交通網(wǎng)的最短路徑分析高速公路交通網(wǎng)的最短路徑 ABCDEF012345解決圖的編程問題解決圖的編程問題數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)(C#語(yǔ)言版語(yǔ)言版)2021/3/941finaldistance110100090150140180圖的最短路徑問題圖的最短路徑問題 分析高速公路交通網(wǎng)的最短路徑分析高速公路交通網(wǎng)的最短路徑 ABCDEF012345解決圖的編程問題解決圖的編程問題數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)(C#語(yǔ)言版語(yǔ)言版)2021/3/942finaldistance110100090150140250180圖的最短路徑問題圖的最短路徑問題 分析高速公路交通網(wǎng)的最短路徑分析高速公路交通網(wǎng)的最短路徑 ABCDEF012345解決圖的編程問題解決圖的編程問題數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)(C#語(yǔ)言版語(yǔ)言版)2021/3/943finaldistance111100090150140250180圖的最短路徑問題圖的最短路徑問題 分析高速公路交通網(wǎng)的最短路徑分析高速公路交通網(wǎng)的最短路徑 ABCDE