圖解：什麼是「圖」？
從今天開始，我們開始介紹圖的相關算法 圖解：什麼是「圖」？
1、背景
作為圖的開始，我們先來看一個經典的問題，它被認為是圖論的起源。
這個問題是基於一個現實生活中的事例：河中心有兩個小島。小島與河的兩岸有七條橋連接。在所有橋都只能走一遍的前提下，如何才能把這個地方所有的橋都走遍？
歐拉在1735年提出，並沒有方法能圓滿解決這個問題，他更在第二年發表在論文《柯尼斯堡的七橋》中，證明符合條件的走法並不存在
歐拉把實際的抽象問題簡化為平面上的點與線組合，每一座橋視為一條線，橋所連接的地區視為點。這樣若從某點出發後最後再回到這點，則這一點的線數必須是偶數，這樣的點稱為偶頂點。相對的，連有奇數條線的點稱為奇頂點。由於柯尼斯堡七橋問題中存在4個奇頂點，它無法實現符合題意的遍歷。
之後，不少數學家都嘗試去解析這類事例。而這些解析，最後發展成為了數學中的圖論233。
2、圖的概念
圖的定義：圖是由一組頂點和一組能夠將兩個頂點相連的邊組成的
圖是一種非線性表數據結構，圖中的元素我們叫做頂點，圖中建立的連接關係我們叫做邊。，圖主要分為四種：無向圖、有向圖、加權圖、加權有向圖。
我們把有邊有方向的圖叫做「有向圖」，把邊沒有方向的圖叫做「無向圖」，把邊帶有權重的圖叫做「加權圖」，這些概念其實都比較容易理解，你可以參考下面的幾幅圖對比一下。我們可以分別類比生活中的：知乎關注（有向）、微信交友（無向）和QQ好友親密度（帶權值）。
在圖的表示中，我們定義度的概念。對於無向圖而言，一個頂點的度是指跟該頂點相連接的邊的條數；對於有向圖而言，我們分別定義入度和出度，頂點的入度表示有多少條邊指向這個節點，頂點的出度表示有多少條邊以這個節點為起點指向其他節點。
3、圖的存儲方法
圖的存儲方法主要有兩種：鄰接表（Adjacency List）和鄰接矩陣（Adjacency Matrix）。我們首先來介紹一下這兩種存儲方法。
1.鄰接矩陣
鄰接矩陣，顧名思義，就是利用矩陣去描述圖，它的底層依賴於一個二維數組。對於無向圖而言，如果頂點i與頂點j之間有邊，那麼我們就把A[i][j]和A[j][i]標記為1，它們之間沒有邊就標記為0；對於有向圖而言，如果頂點 i 到頂點 j 之間，有一條箭頭從頂點 i 指向頂點 j 的邊，那我們就將 A[i][j]標記為 1。同理，如果有一條箭頭從頂點j 指向頂點 i 的邊，我們就將 A[j][i]標記為 1。對於帶權圖，數組中就存儲相應的權重。
我們使用鄰接矩陣來表示圖，雖然的確很直觀明了，但是卻比較浪費空間。
其一，對於無向圖來說，A[i][j]永遠等於A[j][i]，我們只需要使用一半矩陣就可以成功地表示，那另一半空間就被浪費掉了；
其二、如果我們存儲的是稀疏圖，也就是頂點很多，但每個頂點的邊並不很多，此時鄰接矩陣的存儲方法就更加浪費空間了。好比微信有好幾億的用戶，對應到圖上就是好幾億的頂點。但是每個用戶的好友並不會很多，一般也就幾百個而已。如果我們用鄰接矩陣來存儲，那絕大部分的存儲空間都被浪費了。
總結一下，當圖為稀疏圖、頂點較多，即圖結構比較大時，更適宜選擇鄰接表作為存儲結構。當圖為稠密圖、頂點較少時，使用鄰接矩陣作為存儲結構較為合適。
2.鄰接表
我們使用一個以頂點為索引的列表數組，其中數組中的每個元素都指向一個單獨的鏈表，該鏈表存儲了與數組中頂點相鄰的所有頂點。有點繞口，不過我為你準備了一張圖，我相信結合圖片你肯定可以更好地理解。
相比於鄰接矩陣，鄰接表比較節省存儲空間，但是使用起來卻比較耗費時間。不過，它的形式更為自由和靈活，比如，在鏈表過長的情況下，我們可以把鏈表用平衡二叉查找樹（紅黑樹）替代，這樣的話就比較高效了。
3.代碼實現
public class Graph{
//無向圖
private int v;//頂點的個數
private LinkedList<Integer> adj[];//鄰接表
public Graph(int v){
this.v=v;
adj=new LinkedList[v];
for(int i=0;i<v;++i){
adj[i]=new LinkedList<>();
}
}
public void addEdge(int s,int t){
//無向圖一條邊存兩次
adj[s].add(t);
adj[t].add(s);
}
}
好了，關於圖的內容就到這裡了，我希望通過這篇文章你對於圖有了一個初步的認識！下一次，我們會介紹深度優先搜索和廣度優先搜索，小超與你不見不散！
碼字繪圖不易，如果覺得本文對你有幫助，關注作者就是最大的支持！順手點個在看更感激不盡！
歡迎大家關注我的公眾號：小超說，之後我會繼續創作算法與數據結構以及計算機基礎知識的文章。也可以加我微信 chao_hey 我們一起交流，一起進步！
