在我看來，想要掌握圖的基礎應用，僅需要三步走。

什么是圖（基本概念）、圖的構造（打地基）、圖的遍歷方式（應用的基礎）

只要能OK的掌握這三步、就算圖論入門了！！！

當然新手也不要恐懼啥的，新知識嘛，就是需要一個接受的過程。

學術上，是這么稱圖的：?

圖由頂點（Vertex）集合和（Edge）集合組成，通常表示G(v,e)

當然，這太學術了(～﹃～)~zZ

換句話說，圖，就是由頂點與邊組成的。

頂點就是各個節點。邊就是各個節點的關系or性質。

基本概念：

首先就是圖的種類，畢竟人還分不同膚色呢，就更不用說圖了。

圖分無向圖、有向圖。

無向圖，邊之間沒有方向。

有向圖，邊之間存在方向。

接下來，咱們講講度的概念。他在有向圖與無向圖中，分別有不同的含義。

在無向圖中，只有統一的 “度”（因為邊無方向）

度：與該節點有幾條邊相鄰。

如圖，節點1，有4條邊與其相連。故度為4。

在有向圖中，他分別是出度、入度與總度。

出度: 指向其他節點的邊。

入度: 其他節點指向本節點的邊。

總度: 出度+入度的總和。

如圖，節點1：出度（3）、入度（1）、總度（3+1=4）

接下來就講到，連通圖與強連通圖的概念。

連通圖是 圖中的概念。意思是每個節點之間，都能相互到達。

但是如果節點之間，無法相互抵達，就是非連通圖。

如下所示，左側每個節點之間，都能相互到達，為連通圖，而右側不是卻不能。為非連通圖。

強連通圖同樣也是每個節點之間，都能相互抵達，但是有個前提條件，必須按照邊的方向。

如圖左側，直接形成了閉環。故為 強連通圖。

而圖的右側，為非強連通圖（舉例：節點4 無法到達 節點3）

構造：

有三種構造方式。

拓撲儲存，鄰接矩陣、鄰接表。

拓撲儲存，雖然是Carl自創的名字，但我挺認同的(。?ω?。)

如圖，一共有8個節點，如果，想要將這8個節點儲存，需要8*2個單位。

如果存在二維數組中，大概需要建立一個二維數組儲存。

但是這樣的前提是，想要遍歷所有內容非常麻煩。（用map儲存，用的是同樣的效果）

鄰接矩陣

鄰接矩陣，通過二維數組來儲存。是從節點的角度來考慮的。有多大的節點，就分配，其平方大的數組。

如圖grid[2][5]=6，代表節點2與節點5之間，有一條節點，權值為6；

在有向圖中，grid[2][5]=6 表示為，節點2指向節點6；

在無向圖中，若向表示2與5之間有節點。grid[2][5]=6、grid[5][2]=6。

這樣聯動著表示。

優點：可以迅速查詢，兩點直接是否有聯通。

缺點：適用于稠密圖，若果節點變很少，會造成空間極大的浪費。

鄰接表

鄰接表是通過，數組+鏈表來儲存的。

優點：需要多少邊，就申請多少節點。

缺點：若要查詢兩點之間，是否連通。無法很快查詢到。

應用：

其實最后一部分，叫做圖的遍歷方式更好。

但為啥叫做應用呢，圖的應用不就是圖的遍歷嗎，通過各種遍歷解決問題。

圖的遍歷方式大概分為兩大類：

深度優先搜索（DFS），與廣度優先搜索（BFS）

其實圖的遍歷方式與樹的遍歷方式大差不差。

主要還是需要借助實戰。

從下一篇博客，就要開始實戰嘍。

注意??????，用Carl的話說，圖論是非常龐大的知識體系，以上只是一小部分理論基礎。

更多的，還是要考刷題積累。

接下來，我們要面對，深度優先搜索(dfs)、廣度優先搜索(bfs)、并查集、拓撲排序、最小生成樹系列、最短路徑系列....熱血沸騰吧！

---

借鑒博客：

1、圖論理論基礎

---