資料結構--圖的JAVA實作(下)

在上一篇文章中記錄了如何實作圖的鄰接表。本文借助上一篇文章實作的鄰接表來表示一個有向無環圖。

1，概述

圖的實作與鄰接表的實作最大的不同就是，圖的實作需要定義一個資料結構來存儲所有的頂點以及能夠對圖進行什麼操作，而鄰接表的實作重點關注的圖中頂點的實作，即怎麼定義JAVA類來表示頂點，以及能夠對頂點進行什麼操作。

為了存儲圖中所有的頂點，定義了一個Map<key, value>，實際實作為LinkedHashMap<T, VertexInterface<T>>，key 為頂點的辨別，key 是泛型，這樣就可以用任意資料類型來辨別頂點了，如String、Integer……

value 當然就是表示頂點的類了，因為我們需要存儲的是頂點嘛。即value 為 VertexInterface<T> 。這裡為什麼不用List而用Map來存儲頂點呢？用Map的好處就是友善查詢頂點，即可以用頂點辨別來查找頂點。這也是為了友善後面實作圖的DFS、BFS 等算法而考慮的。

此外，還定義了一個整型變量 edgeCount 用來儲存圖中邊的數目，這也是必要的。讨論一個圖，當然要有圖的頂點，由Map儲存，頂點數目可以通過 Map.size() 方法獲得；也要有邊，而邊已經隐含在Vertex.java中了(具體參考上一篇文章），是以這裡隻定義一個儲存圖中邊的總數的變量即可。圖的定義部分代碼如下：

1 public class DirectedGraph<T> implements GraphInterface<T>,java.io.Serializable{
 2 
 3     private static final long serialVersionUID = 1L;
 4 
 5     private Map<T, VertexInterface<T>> vertices;//map 對象用來儲存圖中的所有頂點.T 是頂點辨別,VertexInterface為頂點對象
 6     private int edgeCount;//記錄圖中 邊的總數
 7     
 8     public DirectedGraph() {
 9         vertices = new LinkedHashMap<>();//按頂點的插入順序儲存頂點
10     }

2，圖的基本操作

這裡的基本操作不是對圖進行DFS、BFS、拓撲排序、求最短路徑……而是一系列的如何構造圖的方法，這些方法是實作圖的周遊、求最短路徑、拓撲排序的基礎。

在 1 中說明了用Map儲存圖的頂點，那麼如何把頂點對象添加到Map中呢？

1 public void addVertex(T vertexLabel) {
2         //若頂點相同時,新插入的頂點将覆寫原頂點,這是由LinkedHashMap的put方法決定的
3         //每添加一個頂點,會建立一個LinkedList清單,它存儲該頂點對應的鄰接點,或者說是與該頂點相關聯的邊
4         vertices.put(vertexLabel, new Vertex(vertexLabel));//new Vertex 對象,會建立一個LinkedList,該LinkedList用來表示該頂點的鄰接表
5     }

如何表示圖中兩個頂點之間的邊呢？

1 public boolean addEdge(T begin, T end, double edgeWeight) {
 2         boolean result = false;
 3         VertexInterface<T> beginVertex = vertices.get(begin);//獲得表示邊的起始頂點
 4         VertexInterface<T> endVertex = vertices.get(end);//獲得表示 邊的終點
 5         
 6         if(beginVertex != null && endVertex != null)
 7             result = beginVertex.connect(endVertex, edgeWeight);//起始點與終點連接配接,即成一條邊
 8         if(result)
 9             edgeCount++;
10         return result;//當添加重複邊時會傳回 false
11     }

3，圖的相關算法的JAVA實作及分析

正如上一篇文章中的總結提到：算法的實作依賴于采用了何種資料結構，依賴于資料結構--圖的具體實作。由于這裡的資料結構--圖的實作與《算法導論》中描述的圖的資料結構有一點差别，如：沒有定義表示圖的通路狀态的"白色頂點、灰色頂點、黑色頂點"，是以算法的實作也與《算法導論》中算法的實作有輕微的差别。

對于不帶權的圖而言(邊上沒有權值) 廣度優先周遊算法與最短路徑算法很相似，對廣度優先周遊算法稍加修改，就可以變成最短路徑算法了。

可參考：無向圖的最短路徑算法JAVA實作和帶權圖的最短路徑算法(Dijkstra)實作

了解：

深度優先周遊算法與拓撲算法也很相似，拓撲排序算法的實作可以借助深度優先周遊算法。

具體參考《算法導論》

①廣度優先周遊算法：若頂點A先于頂點B被通路，則頂點A的鄰接點也先于頂點B的鄰接點被通路。特點：先把起始頂點附近的頂點通路完，再通路遠處的頂點。

在廣度優先周遊算法的具體實作中，需要兩個隊列。一個輔助周遊，儲存周遊過程中遇到的頂點，當通路完成了某個頂點A後，将A出隊列，緊接着将A的所有鄰接點都入隊列，并通路。

另一個隊列用來儲存通路的順序，另一個隊列的頂點入隊順序就是圖的廣度周遊順序，是以，該隊列保持與前一個隊列的頂點入隊操作一緻。由于前一個隊列是輔助周遊的，它有出隊的操作，它就不能記錄整個頂點的通路序列了，是以才需要一個儲存通路順序的隊列。當整個過程周遊完成後，将儲存通路順序的隊列進行出隊操作，即可得到整個圖的廣度優先周遊的順序了。具體算法如下：

1 public Queue<T> getBreadthFirstTraversal(T origin) {//origin 辨別周遊的初始頂點
 2         resetVertices();//将頂點的必要資料域初始化,複雜度為O(V)
 3         Queue<VertexInterface<T>> vertexQueue = new LinkedList<>();//儲存周遊過程中遇到的頂點,它是輔助周遊的,有出隊列操作
 4         Queue<T> traversalOrder = new LinkedList<>();//儲存周遊過程中遇到的 頂點辨別--整個圖的周遊順序就儲存在其中,無出隊操作
 5         VertexInterface<T> originVertex = vertices.get(origin);//根據頂點辨別獲得初始周遊頂點
 6         originVertex.visit();//通路該頂點
 7         traversalOrder.offer(originVertex.getLabel());
 8         vertexQueue.offer(originVertex);
 9         
10         while(!vertexQueue.isEmpty()){
11             VertexInterface<T> frontVertex = vertexQueue.poll();//出隊列,poll()在隊列為空時傳回null
12             Iterator<VertexInterface<T>> neighbors = frontVertex.getNeighborInterator();
13             while(neighbors.hasNext())//對于 每個頂點都周遊了它的鄰接表,即周遊了所有的邊,複雜度為O(E)
14             {
15                 VertexInterface<T> nextNeighbor = neighbors.next();
16                 if(!nextNeighbor.isVisited()){
17                     nextNeighbor.visit();//廣度優先周遊未通路的頂點
18                     traversalOrder.offer(nextNeighbor.getLabel());
19                     vertexQueue.offer(nextNeighbor);//将該頂點的鄰接點入隊列
20                 }
21             }//end inner while
22         }//end outer while
23         return traversalOrder;
24     }

從中可以看出，該算法的時間複雜度為--周遊之前，給每個頂點進行初始化時需要周遊所有頂點V，在周遊過程中需要判斷頂點的鄰接點是否被周遊，也即周遊該頂點的鄰接表，鄰接表代表的實質是邊，邊總數為E，故總的時間複雜度為O(V+E)，空間複雜度為O(V)--輔助隊列的長度為頂點的長度

②最短路徑算法：在邊不帶權值的圖中求頂點A到頂點B的最短路徑--其實就是頂點A到頂點B之間的最少邊的條數

調用最短路徑算法之前，首先要确定一個初始頂點，圖中其他頂點的路徑長度都是相對于初始頂點而言的。求兩個頂點間最短路徑，其實并不是找出兩個頂點間所有的路徑長度，然後取最小值。而是借助于廣度優先周遊算法，将每個頂點相對于初始頂點的最短路徑長度儲存在 cost 屬性中，廣度優先算法的性質保證了頂點間的路徑是最短的。在最短路徑的計算中，設初始點為 i，頂點A相對于初始點的最短路徑長度為 length,則頂點A的鄰接點相對于初始頂點 i 的最短長度為 length+1.

是以，執行最短路徑算法後，實際上求得了圖中所有頂點相對于初始頂點的最短路徑。

初始頂點的路徑長度為0（每個頂點有一個 cost 屬性---見上一文章分析，由 cost 來記錄每個頂點相對于初始頂點的路徑長度)。是以，獲得某頂點的最短路徑隻需要調用它的getCost方法即可。

最短路徑算法的代碼如下，可以看出它和廣度優先算法的代碼非常的相似，其實就是廣度優先算法的應用而已。

1     public int getShortestPath(T begin, T end, Stack<T> path) {
 2         resetVertices();//圖中頂點的初始化
 3         boolean done = false;//标記整個周遊過程是否完成
 4         Queue<VertexInterface<T>> vertexQueue = new LinkedList<>();//輔助隊列,儲存周遊過程中遇到的頂點
 5         VertexInterface<T> beginVertex = vertices.get(begin);//獲得起始頂點
 6         VertexInterface<T> endVertex = vertices.get(end);//獲得終點,求起始頂點到終點的最短路徑
 7         
 8         beginVertex.visit();
 9         vertexQueue.offer(beginVertex);//起始頂點入隊列
10         //Assertion: resetVertices() 已經對 beginVertex 執行了 setCost(0)
11         
12         while(!done && !vertexQueue.isEmpty()){//while循環完成後,實際上求得了圖中所有頂點相對于初始點的 cost 屬性值
13             VertexInterface<T> frontVertex = vertexQueue.poll();
14             Iterator<VertexInterface<T>> neighbors = frontVertex.getNeighborInterator();
15             while(!done && neighbors.hasNext()){//計算 frontVertex的所有鄰接頂點的 路徑長度
16                 VertexInterface<T> nextNeighbor = neighbors.next();
17                 if(!nextNeighbor.isVisited()){
18                     nextNeighbor.visit();
19                     nextNeighbor.setPredecessor(frontVertex);//設定frontVertex 的前驅頂點
20                     nextNeighbor.setCost(frontVertex.getCost() + 1);//該頂點的路徑長度是 它的前驅頂點的路徑長度+1
21                     vertexQueue.offer(nextNeighbor);
22                 }//end if
23                 
24                 if(nextNeighbor.equals(endVertex))
25                     done = true;
26             }//end inner while
27         }//end outer while. and traverse over
28         
29         int pathLength = (int)endVertex.getCost();//初始頂點的 cost為 0,每個頂點的 cost 屬性記錄了它相對于初始頂點的最短長度
30         path.push(endVertex.getLabel());
31         
32         VertexInterface<T> vertex = endVertex;
33         while(vertex.hasPredecessor()){
34             vertex = vertex.getPredecessor();
35             path.push(vertex.getLabel());
36         }
37         return pathLength;
38     }

③深度優先周遊算法：

在深度優先周遊中，需要兩個棧，這裡可以看出深度優先周遊帶有遞歸的性質。一個棧用來輔助周遊，即用來儲存周遊過程中裡面的頂點，另一個棧用來儲存周遊的順序。之是以另外需要一個棧來儲存周遊的順序的原因與廣度優先周遊中需要用另一個隊列來儲存周遊順序的原因相同。當深度優先周遊到某個頂點時，若該頂點的所有鄰接點均已經被通路，則發生回溯，即傳回去周遊該頂點的前驅頂點的未被通路的某個鄰接點。

深度優先周遊的代碼與廣度優先周遊的代碼很大的一個不同就是，在while 循環裡面，當取出棧頂/隊頭頂點時，深度優先是用一個 if 語句來執行邏輯，而廣度優先則是用一個 while 循環來執行邏輯。

這是因為：對于深度優先而言，通路了頂點A 時，緊接着隻需要找到頂點A 的一個未被通路的鄰接點，再通路該鄰接點即可。而對于廣度優先，通路了頂點A 時，就是要尋找頂點A的所有未被通路的鄰接點，再通路所有的這些鄰接點。

代碼對比如下：

1 while(!vertexStack.isEmpty()){
 2             VertexInterface<T> topVertex = vertexStack.peek();
 3             //找到該頂點的一個未被通路的鄰接點,從該鄰接點出發又去周遊鄰接點的鄰接點
 4             VertexInterface<T> nextNeighbor = topVertex.getUnvisitedNeighbor();
 5             if(nextNeighbor != null){
 6                 nextNeighbor.visit();
 7                 //由于用的是if,在這裡push鄰接點後,下一次while循環pop的是該鄰接點,然後又獲得它的鄰接點,---DFS
 8                 vertexStack.push(nextNeighbor);
 9                 traversalOrder.offer(nextNeighbor.getLabel());
10             }
11             else
12                 vertexStack.pop();//當某頂點的所有鄰接點都被通路了時,直接将該頂點pop,這樣下一次while pop 時就回溯到前一個頂點

1 while(!vertexQueue.isEmpty()){
 2             VertexInterface<T> frontVertex = vertexQueue.poll();//出隊列,poll()在隊列為空時傳回null
 3             Iterator<VertexInterface<T>> neighbors = frontVertex.getNeighborInterator();
 4             while(neighbors.hasNext())//對于 每個頂點都周遊了它的鄰接表,即周遊了所有的邊,複雜度為O(E)
 5             {
 6                 VertexInterface<T> nextNeighbor = neighbors.next();
 7                 if(!nextNeighbor.isVisited()){
 8                     nextNeighbor.visit();//廣度優先周遊未通路的頂點
 9                     traversalOrder.offer(nextNeighbor.getLabel());
10                     vertexQueue.offer(nextNeighbor);//将該頂點的鄰接點入隊列
11                 }
12             }//end inner while
13         }//end outer while

整個深度優先周遊算法代碼如下：

1 public Queue<T> getDepthFirstTraversal(T origin) {
 2         resetVertices();//先将所有的頂點初始化--時間複雜度為O(V)
 3         LinkedList<VertexInterface<T>> vertexStack = new LinkedList<>();//輔助DFS遞歸周遊
 4         Queue<T> traversalOrder = new LinkedList<>();//儲存DFS周遊順序
 5         
 6         VertexInterface<T> originVertex = vertices.get(origin);//根據起始頂點的辨別獲得起始頂點
 7         originVertex.visit();//通路起始頂點,起始頂點的出度不能為0(隻考慮多于一個頂點的連通圖),若為0,它就沒有鄰接點了
 8         vertexStack.push(originVertex);//各個頂點的入棧順序就是DFS的周遊順序
 9         traversalOrder.offer(originVertex.getLabel());//每當一個頂點入棧時,就将它入隊列,進而隊列儲存了整個周遊順序
10         
11         while(!vertexStack.isEmpty()){
12             VertexInterface<T> topVertex = vertexStack.peek();
13             //找到該頂點的一個未被通路的鄰接點,從該鄰接點出發又去周遊鄰接點的鄰接點
14             VertexInterface<T> nextNeighbor = topVertex.getUnvisitedNeighbor();//判斷所有未被通路的鄰接點，也即周遊了所有的邊--複雜度O(E)
15             if(nextNeighbor != null){
16                 nextNeighbor.visit();
17                 //由于用的是if,在這裡push鄰接點後,下一次while循環pop的是該鄰接點,然後又獲得它的鄰接點,---DFS
18                 vertexStack.push(nextNeighbor);
19                 traversalOrder.offer(nextNeighbor.getLabel());
20             }
21             else
22                 vertexStack.pop();//當某頂點的所有鄰接點都被通路了時,直接将該頂點pop,這樣下一次while pop 時就回溯到前一個頂點
23         }//end while
24         return traversalOrder;
25     }

深度優先周遊的算法的時間複雜度：O(V+E)--周遊之前，給每個頂點進行初始化時需要周遊所有頂點V，在周遊過程中需要判斷頂點的鄰接點是否被周遊，也即周遊該頂點的鄰接表，鄰接表代表的實質是邊，邊總數為 E，故總的時間複雜度為O(V+E)；空間複雜度：O(V)--用了兩個輔助棧

④拓撲排序算法

求圖的拓撲序列的思路就是：先找到圖中一個出度為0的頂點，通路該頂點并将之入棧。通路了該頂點之後，相當于指向該頂點的所有的邊都已經被删除了。然後，繼續在圖中尋找下一個出度為0且未被通路的頂點，直至圖中所有的頂點都已被通路。尋找這樣的頂點的方法實作如下：

1 private VertexInterface<T> getNextTopologyOrder(){//最壞情況下複雜度為O(V+E)
 2         VertexInterface<T> nextVertex = null;
 3         Iterator<VertexInterface<T>> iterator = vertices.values().iterator();//獲得圖的頂點的疊代器
 4         boolean found = false;
 5         while(!found && iterator.hasNext()){
 6             nextVertex = iterator.next();
 7             //尋找出度為0且未被通路的頂點
 8             if(nextVertex.isVisited() == false && nextVertex.getUnvisitedNeighbor() == null)
 9                 found = true;
10         }
11         return nextVertex;
12     }

圖的拓撲排序實作代碼如下：

1 public Stack<T> getTopologicalSort() {
 2         /**
 3          *相比于《算法導論》中的拓撲排序借助了DFS複雜度為O(V+E),該算法的時間複雜度較大
 4          *因為算法導論中介紹的圖的資料結構與此處實作的圖的資料結構不同
 5          *此算法的最壞時間複雜度為O(V*(V+E))==V * max{V,E}
 6         */
 7         resetVertices();//先将所有的頂點初始化
 8         
 9         Stack<T> vertexStack = new Stack<>();//存放已通路的頂點的棧,該棧就是一個拓撲序列
10         int numberOfVertices = vertices.size();//獲得圖中頂點的個數
11         
12         for(int counter = 1; counter <= numberOfVertices; counter++){
13             VertexInterface<T> nextVertex = getNextTopologyOrder();//獲得一個未被通路的且出度為0的頂點
14             if(nextVertex != null){
15                 nextVertex.visit();
16                 vertexStack.push(nextVertex.getLabel());//周遊完成後,出棧就可以獲得圖的一個拓撲序列
17             }
18         }
19         return vertexStack;
20     }

此拓撲排序算法實作的最壞情況下時間複雜度為：O(V*max(V,E))；空間複雜度為：O(V)--定義一個輔助棧來儲存周遊順序

4，總結

本文實作了有向無環圖及四個常用的圖的周遊算法，在客戶程式中隻需要 new 一個圖對象，然後就可以調用這些算法了。哈哈，以後可以用這個類來測試一些複雜的算法了。。。

在實作過程中讓我明白了，資料結構與算法是緊密相關的，算法實作的難易程式及好壞依賴于你所設計的資料結構。

整個資料結構的學習至此為止告一段落了。在整個學習過程中，用JAVA語言把常用的資料結構數組、連結清單、棧、隊列、樹、詞典、圖都實作了一遍。感覺學到最多的是加深了對JAVA集合類庫的了解和基本算法的了解(樹的周遊算法和圖的周遊算法)。

整個圖的實作的JAVA完整代碼下載下傳(僅供學習)

資料結構--圖的JAVA實作(下)

繼續閱讀

樹的基本概念(定義、基本術語、性質)

GSL--GNU Scientific Library

D5|哈希表，善用資料結構

如何成為一名.net 工程師?

BMP檔案結構及圖像每行位元組計算方法

D. Ehab the Xorcist(構造+思維)

查找算法之二分查找查找算法之二分查找

JAVA高效程式設計指南

CQ V1.0分詞bates(基于雙數組tire樹)—應該是目前最快的中文分詞算法

【資料結構】醫院選址

[轉]ISUP信令的IAM消息詳細内容

筆試面試題目：滑動視窗(二)

交通/城市相關的公開的資料集上學時整理的Xie et al., 2020收集的

資料結構與算法（27）——排序（二）

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

Linux裝置模型（中）之上層容器

資料結構--圖 的JAVA實作(下)

繼續閱讀

資料結構--圖的JAVA實作(下)