數(shù)據(jù)結構與算法（Java語言版）課件 第13章 圖論

第13章圖論2024/11/912024/11/92

13.1無向圖2024/11/93

⒈無向圖的定義2024/11/9413.1無向圖

⒈無向圖的定義2024/11/9513.1無向圖

2鄰接點

2024/11/9613.1無向圖3.路徑

2024/11/9713.1無向圖4.連通圖

13.2有向圖2024/11/98⒈有向圖的定義

2024/11/9913.2有向圖

⒈有向圖的定義

2024/11/91013.2有向圖2鄰接點

2024/11/91113.2無向圖3.路徑

2024/11/91213.2有向圖4.強連通圖

13.3網(wǎng)絡2024/11/913

2024/11/91413.3網(wǎng)絡刻畫北京，廣州，成都和上海四個城市之間的民航航線，航線之間的權重是航線距離。2024/11/91513.3網(wǎng)絡刻畫北京，廣州，成都和上海四個城市之間的民航航線，航線之間的權重是航線的票價（往返的票價不盡相同）。13.4圖的存儲2024/11/9161.鄰接矩陣

13.4圖的存儲2024/11/9171.鄰接矩陣

2024/11/91813.4圖的存儲例子1Example13_1.javaGraphByMatrix.java例子1中的GraphByMatrix類使用鄰接矩陣存儲圖或網(wǎng)絡的邊。例子1的主類Example13_1使用GraphByMatrix類演示了無向圖、有向圖和有向網(wǎng)絡使用鄰接矩陣存儲邊.13.4圖的存儲2024/11/9191.鄰接表

2024/11/92013.4圖的存儲例子2Example13_2.javaGraphByLinkedList.java例子2中的GraphByLinkedList類使用鄰接鏈表存儲圖或網(wǎng)絡的邊。例子2的主類Example13_2使用GraphByLinkedList類演示了無向圖、有向圖和有向網(wǎng)絡使用鄰接鏈表存儲邊.13.4圖的遍歷2024/11/921

13.4圖的遍歷2024/11/922廣度搜索（BFS）則是從起點開始，逐層訪問所有路徑可達到的頂點，一層一層地往外擴展（廣度優(yōu)先），直到所有路徑可達到的頂點都被訪問到，就結束此次遍歷過程。如果圖中仍然有沒訪問過的頂點，就在沒訪問過的頂點中，選擇一個頂點重新開始遍歷。廣度優(yōu)先搜索一直到圖中再也沒有可訪問的頂點，就結束搜索過程。廣度優(yōu)先搜索的算法中可以用隊列（Deque）這種數(shù)據(jù)結構體現(xiàn)廣度優(yōu)先.2024/11/92313.5圖的遍歷例子3Example13_3.javaGraphDFS.java1.深度優(yōu)先搜索（DFS）算法DFS算法描述如下。①檢查是否已經(jīng)訪問了全部的頂點，如果已經(jīng)訪問了全部的頂點，進行③，否則，將一個不曾訪問的頂點壓入棧，進行②。②如果棧是空，進行①，否則進行彈棧，把彈出的頂點標記為訪問過的頂點，然后把彈出的頂點的鄰接頂點壓入棧（體現(xiàn)深度優(yōu)先），但不再對訪問過的頂點進行壓棧操作，再進行②。③算法結束。例子3中的GraphDFS類封裝了DFS算法。Vertex.java2024/11/92413.5圖的遍歷例子4Example13_4.javaGraphBFS.java2.廣度優(yōu)先搜索（BFS）算法例子4中的GraphBFS類封裝了BFS算法。Vertex.javaBFS算法描述如下：①檢查是否已經(jīng)訪問了全部的頂點，如果已經(jīng)訪問了全部的頂點，進行③，否則，將一個不曾訪問的頂點入列，進行②。②如果隊列是空，進行①，否則進行出列操作，把出列的頂點標記為訪問過的頂點，然后把出列的頂點的鄰接頂點入列（體現(xiàn)廣度優(yōu)先），但不再對訪問過的頂點進行入列操作，再進行②。③算法結束。13.6測試連通性2024/11/925從任意頂點開始遍歷圖中的頂點，方法結束后，使得圖的頂點都可以被訪問了一次，那么該圖就是連通圖或強連通圖。如果存在某個頂點vertex，使得graphBFS(vertex)或graphDFS(vertex)執(zhí)行完畢后，圖中還有某些頂點未被訪問，那就說明頂點vertex和這些未被訪問頂點之間沒有路徑相連接，因此，圖就不是連通圖。2024/11/92613.6測試圖的連通性例子5Example13_5.javaTestConnection.java例子5中的TestConnection類的isConnection(GraphDFSgraph)方法和isConnection(GraphBFSgraph)方法，分別借助例子3和例子4中的GraphDFS類和GraphBFS中的深度優(yōu)先搜索（graphDFS(Vertexvertex)）和廣度優(yōu)先搜索（graphBFS(Vertexvertex)）測試圖graph是否是連通圖。13.7最短路徑2024/11/927

13.7最短路徑2024/11/928

13.7最短路徑2024/11/929

13.7最短路徑2024/11/930

13.7最短路徑2024/11/9312024/11/93213.7最短路徑取第0個頂點，第1次迭代得到：2024/11/93313.7最短路徑取第1個頂點，第2次迭代得到：2024/11/93413.7最短路徑取第2個頂點，第3次迭代得到：2024/11/93513.7最短路徑取第3個頂點，第4次迭代得到：2024/11/93613.7最短路徑取第3個頂點，第4次迭代得到：2024/11/93713.7最短路徑

2024/11/93813.7最短路徑例子6Example13_6.javaFloyd.java例子6中的Floyd類的floyd(int[][]graph)方法是經(jīng)典的Floyd最短路徑算法。13.8最小生成樹2024/11/939

13.8最小生成樹2024/11/940一個網(wǎng)絡的可能有很多生成樹，人們關心的往往是最小生成樹。最小生成樹是生成樹中邊的權值總和最小的某個生成樹（可能有多個生成樹的權值總和相同，同時也是最小之一）。如果網(wǎng)絡中的權值互不相同，那么最小生成樹一定是唯一的。13.8最小生成樹2024/11/941Prim給出MST算法（1957年由美國計算機科學家普里姆獨立發(fā)現(xiàn)），稱作Prim算法。該算法可以從網(wǎng)絡的任何一個頂點開始，得到最小生成樹。