吐血整理程序員必讀書單：https://github.com/silently9527/ProgrammerBooks

微信公眾號(hào)：貝塔學(xué)Java

前言

從本篇開(kāi)始我們將會(huì)一起來(lái)學(xué)習(xí)圖相關(guān)的算法，圖算有很多相當(dāng)實(shí)用算法，比如：垃圾回收器的標(biāo)記清除算法、地圖上求路徑的最短距離、拓?fù)渑判虻取Ｔ陂_(kāi)始學(xué)習(xí)這些算法之前我們需要先來(lái)了解下圖的基本定義，以及使用哪種數(shù)據(jù)結(jié)構(gòu)來(lái)表示一張圖，本篇我們先從無(wú)向圖開(kāi)始學(xué)習(xí)。

圖的定義

圖：是有一組頂點(diǎn)和一組能夠?qū)蓚€(gè)訂單相連組成的。連接兩個(gè)頂點(diǎn)的邊沒(méi)有方向，這種圖稱之為無(wú)向圖。

image

圖的術(shù)語(yǔ)

通過(guò)同一條邊相連的兩個(gè)頂點(diǎn)我們稱這兩個(gè)頂點(diǎn)相鄰；

某個(gè)頂點(diǎn)的度數(shù)即表示連接這個(gè)頂點(diǎn)的邊的總數(shù)；如上圖：頂點(diǎn)1的度數(shù)是3

一條邊連接了一個(gè)頂點(diǎn)與其自身，我們稱為自環(huán)

連接同一對(duì)頂點(diǎn)的邊稱為平行邊

image

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

如何表示出圖

圖用什么數(shù)據(jù)結(jié)構(gòu)來(lái)表示主要參考兩個(gè)要求：

1. 在開(kāi)發(fā)圖的相關(guān)算法時(shí)，圖的表示的數(shù)據(jù)結(jié)構(gòu)是基礎(chǔ)，所以這種數(shù)據(jù)結(jié)構(gòu)效率的高
2. 在實(shí)際的過(guò)程中圖的大小不確定，可能會(huì)很大，所以需要預(yù)留出足夠的空間

考慮了這兩個(gè)要求之后大佬們提出以下三個(gè)方法來(lái)供選擇：

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

image

無(wú)向圖的API定義

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

無(wú)向圖API的實(shí)現(xiàn)

要實(shí)現(xiàn)上面定義的API，我們需要三個(gè)成員變量，v表示圖中頂點(diǎn)的個(gè)數(shù)，e表示圖總共邊的數(shù)據(jù)，LinkedListQueue的數(shù)組用來(lái)存儲(chǔ)頂點(diǎn)v的相鄰節(jié)點(diǎn)；

構(gòu)造函數(shù)會(huì)初始化空的鄰接表數(shù)組

因?yàn)槭菬o(wú)向圖，所以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(" 個(gè)頂點(diǎn)，").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();
    }
}

圖的常用工具方法

基于圖數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)，我們可以提供一些工具方法

1. 計(jì)算頂點(diǎn)v的度數(shù)
   頂點(diǎn)的度數(shù)就等于與之相連接頂點(diǎn)的個(gè)數(shù)

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

2. 計(jì)算所有頂點(diǎn)的最大度數(shù)

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;
}

3. 計(jì)算所有頂點(diǎn)的平均度數(shù)
   每條邊都有兩個(gè)頂點(diǎn)，所以圖所有頂點(diǎn)的總度數(shù)是邊的2倍

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

4. 計(jì)算圖中的自環(huán)個(gè)數(shù)
   對(duì)于頂點(diǎn)v，如果v同時(shí)也出現(xiàn)了在v的鄰接表中，那么表示v存在一個(gè)自環(huán)；由于是無(wú)向圖，每條邊都被記錄了兩次（如果不好理解可以把圖的toString打印出來(lái)就可以理解了）

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;
}

總結(jié)

本篇我們主要學(xué)習(xí)使用何種數(shù)據(jù)結(jié)構(gòu)來(lái)表示一張圖，以及基于這種數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)了幾個(gè)簡(jiǎn)單的工具方法，在下一篇我們將來(lái)學(xué)習(xí)圖的第一個(gè)搜索算法 - 深度優(yōu)先搜索

文中所有源碼已放入到了github倉(cāng)庫(kù):
https://github.com/silently9527/JavaCore

最后（點(diǎn)關(guān)注，不迷路）

文中或許會(huì)存在或多或少的不足、錯(cuò)誤之處，有建議或者意見(jiàn)也非常歡迎大家在評(píng)論交流。

最后，寫作不易，請(qǐng)不要白嫖我喲，希望朋友們可以點(diǎn)贊評(píng)論關(guān)注三連，因?yàn)檫@些就是我分享的全部動(dòng)力來(lái)源??