為什麼QQ能幫你找到失散多年的兄弟？—-圖論

• 2019 年 12 月 11 日
• 筆記

編程三分鐘的第 44 篇原創文章

為什麼qq里「可能認識的人」功能推薦的如此精準？ 為什麼兩個沒有什麼聯繫的朋友會相互認識？

一切的背後到底是道德的淪喪,還是人性的扭曲 ？ 讓我們走進圖的內心世界！

什麼是圖？

微信好友之間的關係像一張巨大的網絡，朋友的朋友可能是自己的朋友，所以用一種叫 圖 的數據結構儲存起來，元素和元素之間都可能發生關係。

下面要開始乾貨了！非戰鬥成員請撤離，圖有兩種有向圖和無向圖，唯一的區別就是有木有箭頭，是不是看起來很像關係網。

來說說它的細節

圖上的東西全都有名字，圓圈 圈着字母叫 頂點，是最基本的組成元素。

連接各個頂點的線就是 邊，圖 可以沒有 邊，但是不能沒有 頂點 。連接某個頂點的邊數量叫做這個頂點的 度。比如上圖中的 C 有三個度。

有向圖多一個概念，那就是出度，入度。比如 C 頂點，有兩個箭頭指向自己，一個箭頭指出來，就是兩 入度，一 出度。

結合上面的幾個概念，來做點題目，如圖：

如何存儲圖

經過我精彩的表達，想必你肯定知道了圖的基本概念，作為一個技術人員，刨根問底才是我們的特色。

有沒有想過長的這麼瘋狂的一個數據結構，他是怎麼存的？

因為要表現出來每個頂點都有可能指向其他頂點，所以有兩種常見的儲存方式，二維數組 和 鄰接表。

使用鄰接矩陣（二維數組）存儲

下面就是非常明顯的二維數組存儲圖的例子。

上圖是 8 * 8 的二維數組，豎著和橫着都是各個 頂點，比如 開發 、設計 、工程 都是頂點。

每一行都代表當前這個人對其他 8 個人的看法（包括自己），在圖裡就只有 有關係 和 沒關係 兩種看法而已。

例如上圖， A – G 共 7 個頂點，所以需要 7 * 7 的二維數組。

橫坐標代表着當前的節點，縱坐標代表當前節點和其他節點的關係，加入當前節點有 出度，那麼當前的值就為 1 ，入度不管，拆解如下：

頭髮少叫頭髮稀疏，1 少就叫 稀疏矩陣，指的就是圖的各個頂點之間的聯繫很少，存了沒意義的 0 ，使得大量的二維數組數組空間被浪費。

使用鄰接表（鏈表）存儲

如上面的 圖，對其使用 鏈表 來存儲，略像哈希表，每行都是一個節點，每列也只存儲這個節點的所有 出度。

兩種存儲方式的比較

我們要根據不同的情況來決定不同的存儲數據結構：

（1）數組：浪費空間，但是速度快。適合處理數據不大的，只要數據不大，優先選用數組

（2）鏈表：節省空間，但是速度慢。數據大的時候，使用鄰接表（鏈表來存儲）