圖（Graph）

在討論圖這種數(shù)據(jù)結(jié)構(gòu)之前，先來(lái)回顧一下前面介紹的幾種數(shù)據(jù)結(jié)構(gòu)

線性結(jié)構(gòu)

• 數(shù)組
• 鏈表
• 棧
• 隊(duì)列
• 哈希表

樹(shù)形結(jié)構(gòu)

• 二叉樹(shù)
• B樹(shù)
• 堆
• Trie
• 哈夫曼樹(shù)
• 并查集

接下來(lái)就是將要討論到的圖這種樹(shù)形結(jié)構(gòu)

通過(guò)觀察，可以發(fā)現(xiàn)，圖這種數(shù)據(jù)結(jié)構(gòu)確實(shí)和前面的線性結(jié)構(gòu)，樹(shù)形結(jié)構(gòu)很不一樣，看起來(lái)更加復(fù)雜。不用擔(dān)心，這里將一步一步的對(duì)圖進(jìn)行研究。首先，先來(lái)了解圖的一些基本概念。

圖的基本概念

1. 圖[下圖]由頂點(diǎn)（vertex）和邊（edge）組成，通常表示為G= （V，E）
   • G表示一個(gè)圖，V的頂點(diǎn)集，E是邊集
   • 頂點(diǎn)集V有窮且非空（下圖1有6個(gè)頂點(diǎn)，下圖2有6個(gè)頂點(diǎn)，下圖3有6個(gè)頂點(diǎn)）
   • 任意兩個(gè)頂點(diǎn)之間都可以用邊來(lái)表示它們之間的關(guān)系，邊集E可以是空的（下圖1有6條邊，下圖2有2條邊，下圖3有0條邊）

圖的應(yīng)用

圖結(jié)構(gòu)的應(yīng)用極其廣泛

1. 社交網(wǎng)絡(luò)

   
   

2. 地圖導(dǎo)航

   
   
   
   

3. 游戲開(kāi)發(fā)

   
   

其他應(yīng)用場(chǎng)景不一一舉例

有向圖（Directed Graph）

有向圖的邊是右明確方向的，例如下圖的就表示一個(gè)有向圖，每一條邊都是有明確方向的

有向無(wú)環(huán)圖（Directed Acyclic Graph，簡(jiǎn)稱(chēng)DAG）

• 如果有一個(gè)有向圖，從任一頂點(diǎn)出發(fā)無(wú)法經(jīng)過(guò)若干條邊回到該頂點(diǎn)，那么它就是一個(gè)有向無(wú)環(huán)圖

所以上圖為一個(gè)有向無(wú)環(huán)圖，下圖則不是一個(gè)有向無(wú)環(huán)圖

出度、入度

出度、入度使用于有向圖

出度（Out-degree）

• 一個(gè)頂點(diǎn)的出度為x，是指有x條邊以該頂點(diǎn)為起點(diǎn)（以當(dāng)前節(jié)點(diǎn)，出發(fā)的邊的數(shù)量，就表示出度值）

  根據(jù)這條結(jié)論，可以知道，頂點(diǎn)11的出度為3

入度（In-degree）

• 一個(gè)頂點(diǎn)的入度為x，是指有x條邊以該頂點(diǎn)為終點(diǎn)（以當(dāng)前節(jié)點(diǎn)為重點(diǎn)的邊，就表示入度）

  根據(jù)這條結(jié)論，可以知道，頂點(diǎn)11的入度為2

無(wú)向圖（Undirected Graph）

無(wú)向圖的邊，是沒(méi)有方向的，如下圖所示

這種有向圖，類(lèi)似于下面這種有向圖

混合圖（Mixed Graph）

緩和圖的邊可能是無(wú)向的，也有可能是有向的，如下圖所示

平行邊

• 在無(wú)向圖中，關(guān)聯(lián)一對(duì)頂點(diǎn)的無(wú)向邊如果多于一條，則稱(chēng)這些邊為平行邊
• 在有向圖中，關(guān)聯(lián)一對(duì)頂點(diǎn)的有向邊如果多于一條，并且它們的方向相同，則稱(chēng)這些邊為平行邊

多重圖（Multigraph）

有平行邊或者有自環(huán)的圖（可以理解為比較復(fù)雜的圖）

為什么上圖是多重圖呢？因?yàn)樵搱D有平行邊（紅色線條），有自環(huán)邊（藍(lán)色線條）

簡(jiǎn)單圖（Simple Graph）

既沒(méi)有平行邊，也沒(méi)有自環(huán)的圖，成為簡(jiǎn)單圖。從定義可以知道，簡(jiǎn)單圖與多重圖是相對(duì)的，所以在多重圖之前，介紹的所有圖，其實(shí)都是簡(jiǎn)單圖

本節(jié)內(nèi)容，也將主要對(duì)簡(jiǎn)單圖進(jìn)行討論

無(wú)向完全圖（Undirected Complete Graph）

無(wú)向完全圖的任意兩個(gè)頂點(diǎn)之間都存在邊

所以，n個(gè)頂點(diǎn)的無(wú)向完全圖有n(n - 1) / 2條邊，即(n - 1) + (n - 2) + ( n - 3) + ... + 3 + 2 + 1

有向完全圖（Directed Complete Graph）

有向完全圖的任意兩個(gè)頂點(diǎn)之間，都存在方向相反的兩條邊

所以，n個(gè)頂點(diǎn)的有向完全圖有n(n - 1)條邊

稠密圖（Dense Graph）

如果邊數(shù)接近于或者等于完全圖，則稱(chēng)該圖為稠密圖（上圖也是一個(gè)稠密圖）

稀疏圖（Sparse Graph）

如果邊的數(shù)量遠(yuǎn)遠(yuǎn)少于完全圖，就成為稀疏圖

有權(quán)圖（Weighted Graph）

有權(quán)圖的邊可以擁有權(quán)值（Weight），例如下圖的有向圖，每一條邊可以帶上一個(gè)權(quán)值，權(quán)值代表一定的含義。

下圖表示兩個(gè)地點(diǎn)之間來(lái)往，所消耗的成本

當(dāng)前，權(quán)值不僅僅可以是整數(shù)，還可以是小數(shù)，負(fù)數(shù)。根據(jù)情況而定，甚至還可以是自定義對(duì)象

連通圖（Connected Graph）

1. 如果頂點(diǎn)x和y之間存在可相互抵達(dá)的路徑（直接或間接的路徑），則稱(chēng)x和y是連通的。
2. 如果無(wú)向圖G中任意兩個(gè)頂點(diǎn)都是連通的，則稱(chēng)G為連通圖[如下圖所示]

連通分量（Connected Component）

連通分量：無(wú)向圖的幾大連通子圖（盡可能多的連通子圖，子圖：圖中的圖）

• 連通圖只有一個(gè)連通分量，即其自身；非連通的無(wú)向圖有多個(gè)連通分量

根據(jù)上面的定義，可以知道，下面的無(wú)向圖有3個(gè)連通分量

強(qiáng)連通圖（Strongly Connected Graph）

如果有向圖G中任意兩個(gè)頂點(diǎn)都是連通的，則稱(chēng)G為強(qiáng)連通圖[如下圖所示]

強(qiáng)連通分量（Strongly Connected Component）

強(qiáng)連通分量：有向圖的極大強(qiáng)連通子圖

• 強(qiáng)連通圖只有一個(gè)連通分量，即其自身，非強(qiáng)連通的有向圖有多個(gè)強(qiáng)連通分量

以上，就是關(guān)于圖的一些基本概念，內(nèi)容比較多，相信如果是第一次學(xué)習(xí)相關(guān)知識(shí)的話，很難記得住，不過(guò)沒(méi)有關(guān)系，只要有一個(gè)印象即可，后面會(huì)在使用中慢慢熟悉。

圖的實(shí)現(xiàn)方案

前面介紹了一大堆與圖相關(guān)的概念。那如果現(xiàn)在需要用代碼來(lái)表達(dá)一個(gè)圖，實(shí)現(xiàn)方案是怎么樣的呢？圖一般來(lái)講，有2中實(shí)現(xiàn)方案，分別為

• 鄰接矩陣（Adjacency Matrix）
• 鄰接表（Adjacency List）

接下來(lái)就來(lái)了解這兩種方案有什么區(qū)別

鄰接矩陣（Adjacency Matrix）

鄰接矩陣的存儲(chǔ)方式

• 用一維數(shù)組存放頂點(diǎn)信息
• 用二維數(shù)組存放邊信息

存儲(chǔ)無(wú)向圖

例如現(xiàn)在有如下圖所示的無(wú)向圖

首先，有一個(gè)存放頂點(diǎn)的一維數(shù)組，存放著上圖中的4個(gè)頂點(diǎn)

然后，邊用二維數(shù)組來(lái)進(jìn)行表達(dá)，由于現(xiàn)在每一條邊沒(méi)有權(quán)值，所以兩個(gè)頂點(diǎn)之間的值，如果為1，就邊數(shù)存在邊，為0就不存在邊，所以上面的圖可以通過(guò)下圖的二維邊數(shù)組進(jìn)行表示。所以，一個(gè)頂點(diǎn)到另外一個(gè)頂點(diǎn)，有沒(méi)有邊，通過(guò)矩陣就可以表示清楚了

可以發(fā)現(xiàn)，如果是這種無(wú)向圖，通過(guò)鄰接矩陣的方式來(lái)存儲(chǔ)的話，數(shù)據(jù)有一點(diǎn)冗余，例如V0到V2,V2到V0都存儲(chǔ)了一次，這兩次存儲(chǔ)其實(shí)是有一點(diǎn)重復(fù)的

存儲(chǔ)有向圖

如果用鄰接矩陣來(lái)表示有向圖的話[下圖]

首先，這個(gè)有向圖與無(wú)向圖的頂點(diǎn)是一樣的，所以頂點(diǎn)數(shù)組是一樣的，存放著所有的頂點(diǎn)

邊仍然是使用二維數(shù)組來(lái)進(jìn)行存儲(chǔ)，但是存儲(chǔ)的內(nèi)容卻有所不同，首先仍然使用0表示兩個(gè)頂點(diǎn)時(shí)間沒(méi)有邊，1表示兩個(gè)頂點(diǎn)之間有邊，由于是有向圖，所以邊數(shù)組中的存儲(chǔ)的每一條邊都有一條唯一的邊進(jìn)行對(duì)應(yīng)，所以數(shù)據(jù)不冗余

所以，鄰接矩陣比較適合稠密圖。因?yàn)猷徑泳仃嚳梢员硎敬罅康倪呅畔?，否則就會(huì)造成內(nèi)存的浪費(fèi)，因?yàn)槿绻鎯?chǔ)的是稀疏圖，則會(huì)在矩陣中存儲(chǔ)大量的0，導(dǎo)致內(nèi)存浪費(fèi)。

存儲(chǔ)有權(quán)圖

如果現(xiàn)在有如下所示的一個(gè)有權(quán)圖

那在鄰接矩陣中應(yīng)該如何進(jìn)行存儲(chǔ)呢？

首先存儲(chǔ)頂點(diǎn)與前面的存儲(chǔ)方式一致，利用一個(gè)一維數(shù)組存放頂點(diǎn)

存儲(chǔ)邊時(shí)，就有一些區(qū)別了，由于是有權(quán)值的圖，所以在存儲(chǔ)邊時(shí)，需要存儲(chǔ)兩個(gè)頂點(diǎn)對(duì)應(yīng)邊的權(quán)值，如果兩個(gè)頂點(diǎn)之間沒(méi)有邊，則使用無(wú)窮大來(lái)表示，所以最終表示的結(jié)果如下

可以發(fā)現(xiàn)，利用鄰接矩陣來(lái)表示圖中頂點(diǎn)與邊之間的關(guān)系，還是比較簡(jiǎn)單的，但是在某些時(shí)候，可能會(huì)導(dǎo)致內(nèi)存的浪費(fèi)。所以接下來(lái)研究鄰接表是如何實(shí)現(xiàn)的。

鄰接表（Adjacency List）

鄰接表，利用一個(gè)一維數(shù)組就可以存儲(chǔ)了，數(shù)組中的每一個(gè)元素是一個(gè)鏈表對(duì)象。存儲(chǔ)方式如下

存儲(chǔ)無(wú)向圖

現(xiàn)在有如下的一個(gè)無(wú)向圖

如果使用無(wú)向圖來(lái)進(jìn)行存儲(chǔ)的話，最終存儲(chǔ)的結(jié)果如下

表達(dá)的意思是這樣的，

1. 首先從圖中可以知道頂點(diǎn)V0可以到達(dá)V1，V2，V3，所以在頂點(diǎn)V0后面，就跟著1,2,3這3個(gè)節(jié)點(diǎn)，就代表V0能通往這三個(gè)節(jié)點(diǎn)
2. V1可以到達(dá)V0，V2，所以在頂點(diǎn)V1后面，跟著0,2這兩個(gè)節(jié)點(diǎn)，就代表V1可以通往這兩個(gè)節(jié)點(diǎn)
3. 以此類(lèi)推。。。

可以發(fā)現(xiàn)，使用鄰接表，在表示圖時(shí)，只存儲(chǔ)了當(dāng)前頂點(diǎn)可以到達(dá)的頂點(diǎn)，不會(huì)存儲(chǔ)其他無(wú)法到達(dá)的頂點(diǎn)，這樣的話， 就不會(huì)導(dǎo)致內(nèi)存浪費(fèi)

存儲(chǔ)有向圖

所以，如果你用鄰接表存儲(chǔ)如下的有向圖

在鄰接表中存儲(chǔ)的結(jié)果如下，由于是有向圖，所以鄰接表與逆鄰接表來(lái)進(jìn)行表示，其中鄰接表表示當(dāng)前節(jié)點(diǎn)可以到達(dá)的節(jié)點(diǎn)，如下所示

逆鄰接表表示哪些節(jié)點(diǎn)可以到達(dá)當(dāng)前節(jié)點(diǎn)，例如V0可以通過(guò)V1，V2節(jié)點(diǎn)到達(dá)，所以在逆鄰接表中，V0后面，就跟著1,2，其他頂點(diǎn)以此類(lèi)推即可

存儲(chǔ)有權(quán)圖

如下所示的有權(quán)圖

利用鄰接表進(jìn)行存儲(chǔ)如下

與前面的無(wú)向圖/有向圖存儲(chǔ)方式相似，唯一的區(qū)別是在存儲(chǔ)當(dāng)前頂點(diǎn)可以到達(dá)的頂點(diǎn)時(shí)，需要存儲(chǔ)兩個(gè)頂點(diǎn)之間的權(quán)值

結(jié)合前面的分析，現(xiàn)在可以著手實(shí)現(xiàn)一個(gè)圖了。

圖的實(shí)現(xiàn)

前面分析知道，圖是由頂點(diǎn)和邊組成的，所以肯定會(huì)定義兩個(gè)對(duì)應(yīng)的類(lèi)與頂點(diǎn)和邊進(jìn)行對(duì)應(yīng)。

• 頂點(diǎn)類(lèi)中存儲(chǔ)的數(shù)據(jù)
  • 頂點(diǎn)的值
  • 以頂點(diǎn)出去的邊
  • 以頂點(diǎn)進(jìn)來(lái)的邊

所以可以通過(guò)這種方式，定義一個(gè)頂點(diǎn)類(lèi)

private static class Vertex<V,E> {
    V value;
    Set<Edge<V,E>> inEdges = new HashSet<>();
    Set<Edge<V,E>> outEdges = new HashSet<>();
}

• 邊類(lèi)中存儲(chǔ)的數(shù)據(jù)
  • 出發(fā)到當(dāng)前頂點(diǎn)的頂點(diǎn)
  • 當(dāng)前頂點(diǎn)出發(fā)到的頂點(diǎn)
  • 權(quán)值

所以，邊的定義如下

private static class Edge<V,E> {
    Vertex<V,E> from;
    Vertex<V,E> to;
    E weight;
}

好的，頂點(diǎn)和邊定義好以后，就可以添加頂點(diǎn)和邊了。

添加頂點(diǎn)

public void addVertex(V v) {
    if (vertices.containsKey(v)) return;
    vertices.put(v,new Vertex<>(v));
}

添加邊

public void addEdge(V from, V to, E weight) {
    //判斷 from to頂點(diǎn)是否存在
    Vertex fromVertex = vertices.get(from);
    if (fromVertex == null) {
        fromVertex = new Vertex(from);
        vertices.put(from,fromVertex);
    }
    Vertex toVertex = vertices.get(to);
    if (toVertex == null) {
        toVertex = new Vertex(to);
        vertices.put(to,toVertex);
    }
    Edge edge = new Edge(fromVertex,toVertex);
    edge.weight = weight;
    if (fromVertex.outEdges.remove(edge)){
        toVertex.inEdges.remove(edge);
        edges.remove(edge);
    }
    fromVertex.outEdges.add(edge);
    toVertex.inEdges.add(edge);
    edges.add(edge);
}

刪除邊

public void removeEdge(V from, V to) {
    Vertex fromVertex = vertices.get(from);
    if (fromVertex == null) return;
    Vertex toVertex = vertices.get(to);
    if (toVertex == null) return;

    Edge edge = new Edge(fromVertex,toVertex);
    if (fromVertex.outEdges.remove(edge)){
        toVertex.inEdges.remove(edge);
        edges.remove(edge);
    }
}

刪除頂點(diǎn)

public void removeVertex(V v) {
    Vertex<V,E> vertex = vertices.remove(v);
    if (vertex == null) return;
    //刪除頂點(diǎn)相關(guān)聯(lián)的邊
    //使用迭代器進(jìn)行刪除
    for (Iterator<Edge<V,E>> iterator = vertex.outEdges.iterator(); iterator.hasNext() ;)   {
        Edge<V,E> edge = iterator.next();
        edge.to.inEdges.remove(edge);
        iterator.remove();//將當(dāng)前遍歷到的元素edge從集合vertex.outEdges中刪掉
        edges.remove(edge);
    }

    for (Iterator<Edge<V,E>> iterator = vertex.inEdges.iterator(); iterator.hasNext() ;)    {
        Edge<V,E> edge = iterator.next();
        edge.from.outEdges.remove(edge);
        iterator.remove();//將當(dāng)前遍歷到的元素edge從集合vertex.outEdges中刪掉
        edges.remove(edge);
    }
}

所以到這里，圖的添加頂點(diǎn)，添加邊，刪除頂點(diǎn)，刪除邊都已經(jīng)實(shí)現(xiàn)了。接下來(lái)研究一下如何對(duì)圖進(jìn)行遍歷

遍歷

圖的遍歷

• 從圖中某一頂點(diǎn)出發(fā)訪問(wèn)圖中其余頂點(diǎn)，且每個(gè)頂點(diǎn)僅被訪問(wèn)一次

圖有2中常見(jiàn)的遍歷方式（有向圖，無(wú)向圖都適用）

• 廣度優(yōu)先搜索（Breadth First Search，BFD），又稱(chēng)為寬度優(yōu)先搜索，橫向優(yōu)先搜索
• 深度優(yōu)先搜索（Depth First Search，DFS）

發(fā)明“深度優(yōu)先搜索”算法的2為科學(xué)家在1986年共同獲得計(jì)算機(jī)領(lǐng)域的最高獎(jiǎng)：圖靈獎(jiǎng)

關(guān)于這兩種搜索遍歷方式，將會(huì)在后面的章節(jié)中繼續(xù)介紹。

demo下載地址

完！