# 圖 > 開頭還是求點贊，求轉發！原創優質公眾號，希望大家能讓更多人看到我們的文章。 > > 圖片都是我們手繪的，可以說非常用心了！ 圖是一種較為復雜的非線性結構。 **為啥說其較為復雜呢？** 根據前面的內容，我們知道： - 線性數據結構的元素滿足唯一的線性關系，每個元素(除第一個和最后一個外)只有一個直接前趨和一個直接后繼。 - 樹形數據結構的元素之間有著明顯的層次關系。 但是，樹形結構的元素之間的關系是任意的。 **何為圖呢？** 簡單來說，圖就是由頂點的有窮非空集合和頂點之間的邊組成的集合。通常表示為：**G(V,E)**，其中，G表示一個圖，V表示頂點的集合，E表示邊的集合。 下圖所展示的就是圖這種數據結構，并且還是一張有向圖。  圖在我們日常生活中的例子很多！比如我們在社交軟件上好友關系就可以用圖來表示。 ## 圖的基本概念 ### 頂點 圖中的數據元素，我們稱之為頂點，圖至少有一個頂點（非空有窮集合） 對應到好友關系圖，每一個用戶就代表一個頂點。 ### 邊 頂點之間的關系用邊表示。 對應到好友關系圖，兩個用戶是好友的話，那兩者之間就存在一條邊。 ### 度 度表示一個頂點包含多少條邊，在有向圖中，還分為出度和入度，出度表示從該頂點出去的邊的條數，入度表示進入該頂點的邊的條數。 對應到好友關系圖，度就代表了某個人的好友數量。 ### 無向圖和有向圖 邊表示的是頂點之間的關系，有的關系是雙向的，比如同學關系，A是B的同學，那么B也肯定是A的同學，那么在表示A和B的關系時，就不用關注方向，用不帶箭頭的邊表示，這樣的圖就是無向圖。 有的關系是有方向的，比如父子關系，師生關系，微博的關注關系，A是B的爸爸，但B肯定不是A的爸爸，A關注B，B不一定關注A。在這種情況下，我們就用帶箭頭的邊表示二者的關系，這樣的圖就是有向圖。 ### 無權圖和帶權圖 對于一個關系，如果我們只關心關系的有無，而不關心關系有多強，那么就可以用無權圖表示二者的關系。 對于一個關系，如果我們既關心關系的有無，也關心關系的強度，比如描述地圖上兩個城市的關系，需要用到距離，那么就用帶權圖來表示，帶權圖中的每一條邊一個數值表示權值，代表關系的強度。  ## 圖的存儲 ### 鄰接矩陣存儲 鄰接矩陣將圖用二維矩陣存儲，是一種較為直觀的表示方式。 如果第i個頂點和第j個頂點之間有關系，且關系權值為n，則 `A[i][j]=n` 。 在無向圖中，我們只關心關系的有無，所以當頂點i和頂點j有關系時，`A[i][j]`=1，當頂點i和頂點j沒有關系時，`A[i][j]`=0。如下圖所示：  值得注意的是：**無向圖的鄰接矩陣是一個對稱矩陣，因為在無向圖中，頂點i和頂點j有關系，則頂點j和頂點i必有關系。**  鄰接矩陣存儲的方式優點是簡單直接（直接使用一個二維數組即可），并且，在獲取兩個定點之間的關系的時候也非常高效（直接獲取指定位置的數組元素的值即可）。但是，這種存儲方式的缺點也比較明顯，那就是比較浪費空間， ### 鄰接表存儲 針對上面鄰接矩陣比較浪費內存空間的問題，誕生了圖的另外一種存儲方法—**鄰接表** 。 鄰接鏈表使用一個鏈表來存儲某個頂點的所有后繼相鄰頂點。對于圖中每個頂點Vi，把所有鄰接于Vi的頂點Vj鏈成一個單鏈表，這個單鏈表稱為頂點Vi的 **鄰接表**。如下圖所示：   大家可以數一數鄰接表中所存儲的元素的個數以及圖中邊的條數，你會發現： - 在無向圖中，鄰接表元素個數等于邊的條數的兩倍，如左圖所示的無向圖中，邊的條數為7，鄰接表存儲的元素個數為14。 - 在有向圖中，鄰接表元素個數等于邊的條數，如右圖所示的有向圖中，邊的條數為8，鄰接表存儲的元素個數為8。 ## 圖的搜索 ### 廣度優先搜索 廣度優先搜索就像水面上的波紋一樣一層一層向外擴展，如下圖所示：  **廣度優先搜索的具體實現方式用到了之前所學過的線性數據結構——隊列** 。具體過程如下圖所示： **第1步：**  **第2步：**  **第3步：**  **第4步：**  **第5步：**  **第6步：**  ### 深度優先搜索 深度優先搜索就是“一條路走到黑”，從源頂點開始，一直走到沒有后繼節點，才回溯到上一頂點，然后繼續“一條路走到黑”，如下圖所示：  **和廣度優先搜索類似，深度優先搜索的具體實現用到了另一種線性數據結構——棧** 。具體過程如下圖所示： **第1步：**  **第2步：**  **第3步：**  **第4步：**  **第5步：**  **第6步：**