[[393944]]

 本文轉載自微信公眾號「貝塔學JAVA」，作者Silently9527。轉載本文請聯系貝塔學JAVA公眾號。

前言

從本篇開始我們將會一起來學習圖相關的算法，圖算有很多相當實用算法，比如：垃圾回收器的標記清除算法、地圖上求路徑的最短距離、拓撲排序等。在開始學習這些算法之前我們需要先來了解下圖的基本定義，以及使用哪種數據結構來表示一張圖，本篇我們先從無向圖開始學習。

圖的定義

圖：是有一組頂點和一組能夠將兩個訂單相連組成的。連接兩個頂點的邊沒有方向，這種圖稱之為無向圖。

圖的術語

通過同一條邊相連的兩個頂點我們稱這兩個頂點相鄰;

某個頂點的度數即表示連接這個頂點的邊的總數;如上圖：頂點1的度數是3

一條邊連接了一個頂點與其自身，我們稱為自環

連接同一對頂點的邊稱為平行邊

術語還有很多，暫時這里只列出本篇我們需要使用到的術語，后面有在使用到其他的術語再做解釋，太多也不太容易記得住

如何表示出圖

圖用什么數據結構來表示主要參考兩個要求：

1. 在開發圖的相關算法時，圖的表示的數據結構是基礎，所以這種數據結構效率的高
2. 在實際的過程中圖的大小不確定，可能會很大，所以需要預留出足夠的空間

考慮了這兩個要求之后大佬們提出以下三個方法來供選擇：

• 鄰接矩陣 鍵入有v個頂點的圖，我們可以使用v乘以v的矩陣來表示，如果頂點v與w相連，那么把v行w列設置為true，這樣就可以表示兩個頂點相連，但是這個方式有個問題，如果遇到圖很大，會造成空間的浪費。不滿足第二點。其次這種方式沒辦法表示平行邊
• 邊的數組 可以定義一個表示的邊對象，包含兩個int屬性表示頂點，但是如果需要找到某個頂點的相連頂點有哪些，我們就需要遍歷一遍全部的邊。這種數據結構的效率較差
• 鄰接表數組 定義一個數組，數組的大小為頂點的個數，數據下標表示頂點，數組中每個元素都是一個鏈表對象(LinkedListQueue),鏈表中存放的值就是與該頂點相連的頂點。(LinkedListQueue我們已經在之前的文章中實現，可以參考文章《https://juejin.cn/post/6926685994347397127》)

無向圖的API定義

public class Graph { 
    public Graph(int V); //創建含有v個頂點不含邊的圖 
     
    public int V(); //返回頂點的個數 
     
    public int E(); //返回圖中邊的總數 
     
    public void addEdge(int v, int w); //向圖中添加一條邊 v-W  
         
    public Iterable<Integer> adj(int v); //返回與v相鄰的所有頂點 
     
    public String toString(); //使用字符串打印出圖的關系 
} 

無向圖API的實現

要實現上面定義的API，我們需要三個成員變量，v表示圖中頂點的個數，e表示圖總共邊的數據，LinkedListQueue的數組用來存儲頂點v的相鄰節點;

構造函數會初始化空的鄰接表數組

因為是無向圖，所以addEdge方法在向圖中添加邊既要添加一條v->w的邊，有需要添加一條w->v的邊

public class Graph { 
    private final int v; 
    private int e; 
    private LinkedListQueue<Integer>[] adj; 
 
    public Graph(int v) { 
        this.v = v; 
        this.adj = (LinkedListQueue<Integer>[]) new LinkedListQueue[v]; 
        for (int i = 0; i < v; i++) { 
            this.adj[i] = new LinkedListQueue<>(); 
        } 
    } 
 
    public int V() { 
        return v; 
    } 
 
    public int E() { 
        return e; 
    } 
 
    public void addEdge(int v, int w) { 
        this.adj[v].enqueue(w); 
        this.adj[w].enqueue(v); 
        this.e++; 
    } 
 
    public Iterable<Integer> adj(int v) { 
        return this.adj[v]; 
    } 
 
    @Override 
    public String toString() { 
        StringBuilder sb = new StringBuilder(); 
        sb.append(v).append(" 個頂點，").append(e).append(" 條邊\n"); 
        for (int i = 0; i < v; i++) { 
            sb.append(i).append(": "); 
            for (int j : this.adj[i]) { 
                sb.append(j).append(" "); 
            } 
            sb.append("\n"); 
        } 
        return sb.toString(); 
    } 
} 

圖的常用工具方法

基于圖數據結構的實現，我們可以提供一些工具方法

計算頂點v的度數 頂點的度數就等于與之相連接頂點的個數

public static int degree(Graph graph, int v) { 
    int degree = 0; 
    for (int w : graph.adj(v)) { 
        degree++; 
    } 
    return degree; 
} 

計算所有頂點的最大度數

public static int maxDegree(Graph graph) { 
    int maxDegree = 0; 
    for (int v = 0; v < graph.V(); v++) { 
        int degree = degree(graph, v); 
        if (maxDegree < degree) { 
            maxDegree = degree; 
        } 
    } 
    return maxDegree; 
} 

計算所有頂點的平均度數 每條邊都有兩個頂點，所以圖所有頂點的總度數是邊的2倍

public static double avgDegree(Graph graph) { 
    return 2.0 * graph.E() / graph.V(); 
} 

計算圖中的自環個數 對于頂點v，如果v同時也出現了在v的鄰接表中，那么表示v存在一個自環;由于是無向圖，每條邊都被記錄了兩次(如果不好理解可以把圖的toString打印出來就可以理解了)

public static int numberOfSelfLoops(Graph graph) { 
    int count = 0; 
    for (int v = 0; v < graph.V(); v++) { 
        for (int w : graph.adj(v)) { 
            if (v == w) { 
                count++; 
            } 
        } 
    } 
    return count / 2; 
} 

總結

本篇我們主要學習使用何種數據結構來表示一張圖，以及基于這種數據結構實現了幾個簡單的工具方法，在下一篇我們將來學習圖的第一個搜索算法 - 深度優先搜索

文中所有源碼已放入到了github倉庫:https://github.com/silently9527/JavaCore