Java數據結構之圖的原理與實現
首先介紹瞭圖的入門概念，然後介紹瞭圖的鄰接矩陣和鄰接表兩種存儲結構、以及深度優先遍歷和廣度優先遍歷的兩種遍歷方式，最後提供瞭Java代碼的實現。
圖，算作一種比較復雜的數據結構，因此建議有一定數據結構基礎的人再來學習！
1 圖的定義和相關概念
定義：圖（Graph）是由頂點的有窮非空集合和頂點之間邊的集合組成，通常表示為：G(V,E)，其中，G表示一個圖，V是圖G中頂點的集合，E是圖G中邊的集合。圖在數據結構中是中多對多的關系，而樹則是1對多的關系，樹就是一種特別的沒有閉環的圖。
頂點：圖中的頂點就是節點的意思，不過圖中任意的節點都算作頂點。將頂點集合為空的圖稱為空圖。圖中任意兩個頂點之間都可能存在關系，頂點之間的邏輯關系用邊來表示，邊集可以是空的。
無向圖：若頂點vi到vj之間的邊沒有方向，則稱這條邊為無向邊（Edge），用無序偶對(vi,vj)來表示。如果圖中任意兩個頂點之間的邊都是無向邊，則稱該圖為無向圖（Undirected graphs）。
有向圖：若從頂點vi到vj的邊有方向，則稱這條邊為有向邊，也稱為弧（Arc）。如果圖中任意兩個頂點之間的邊都是有向邊，則稱該圖為有向圖（Directed graphs）。
完全圖、稠密圖、稀疏圖：具有n個頂點，n(n-1)/2條邊的圖，稱為完全無向圖；具有n個頂點，n(n-1) 條弧的有向圖,稱為完全有向圖。完全無向圖和完全有向圖都稱為完全圖。當一個圖接近完全圖時，則稱它為稠密圖，當一個圖中含有較少的邊或弧時，則稱它為稀疏圖。
權、網：有些圖的邊或弧具有與它相關的數字，這種與圖的邊或弧相關的數叫做權（Weight）。這些權可以表示從一個頂點到另一個頂點的距離或耗費。這種帶權的圖通常稱為網（Network）。
子圖：若有兩個圖G=(V1,E1)， G2=(V2,E2)， 滿足如下條件：V2⊆V1 ，E2⊆ E1，即V2為V1的子集，E2為E1的子集，則 稱圖G2為圖G1的子圖。
下圖中帶底紋的圖均為左側無向圖與有向圖的子圖。
鄰接點、度：相鄰且有邊直接連接的兩個頂點稱為鄰接點。頂點所連邊的數目稱為度，在有向圖中，由於邊有方向，則頂點的度分為入度和出度。
簡單路徑、連通圖：圖中頂點間存在路徑，兩頂點存在路徑則說明是連通的，如果路徑最終回到起始點則稱為環，當中不重復叫簡單路徑。若任意兩頂點都是連通的，則圖就是連通圖，有向則稱強連通圖。圖中有子圖，若子圖極大連通則就是連通分量，有向的則稱強連通分量。
生成樹：無向圖中連通且n個頂點n-1條邊叫生成樹。有向圖中一頂點入度為0其餘頂點入度為1的叫有向樹。一個有向圖由若幹棵有向樹構成生成森林。
2 圖的存儲結構
由於圖的結構比較復雜，任意兩個頂點之間都可能存在聯系，因此無法以單一的結構來表示。圖最常見的表示形式為鄰接鏈表和鄰接矩陣，它們都是采用復合的結構來表示圖。
2.1 鄰接矩陣
鄰接矩陣（Adjacency Matrix）：采用兩個數組來存儲圖，一個一維數組存儲圖頂點信息，一個二維數組存儲圖邊或弧的信息，二維數組可以看作矩陣，這也是“鄰接矩陣”名字的由來。這是最簡單的圖的存儲方式，但是存在空間浪費的情況。
設圖G有n個頂點，則鄰接矩陣是一個n×n的方陣，定義為：
矩陣的對角線始終為0，因為頂點不能和自己連接。無向圖的數據是對稱的，有向圖就不一定瞭。
下圖就是采用鄰接矩陣表示的無向圖。
下圖就是采用鄰接矩陣表示的有向圖。
有向圖講究入度與出度，頂點0的入度為3，正好是第1列各數之和。頂點0的出度為3，即第1行的各數之和。一個點的入度是點所表示的列的各數的和，出度就是個點所表示的行的各數的和。
下圖就是采用鄰接矩陣表示的帶權有向圖。
註意，邊二維數組中的數字表示權，沒有關系的頂點（沒有權)使用”/”表示。
2.2 鄰接表
鄰接表（Adjacency List）：采用數組和鏈表存儲，一個數組存儲頂點，同時頂點想外拉出鏈表表示邊或者弧，鏈表稱為邊表，如度的邊表稱為入邊表，出度的邊表稱為出邊表。鄰接表的實現隻關心存在的邊，不關心不存在的邊，因此沒有空間浪費。
下圖就是采用鄰接表表示的無向圖。
下圖就是采用鄰接表表示的有向圖。
下圖就是采用鄰接矩陣表示的帶權有向圖。
鄰接表在表示稀疏圖時非常緊湊而成為瞭通常的選擇，相比之下，如果在稀疏圖表示時使用鄰接矩陣，會浪費很多內存空間，遍歷的時候也會增加開銷。如果圖是稠密圖，鄰接表的優勢就不明顯瞭，那麼就可以選擇更加方便的鄰接矩陣。
3 圖的遍歷
3.1 深度優先遍歷
深度優先遍歷（Depth First Search），也有稱為深度優先搜索，簡稱為DFS。類似於樹的先序遍歷。基本思想是“一條路走到黑”，然後往回退，回退過程中如果遇到沒探索過的支路，就進入該支路繼續深入，直到所有頂點都被訪問到。
假設初始狀態是圖中所有頂點均未被訪問，則從某個頂點v出發，首先訪問該頂點，然後依次從它的各個未被訪問的鄰接點出發深度優先搜索遍歷圖，直至圖中所有和v有路徑相通的頂點都被訪問到。但此時還有可能有其他分支我們沒有訪問到，若此時尚有其他頂點未被訪問到，需要回溯，另選一個未被訪問的頂點作起始點，重復上述過程，直至圖中所有頂點都被訪問到為止。顯然，深度優先搜索是一個遞歸的過程。
對如下左邊無向圖從0頂點開始進行深度優先遍歷之後一種結果為：0、1、4、5、3、2，如右圖。
從起始點0開始遍歷，在訪問瞭0後，選擇其鄰接點1。因為1未曾訪問過，則從1出發進行深度優先遍歷。依次類推，接著從4、5、3出發進行遍歷。在訪問瞭3後，由於3的鄰接點都已被訪問，則遍歷回退到5。此時5的另一個鄰接點2未被訪問，則遍歷又從5到2,再繼續進行下去，於是得到節點的線性順序為：0、1、4、5、3、2，如右圖中紅色箭頭線為其深度優先遍歷順序。
對如下左邊有向圖從0頂點開始進行深度優先遍歷之後一種結果為：0、1、4、2、5、3，如右圖。
有向圖的深度優先遍歷頂點的領邊需要考慮頂點的出度對應的頂點。該頂點的出度對應的頂點算作鄰接點。
從起始點0開始遍歷，在訪問瞭0後，選擇其出度鄰接點1、2。這裡選擇1進行訪問，從1出發進行有向圖深度優先遍歷。依次類推，在訪問瞭4後，由於4的出度鄰接點0、1都已被訪問，則遍歷回退直到0。此時0的另一個鄰接點2未被訪問，則遍歷又從0到2,再繼續進行下去，於是得到節點的線性順序為：0、1、4、2、5、4，如右圖中紅色箭頭線為有向圖深度優先遍歷順序。
3.2 廣度優先遍歷
廣度優先遍歷(Depth First Search) ，也有稱為廣度優先搜索，簡稱BFS，類似於樹的層序遍歷。基本思想是盡最大程度輻射能夠覆蓋的節點，並對其進行訪問。
從圖中某頂點v出發，在訪問瞭v之後依次訪問v的各個未曾訪問過的鄰接點，然後分別從這些鄰接點出發依次訪問它們的鄰接點，並使得“先被訪問的頂點的鄰接點先於後被訪問的頂點的鄰接點被訪問，直至圖中所有已被訪問的頂點的鄰接點都被訪問到。如果此時圖中尚有頂點未被訪問，則需要另選一個未曾被訪問過的頂點作為新的起始點，重復上述過程，直至圖中所有頂點都被訪問到為止。換句話說，廣度優先搜索遍歷圖的過程是以v為起點，由近至遠。
對如下左邊無向圖從0頂點開始進行深度優先遍歷之後一種結果為：0、1、2、3、4、5，如右圖。
從起始點0開始遍歷，在訪問瞭0後，尋找鄰接點，找到瞭1、2、3，一次遍歷，訪問完1、2、3之後，再依次訪問它們的鄰接點。首先訪問1的鄰接點4，再訪問2的鄰接點5。因此訪問順序是：0、1、2、3、4、5。
對如下左邊有向圖從0頂點開始進行廣度優先遍歷之後一種結果為：0、1、2、4、5、3，如右圖。
有向圖的廣度優先遍歷頂點的領邊同樣需要考慮頂點的出度對應的頂點。該頂點的出度對應的頂點算作鄰接點。
從起始點0開始遍歷，在訪問瞭0後，選擇其出度鄰接點1、2，然後訪問1、2；訪問完1,2之後，再依次訪問它們的鄰接點。首先訪問1的鄰接點4依次類推，再訪問2的鄰接點5。訪問完5之後，再依次訪問它們的鄰接點，最後訪問5的鄰接點3。此時所有頂點訪問完畢。因此訪問順序是：0、1、2、4、5、3。
4 圖的實現
關於圖的實現，Guava中的com.google.common.graph模塊已經提供瞭圖的各種實現，而且都非常完美，這裡隻提供四個簡單實現。帶權重的圖的實現，將在後面的最小生成樹和最短路徑部分提供實現。
4.1 無向圖的鄰接表實現
/**
* 無向圖鄰接鏈表簡單實現
* {@link UndirectedAdjacencyList#UndirectedAdjacencyList(E[], E[][])} 構建無向圖
* {@link UndirectedAdjacencyList#DFS()} 深度優先遍歷無向圖
* {@link UndirectedAdjacencyList#BFS()} 廣度優先遍歷無向圖
* {@link UndirectedAdjacencyList#toString()} ()} 輸出無向圖
*
* @author lx
*/
public class UndirectedAdjacencyList<E> {
/**
* 頂點類
*
* @param <E>
*/
private class Node<E> {
/**
* 頂點信息
*/
E data;
/**
* 指向第一條依附該頂點的邊
*/
LNode firstEdge;
public Node(E data, LNode firstEdge) {
this.data = data;
this.firstEdge = firstEdge;
}
}
/**
* 邊表節點類
*/
private class LNode {
/**
* 該邊所指向的頂點的索引位置
*/
int vertex;
/**
* 指向下一條邊的指針
*/
LNode nextEdge;
}
/**
* 頂點數組
*/
private Node<E>[] vertexs;
/**
* 創建圖
*
* @param vexs 頂點數組
* @param edges 邊二維數組
*/
public UndirectedAdjacencyList(E[] vexs, E[][] edges) {
/*初始化頂點數組,並添加頂點*/
vertexs = new Node[vexs.length];
for (int i = 0; i < vertexs.length; i++) {
vertexs[i] = new Node<>(vexs[i], null);
}
/*初始化邊表,並添加邊節點到邊表尾部,即采用尾插法*/
for (E[] edge : edges) {
// 讀取一條邊的起始頂點和結束頂點索引值
int p1 = getPosition(edge[0]);
int p2 = getPosition(edge[1]);
/*這裡需要相互添加邊節點,無向圖可以看作相互可達的有向圖*/
// 初始化lnode1邊節點
LNode lnode1 = new LNode();
lnode1.vertex = p2;
// 將LNode鏈接到"p1所在鏈表的末尾"
if (vertexs[p1].firstEdge == null) {
vertexs[p1].firstEdge = lnode1;
} else {
linkLast(vertexs[p1].firstEdge, lnode1);
}
// 初始化lnode2邊節點
LNode lnode2 = new LNode();
lnode2.vertex = p1;
// 將lnode2鏈接到"p2所在鏈表的末尾"
if (vertexs[p2].firstEdge == null) {
vertexs[p2].firstEdge = lnode2;
} else {
linkLast(vertexs[p2].firstEdge, lnode2);
}
}
}
/**
* 獲取某條邊的某個頂點所在頂點數組的索引位置
*
* @param e 頂點的值
* @return 所在頂點數組的索引位置, 或者-1 - 表示不存在
*/
private int getPosition(E e) {
for (int i = 0; i < vertexs.length; i++) {
if (vertexs[i].data == e) {
return i;
}
}
return -1;
}
/**
* 將lnode節點鏈接到邊表的最後,采用尾插法
*
* @param first 邊表頭結點
* @param node 將要添加的節點
*/
private void linkLast(LNode first, LNode node) {
while (true) {
if (first.vertex == node.vertex) {
return;
}
if (first.nextEdge == null) {
break;
}
first = first.nextEdge;
}
first.nextEdge = node;
}
/**
* 深度優先搜索遍歷圖的遞歸實現,類似於樹的先序遍歷
* 因此模仿樹的先序遍歷,同樣借用棧結構,這裡使用的是方法的遞歸,隱式的借用棧
*
* @param i 頂點索引
* @param visited 訪問標志數組
*/
private void DFS(int i, boolean[] visited) {
//索引索引標記為true ,表示已經訪問瞭
visited[i] = true;
System.out.print(vertexs[i].data + " ");
//獲取該頂點的邊表頭結點
LNode node = vertexs[i].firstEdge;
//循環遍歷該頂點的鄰接點,采用同樣的方式遞歸搜索
while (node != null) {
if (!visited[node.vertex]) {
DFS(node.vertex, visited);
}
node = node.nextEdge;
}
}
/**
* 深度優先搜索遍歷圖,類似於樹的前序遍歷,
*/
public void DFS() {
//新建頂點訪問標記數組,對應每個索引對應相同索引的頂點數組中的頂點
boolean[] visited = new boolean[vertexs.length];
//初始化所有頂點都沒有被訪問
for (int i = 0; i < vertexs.length; i++) {
visited[i] = false;
}
System.out.println("DFS: ");
/*循環搜索*/
for (int i = 0; i < vertexs.length; i++) {
//如果對應索引的頂點的訪問標記為false,則搜索該頂點
if (!visited[i]) {
DFS(i, visited);
}
}
/*走到這一步,說明頂點訪問標記數組全部為true,說明全部都訪問到瞭,深度搜索結束*/
System.out.println();
}
/**
* 廣度優先搜索圖,類似於樹的層序遍歷
* 因此模仿樹的層序遍歷,同樣借用隊列結構
*/
public void BFS() {
// 輔組隊列
Queue<Integer> indexLinkedList = new LinkedList<>();
//新建頂點訪問標記數組,對應每個索引對應相同索引的頂點數組中的頂點
boolean[] visited = new boolean[vertexs.length];
//初始化所有頂點都沒有被訪問
for (int i = 0; i < vertexs.length; i++) {
visited[i] = false;
}
System.out.println("BFS: ");
for (int i = 0; i < vertexs.length; i++) {
//如果訪問方劑為false,則設置為true,表示已經訪問,然後開始訪問
if (!visited[i]) {
visited[i] = true;
System.out.print(vertexs[i].data + " ");
indexLinkedList.add(i);
}
//判斷隊列是否有值,有就開始遍歷
if (!indexLinkedList.isEmpty()) {
//出隊列
Integer j = indexLinkedList.poll();
LNode node = vertexs[j].firstEdge;
while (node != null) {
int k = node.vertex;
if (!visited[k]) {
visited[k] = true;
System.out.print(vertexs[k].data + " ");
//繼續入隊列
indexLinkedList.add(k);
}
node = node.nextEdge;
}
}
}
System.out.print("\n");
}
@Override
public String toString() {
StringBuilder stringBuilder = new StringBuilder();
for (int i = 0; i < vertexs.length; i++) {
stringBuilder.append(i).append("(").append(vertexs[i].data).append("): ");
LNode node = vertexs[i].firstEdge;
while (node != null) {
stringBuilder.append(node.vertex).append("(").append(vertexs[node.vertex].data).append(")");
node = node.nextEdge;
if (node != null) {
stringBuilder.append("->");
} else {
break;
}
}
stringBuilder.append("\n");
}
return stringBuilder.toString();
}
public static void main(String[] args) {
//頂點數組 添加的先後順序對於遍歷結果有影響
Character[] vexs = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
//邊二維數組 添加的先後順序對於遍歷結果有影響
Character[][] edges = {
{'A', 'C'},
//對於無向圖來說是多餘的邊關系,在linkLast方法中做瞭判斷,並不會重復添加
{'A', 'D'},
{'A', 'D'},
{'D', 'A'},
{'A', 'F'},
{'B', 'C'},
{'C', 'D'},
{'E', 'G'},
{'E', 'B'},
{'D', 'B'},
{'F', 'G'}};
//構建圖
UndirectedAdjacencyList<Character> undirectedAdjacencyList = new UndirectedAdjacencyList<>(vexs, edges);
//輸出圖
System.out.println(undirectedAdjacencyList);
//深度優先遍歷
undirectedAdjacencyList.DFS();
//廣度優先遍歷
undirectedAdjacencyList.BFS();
}
}
測試無向圖對應的邏輯結構如下：
測試圖的遍歷結果如下：
4.2 有向圖的鄰接表實現
/**
* 有向圖鄰接鏈表簡單實現
* {@link AdjacencyList#AdjacencyList(E[], E[][])} 構建有向圖
* {@link AdjacencyList#DFS()} 深度優先遍歷有向圖
* {@link AdjacencyList#BFS()} 廣度優先遍歷有向圖
* {@link AdjacencyList#toString()} ()} 輸出有向圖
*
* @author lx
*/
public class AdjacencyList<E> {
/**
* 頂點類
*
* @param <E>
*/
private class Node<E> {
/**
* 頂點信息
*/
E data;
/**
* 指向第一條依附該頂點的邊
*/
LNode firstEdge;
public Node(E data, LNode firstEdge) {
this.data = data;
this.firstEdge = firstEdge;
}
}
/**
* 邊表節點類
*/
private class LNode {
/**
* 該邊所指向的頂點的索引位置
*/
int vertex;
/**
* 指向下一條弧的指針
*/
LNode nextEdge;
}
/**
* 頂點數組
*/
private Node<E>[] vertexs;
/**
* 創建圖
*
* @param vexs 頂點數組
* @param edges 邊二維數組
*/
public AdjacencyList(E[] vexs, E[][] edges) {
/*初始化頂點數組,並添加頂點*/
vertexs = new Node[vexs.length];
for (int i = 0; i < vertexs.length; i++) {
vertexs[i] = new Node<>(vexs[i], null);
}
/*初始化邊表,並添加邊節點到邊表尾部,即采用尾插法*/
for (E[] edge : edges) {
// 讀取一條邊的起始頂點和結束頂點索引值
int p1 = getPosition(edge[0]);
int p2 = getPosition(edge[1]);
// 初始化lnode1邊節點 即表示p1指向p2的邊
LNode lnode1 = new LNode();
lnode1.vertex = p2;
// 將LNode鏈接到"p1所在鏈表的末尾"
if (vertexs[p1].firstEdge == null) {
vertexs[p1].firstEdge = lnode1;
} else {
linkLast(vertexs[p1].firstEdge, lnode1);
}
}
}
/**
* 獲取某條邊的某個頂點所在頂點數組的索引位置
*
* @param e 頂點的值
* @return 所在頂點數組的索引位置, 或者-1 - 表示不存在
*/
private int getPosition(E e) {
for (int i = 0; i < vertexs.length; i++) {
if (vertexs[i].data == e) {
return i;
}
}
return -1;
}
/**
* 將lnode節點鏈接到邊表的最後,采用尾插法
*
* @param first 邊表頭結點
* @param node 將要添加的節點
*/
private void linkLast(LNode first, LNode node) {
while (true) {
if (first.vertex == node.vertex) {
return;
}
if (first.nextEdge == null) {
break;
}
first = first.nextEdge;
}
first.nextEdge = node;
}
/**
* 深度優先搜索遍歷圖的遞歸實現,類似於樹的先序遍歷
* 因此模仿樹的先序遍歷,同樣借用棧結構,這裡使用的是方法的遞歸,隱式的借用棧
*
* @param i 頂點索引
* @param visited 訪問標志數組
*/
private void DFS(int i, boolean[] visited) {
//索引索引標記為true ,表示已經訪問瞭
visited[i] = true;
System.out.print(vertexs[i].data + " ");
//獲取該頂點的邊表頭結點
LNode node = vertexs[i].firstEdge;
//循環遍歷該頂點的鄰接點,采用同樣的方式遞歸搜索
while (node != null) {
if (!visited[node.vertex]) {
DFS(node.vertex, visited);
}
node = node.nextEdge;
}
}
/**
* 深度優先搜索遍歷圖,類似於樹的前序遍歷,
*/
public void DFS() {
//新建頂點訪問標記數組,對應每個索引對應相同索引的頂點數組中的頂點
boolean[] visited = new boolean[vertexs.length];
//初始化所有頂點都沒有被訪問
for (int i = 0; i < vertexs.length; i++) {
visited[i] = false;
}
System.out.println("DFS: ");
/*循環搜索*/
for (int i = 0; i < vertexs.length; i++) {
//如果對應索引的頂點的訪問標記為false,則搜索該頂點
if (!visited[i]) {
DFS(i, visited);
}
}
/*走到這一步,說明頂點訪問標記數組全部為true,說明全部都訪問到瞭,深度搜索結束*/
System.out.println();
}
/**
* 廣度優先搜索圖,類似於樹的層序遍歷
* 因此模仿樹的層序遍歷,同樣借用隊列結構
*/
public void BFS() {
// 輔組隊列
Queue<Integer> indexLinkedList = new LinkedList<>();
//新建頂點訪問標記數組,對應每個索引對應相同索引的頂點數組中的頂點
boolean[] visited = new boolean[vertexs.length];
//初始化所有頂點都沒有被訪問
for (int i = 0; i < vertexs.length; i++) {
visited[i] = false;
}
System.out.println("BFS: ");
for (int i = 0; i < vertexs.length; i++) {
//如果訪問方劑為false,則設置為true,表示已經訪問,然後開始訪問
if (!visited[i]) {
visited[i] = true;
System.out.print(vertexs[i].data + " ");
indexLinkedList.add(i);
}
//判斷隊列是否有值,有就開始遍歷
if (!indexLinkedList.isEmpty()) {
//出隊列
Integer j = indexLinkedList.poll();
LNode node = vertexs[j].firstEdge;
while (node != null) {
int k = node.vertex;
if (!visited[k]) {
visited[k] = true;
System.out.print(vertexs[k].data + " ");
//繼續入隊列
indexLinkedList.add(k);
}
node = node.nextEdge;
}
}
}
System.out.println("\n");
}
@Override
public String toString() {
StringBuilder stringBuilder = new StringBuilder();
for (int i = 0; i < vertexs.length; i++) {
stringBuilder.append(i).append("(").append(vertexs[i].data).append("): ");
LNode node = vertexs[i].firstEdge;
while (node != null) {
stringBuilder.append(node.vertex).append("(").append(vertexs[node.vertex].data).append(")");
node = node.nextEdge;
if (node != null) {
stringBuilder.append("->");
} else {
break;
}
}
stringBuilder.append("\n");
}
return stringBuilder.toString();
}
public static void main(String[] args) {
//頂點數組 添加的先後順序對於遍歷結果有影響
Character[] vexs = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
//邊二維數組 {'a', 'b'}表示頂點a->b的邊 添加的先後順序對於遍歷結果有影響
Character[][] edges = {
{'A', 'C'},
{'A', 'D'},
//對於有向圖來說是多餘的邊關系,在linkLast方法中做瞭判斷,並不會重復添加
{'A', 'D'},
//對於有向圖來說不是多餘的邊關系
{'D', 'A'},
{'A', 'F'},
{'B', 'C'},
{'C', 'D'},
{'E', 'G'},
{'E', 'B'},
{'D', 'B'},
{'F', 'G'}};
// 構建圖有向圖
AdjacencyList<Character> adjacencyList = new AdjacencyList<>(vexs, edges);
//輸出圖
System.out.println(adjacencyList);
//深度優先遍歷
adjacencyList.DFS();
//廣度優先遍歷
adjacencyList.BFS();
}
}
測試有向圖對應的邏輯結構如下：
測試圖的遍歷結果如下：
4.3 無向圖的鄰接矩陣實現
/**
* 無向圖鄰接矩陣簡單實現
* {@link UndirectedAdjacencyMatrix#UndirectedAdjacencyMatrix(E[], E[][])} 構建無向圖
* {@link UndirectedAdjacencyMatrix#DFS()} 深度優先遍歷無向圖
* {@link UndirectedAdjacencyMatrix#BFS()} 廣度優先遍歷無向圖
* {@link UndirectedAdjacencyMatrix#toString()} ()} 輸出無向圖
*
* @author lx
*/
public class UndirectedAdjacencyMatrix<E> {
/**
* 頂點數組
*/
private Object[] vertexs;
/**
* 鄰接矩陣
*/
private int[][] matrix;
/*
* 創建圖
*
* 參數說明：
* vexs -- 頂點數組
* edges -- 邊數組
*/
/**
* 創建無向圖
*
* @param vexs 頂點數組
* @param edges 邊二維數組
*/
public UndirectedAdjacencyMatrix(E[] vexs, E[][] edges) {
// 初始化頂點數組,並添加頂點
vertexs = Arrays.copyOf(vexs, vexs.length);
// 初始化邊矩陣,並填充邊信息
matrix = new int[vexs.length][vexs.length];
for (E[] edge : edges) {
// 讀取一條邊的起始頂點和結束頂點索引值
int p1 = getPosition(edge[0]);
int p2 = getPosition(edge[1]);
//對稱的兩個點位都置為1,無向圖可以看作相互可達的有向圖
matrix[p1][p2] = 1;
matrix[p2][p1] = 1;
}
}
/**
* 獲取某條邊的某個頂點所在頂點數組的索引位置
*
* @param e 頂點的值
* @return 所在頂點數組的索引位置, 或者-1 - 表示不存在
*/
private int getPosition(E e) {
for (int i = 0; i < vertexs.length; i++) {
if (vertexs[i] == e) {
return i;
}
}
return -1;
}
/**
* 深度優先搜索遍歷圖,類似於樹的前序遍歷,
*/
public void DFS() {
//新建頂點訪問標記數組,對應每個索引對應相同索引的頂點數組中的頂點
boolean[] visited = new boolean[vertexs.length];
//初始化所有頂點都沒有被訪問
for (int i = 0; i < vertexs.length; i++) {
visited[i] = false;
}
System.out.println("DFS: ");
for (int i = 0; i < vertexs.length; i++) {
if (!visited[i]) {
DFS(i, visited);
}
}
System.out.println();
}
/**
* 深度優先搜索遍歷圖的遞歸實現,類似於樹的先序遍歷
* 因此模仿樹的先序遍歷,同樣借用棧結構,這裡使用的是方法的遞歸,隱式的借用棧
*
* @param i 頂點索引
* @param visited 訪問標志數組
*/
private void DFS(int i, boolean[] visited) {
visited[i] = true;
System.out.print(vertexs[i] + " ");
// 遍歷該頂點的所有鄰接點。若該鄰接點是沒有訪問過，那麼繼續遞歸遍歷領接點
for (int w = firstVertex(i); w >= 0; w = nextVertex(i, w)) {
if (!visited[w]) {
DFS(w, visited);
}
}
}
/**
* 返回頂點v的第一個鄰接頂點的索引，失敗則返回-1
*
* @param v 頂點v在數組中的索引
* @return 返回頂點v的第一個鄰接頂點的索引，失敗則返回-1
*/
private int firstVertex(int v) {
//如果索引超出范圍,則返回-1
if (v < 0 || v > (vertexs.length - 1)) {
return -1;
}
/*根據鄰接矩陣的規律:頂點索引v對應著邊二維矩陣的matrix[v][i]一行記錄
* 從i=0開始*/
for (int i = 0; i < vertexs.length; i++) {
if (matrix[v][i] == 1) {
return i;
}
}
return -1;
}
/**
* 返回頂點v相對於w的下一個鄰接頂點的索引，失敗則返回-1
*
* @param v 頂點索引
* @param w 第一個鄰接點索引
* @return 返回頂點v相對於w的下一個鄰接頂點的索引，失敗則返回-1
*/
private int nextVertex(int v, int w) {
//如果索引超出范圍,則返回-1
if (v < 0 || v > (vertexs.length - 1) || w < 0 || w > (vertexs.length - 1)) {
return -1;
}
/*根據鄰接矩陣的規律:頂點索引v對應著邊二維矩陣的matrix[v][i]一行記錄
* 由於鄰接點w的索引已經獲取瞭,所以從i=w+1開始尋找*/
for (int i = w + 1; i < vertexs.length; i++) {
if (matrix[v][i] == 1) {
return i;
}
}
return -1;
}
/*
* 廣度優先搜索（類似於樹的層次遍歷）
*/
public void BFS() {
// 輔組隊列
Queue<Integer> indexLinkedList = new LinkedList<>();
//新建頂點訪問標記數組,對應每個索引對應相同索引的頂點數組中的頂點
boolean[] visited = new boolean[vertexs.length];
for (int i = 0; i < vertexs.length; i++) {
visited[i] = false;
}
System.out.println("BFS: ");
for (int i = 0; i < vertexs.length; i++) {
if (!visited[i]) {
visited[i] = true;
System.out.print(vertexs[i] + " ");
indexLinkedList.add(i);
}
if (!indexLinkedList.isEmpty()) {
//j索引出隊列
Integer j = indexLinkedList.poll();
//繼續訪問j的鄰接點
for (int k = firstVertex(j); k >= 0; k = nextVertex(j, k)) {
if (!visited[k]) {
visited[k] = true;
System.out.print(vertexs[k] + " ");
//繼續入隊列
indexLinkedList.add(k);
}
}
}
}
System.out.println();
}
@Override
public String toString() {
StringBuilder stringBuilder = new StringBuilder();
for (int i = 0; i < vertexs.length; i++) {
for (int j = 0; j < vertexs.length; j++) {
stringBuilder.append(matrix[i][j]).append(" ");
}
stringBuilder.append("\n");
}
return stringBuilder.toString();
}
public static void main(String[] args) {
Character[] vexs = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
Character[][] edges = {
{'A', 'C'},
//對於無向圖來說是多餘的邊關系,在linkLast方法中做瞭判斷,並不會重復添加
{'A', 'D'},
{'A', 'D'},
{'D', 'A'},
{'A', 'F'},
{'B', 'C'},
{'C', 'D'},
{'E', 'G'},
{'E', 'B'},
{'D', 'B'},
{'F', 'G'}};
//構建圖
UndirectedAdjacencyMatrix<Character> undirectedAdjacencyMatrix = new UndirectedAdjacencyMatrix<>(vexs, edges);
//輸出圖
System.out.println(undirectedAdjacencyMatrix);
//深度優先遍歷
undirectedAdjacencyMatrix.DFS();
//廣度優先遍歷
undirectedAdjacencyMatrix.BFS();
}
}
測試無向圖對應的邏輯結構如下：
測試圖的遍歷結果如下：
可以看到，深度優先遍歷出來的順序不一致，實際上這是內部節點的實際存儲順序和結構的問題導致的，但是我們的思想並沒有變，因此該遍歷也是正確的，實際上如果圖的實現不唯一，那麼遍歷順序也不一定是唯一的。
4.4 有向圖的鄰接矩陣實現
/**
* 有向圖鄰接矩陣簡單實現
* {@link AdjacencyMatrix#AdjacencyMatrix(E[], E[][])} 構建有向圖
* {@link AdjacencyMatrix#DFS()} 深度優先遍歷無向圖
* {@link AdjacencyMatrix#BFS()} 廣度優先遍歷無向圖
* {@link AdjacencyMatrix#toString()} ()} 輸出無向圖
*
* @author lx
*/
public class AdjacencyMatrix<E> {
/**
* 頂點數組
*/
private Object[] vertexs;
/**
* 鄰接矩陣
*/
private int[][] matrix;
/**
* 創建有向圖
*
* @param vexs 頂點數組
* @param edges 邊二維數組
*/
public AdjacencyMatrix(E[] vexs, E[][] edges) {
// 初始化頂點數組,並添加頂點
vertexs = Arrays.copyOf(vexs, vexs.length);
// 初始化邊矩陣,並填充邊信息
matrix = new int[vexs.length][vexs.length];
for (E[] edge : edges) {
// 讀取一條邊的起始頂點和結束頂點索引值 p1,p2表示邊方向p1->p2
int p1 = getPosition(edge[0]);
int p2 = getPosition(edge[1]);
//p1 出度的位置 置為1
matrix[p1][p2] = 1;
//無向圖和有向圖的鄰接矩陣實現的區別就在於下面這一行代碼
//matrix[p2][p1] = 1;
}
}
/**
* 獲取某條邊的某個頂點所在頂點數組的索引位置
*
* @param e 頂點的值
* @return 所在頂點數組的索引位置, 或者-1 - 表示不存在
*/
private int getPosition(E e) {
for (int i = 0; i < vertexs.length; i++) {
if (vertexs[i] == e) {
return i;
}
}
return -1;
}
/**
* 深度優先搜索遍歷圖,類似於樹的前序遍歷,
*/
public void DFS() {
//新建頂點訪問標記數組,對應每個索引對應相同索引的頂點數組中的頂點
boolean[] visited = new boolean[vertexs.length];
//初始化所有頂點都沒有被訪問
for (int i = 0; i < vertexs.length; i++) {
visited[i] = false;
}
System.out.println("DFS: ");
for (int i = 0; i < vertexs.length; i++) {
if (!visited[i]) {
DFS(i, visited);
}
}
System.out.println();
}
/**
* 深度優先搜索遍歷圖的遞歸實現,類似於樹的先序遍歷
* 因此模仿樹的先序遍歷,同樣借用棧結構,這裡使用的是方法的遞歸,隱式的借用棧
*
* @param i 頂點索引
* @param visited 訪問標志數組
*/
private void DFS(int i, boolean[] visited) {
visited[i] = true;
System.out.print(vertexs[i] + " ");
// 遍歷該頂點的所有鄰接點。若該鄰接點是沒有訪問過，那麼繼續遞歸遍歷領接點
for (int w = firstVertex(i); w >= 0; w = nextVertex(i, w)) {
if (!visited[w]) {
DFS(w, visited);
}
}
}
/**
* 返回頂點v的第一個鄰接頂點的索引，失敗則返回-1
*
* @param v 頂點v在數組中的索引
* @return 返回頂點v的第一個鄰接頂點的索引，失敗則返回-1
*/
private int firstVertex(int v) {
//如果索引超出范圍,則返回-1
if (v < 0 || v > (vertexs.length - 1)) {
return -1;
}
/*根據鄰接矩陣的規律:頂點索引v對應著邊二維矩陣的matrix[v][i]一行記錄
* 從i=0開始*/
for (int i = 0; i < vertexs.length; i++) {
if (matrix[v][i] == 1) {
return i;
}
}
return -1;
}
/**
* 返回頂點v相對於w的下一個鄰接頂點的索引，失敗則返回-1
*
* @param v 頂點索引
* @param w 第一個鄰接點索引
* @return 返回頂點v相對於w的下一個鄰接頂點的索引，失敗則返回-1
*/
private int nextVertex(int v, int w) {
//如果索引超出范圍,則返回-1
if (v < 0 || v > (vertexs.length - 1) || w < 0 || w > (vertexs.length - 1)) {
return -1;
}
/*根據鄰接矩陣的規律:頂點索引v對應著邊二維矩陣的matrix[v][i]一行記錄
* 由於鄰接點w的索引已經獲取瞭,所以從i=w+1開始尋找*/
for (int i = w + 1; i < vertexs.length; i++) {
if (matrix[v][i] == 1) {
return i;
}
}
return -1;
}
/*
* 廣度優先搜索（類似於樹的層次遍歷）
*/
public void BFS() {
// 輔組隊列
Queue<Integer> indexLinkedList = new LinkedList<>();
//新建頂點訪問標記數組,對應每個索引對應相同索引的頂點數組中的頂點
boolean[] visited = new boolean[vertexs.length];
for (int i = 0; i < vertexs.length; i++) {
visited[i] = false;
}
System.out.println("BFS: ");
for (int i = 0; i < vertexs.length; i++) {
if (!visited[i]) {
visited[i] = true;
System.out.print(vertexs[i] + " ");
indexLinkedList.add(i);
}
if (!indexLinkedList.isEmpty()) {
//j索引出隊列
Integer j = indexLinkedList.poll();
//繼續訪問j的鄰接點
for (int k = firstVertex(j); k >= 0; k = nextVertex(j, k)) {
if (!visited[k]) {
visited[k] = true;
System.out.print(vertexs[k] + " ");
//繼續入隊列
indexLinkedList.add(k);
}
}
}
}
System.out.println();
}
@Override
public String toString() {
StringBuilder stringBuilder = new StringBuilder();
for (int i = 0; i < vertexs.length; i++) {
for (int j = 0; j < vertexs.length; j++) {
stringBuilder.append(matrix[i][j]).append(" ");
}
stringBuilder.append("\n");
}
return stringBuilder.toString();
}
public static void main(String[] args) {
Character[] vexs = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
Character[][] edges = {
{'A', 'C'},
//對於無向圖來說是多餘的邊關系,在linkLast方法中做瞭判斷,並不會重復添加
{'A', 'D'},
{'A', 'D'},
{'D', 'A'},
{'A', 'F'},
{'B', 'C'},
{'C', 'D'},
{'E', 'G'},
{'E', 'B'},
{'D', 'B'},
{'F', 'G'}};
//構建圖
AdjacencyMatrix<Character> undirectedAdjacencyMatrix = new AdjacencyMatrix<>(vexs, edges);
//輸出圖
System.out.println(undirectedAdjacencyMatrix);
//深度優先遍歷
undirectedAdjacencyMatrix.DFS();
//廣度優先遍歷
undirectedAdjacencyMatrix.BFS();
}
}
測試有向圖對應的邏輯結構以及遍歷結果和有向圖的鄰接表實現的結果是一致的。
5 總結
首先介紹瞭圖的入門概念，然後介紹瞭圖的鄰接矩陣和鄰接表兩種存儲結構、以及深度優先遍歷和廣度優先遍歷的兩種遍歷方式，最後提供瞭Java代碼的實現。
關於圖的實現，Guava中的com.google.common.graph模塊已經提供瞭圖的各種實現，而且都非常完美，這裡隻提供四個簡單實現。帶權重的圖的實現，將在後面的最小生成樹和最短路徑的博客中提供實現，大傢可以關註一下。
以上就是Java數據結構之圖的原理與實現的詳細內容，更多關於Java 圖的資料請關註WalkonNet其它相關文章！
推薦閱讀：
- Java求最小生成樹的兩種算法詳解
- Java利用Dijkstra和Floyd分別求取圖的最短路徑
- java圖論普利姆及克魯斯卡算法解決最小生成樹問題詳解
- Java線性表的順序表示及實現
- Java實用工具之StringJoiner詳解