1 引言

線性數據結構的元素滿足唯一的線性關系，每個元素（初第一個和最后一個外）只有一個直接前趨和一個直接后繼。樹形數據結構的元素之間有著明顯的層次關系。但是圖形結構的元素之間的關系是任意的。

什么是圖？

簡單來說，圖就是由頂點的有窮非空集合和頂點之間的邊組成的集合。通常表示為：G（V,E），其中，G表示一個圖，V表示頂點的集合，E表示邊的集合。

上圖所展示的就是圖，而且是一個有向圖（帶箭頭）?

2 圖的基本概念

拿好友關系舉例

2.1 頂點

圖中的數據元素我們稱之為頂點，圖中至少有一個頂點（非空有窮集合）

對應到好友關系圖，每一個用戶就代表一個頂點。

2.2 邊

頂點之間的關系用邊表示。

對應到好友關系圖，兩個用戶是好友的話，那兩者之間就存在一條邊。

2.3 度

度表示一個頂點包含多少條邊，在有向圖中，還分為出度和入度，出度表示從該頂點出去的邊的條數，入度表示進入該頂點的邊的條數。

對應到好友關系圖，度就代表了某個人的好友數量。

2.4 無向圖和有向圖

邊表示的是頂點之間的關系，有的關系是雙向的，比如同學，A是B的同學，那么B也肯定是A的同學，那么在表示A和B的關系時，就不用關注方向，用不帶箭頭的邊表示，這樣的圖就是無向圖。

有的關系是有方向的，比如抖音，我關注了你，你沒有關注我，這樣我們之間的關系就是單向的，我們用箭頭表示二者之間的關系，這樣的圖就是有向圖。

2.5 無權圖和帶權圖

對于一個關系，如果我們只關心關系的有無，而不關心關系有多強，那么就可以用無權圖來表示二者的關系。

對于一個關系，如果我們既關心關系的有無，也關心關系的強度，比如某某某的好感度，你對人家好感度百分百，人家對你好感度百分之零（一個悲傷的故事），那么就可以用帶權圖來表示，帶權圖中每一條邊用一個數值表示權值，代表關系的強度。

把上面的有向圖進行加工就是一個帶權有向圖

3 圖的存儲

3.1 鄰接矩陣存儲

鄰接矩陣將圖用二維矩陣存儲，是一種較為直觀的表示方式。

如果第i個頂點和第j個頂點之間有關系，且關系權值為n，則A[i][j]=n。

在無向圖中，我們只關心關系的有無，所以當頂點i和頂點j有關系時，A[i][j]=1，當頂點i和頂點j沒有關系時，A[i][j]=0。如下圖所示。

值得注意的是：無向圖的鄰接矩陣是一個對稱矩陣，因為在無向圖中，頂點i和頂點j有關系，那么就必定是雙方的。

鄰接矩陣存儲的方式優點是簡單直接（直接用一個二維數組即可），并且，在獲取兩個頂點之間的關系時也非常高效（直接獲取指定位置的數組元素的值即可）。但是吧，這種存儲方式的缺點也很明顯，那就是比較浪費空間。

3.2?鄰接表存儲

針對上面鄰接矩陣比較浪費內存空間的問題，誕生出了另外一種存儲方法--鄰接表。

鄰接鏈表使用一個鏈表來存儲某個頂點的所有后繼相鄰頂點。對于圖中每個頂點Vi，把所有鄰接于Vi的頂點Vj鏈成一個單鏈表，這個單鏈表稱為頂點Vi的鄰接表。如下圖所示：

可以數一數鄰接表中所存儲的元素的個數以及圖中邊的條數：

在無向圖中，鄰接表元素個數等于邊的條數的兩倍，如左圖所示的無向圖中，邊的條數為7，鄰接表存儲的元素個數為14。

在有向圖中，鄰接表元素個數等于邊的條數，邊的條數為8，那么鄰接表存儲的元素個數就為8.?

4 圖的搜索?

4.1 廣度優先搜索

廣度優先搜索是一層一層向外擴展的

廣度優先搜索的具體實現方式用到了之前學過的線性數據結構--隊列。具體過程如下所示?

4.2 深度優先搜索

深度優先搜索就是從原頂點開始，一直走到沒有后繼節點，才回溯到上一頂點，然后繼續往下走。

?

注意：搜索順序是不唯一的，如果給出了鏈表或矩陣的存儲方式，如下就是用單鏈表存儲，那么搜索順序就是固定的。?

?深度優先搜索的具體實現用到了另一種線性數據結構--棧。（隊列和棧可以從我線性數據結構一文中了解數據結構秘籍（一）線性數據結構（數組、鏈表、棧、隊列一次看完）-CSDN博客）過程如下：

?