圖論是計算機的一種資料結構。在計算機科學中，一個圖就是一些頂點的集合，這些頂點透過一系列邊結對（連線）。頂點用圓圈表示，邊就是這些圓圈之間的連線。頂點之間透過邊連線。我們將從圖的儲存、DFS/BFS和圖的特殊形式樹這三方面來講解圖論的基礎內容。
首先我們來看看圖是如何儲存的。
觀察這個鄰接矩陣後我們可以發現幾個性質。
1。這個矩陣有n行n列。
2。這個矩陣的數值不是0，就是1。
在這裡我把這個矩陣稱為a，其中每個數值稱為ai，j，透過觀察，我們可以很容易發現，如果第i個點指向第j個點，那麼ai，j的值就為1，否則ai，j為0。比如a1，2=1但是a1，3=0
因為a是n行n列的，所以如果完全遍歷一邊，複雜度為O（n^2）。我們定義一個圖中的邊數為m，實際上m最大的情況下等於n^2。因此在m很大的時候（稠密圖），鄰接矩陣不失為一種非常方便，合適的方法。但是如果m非常小（稀疏圖），O（n^2）顯然耗時過長。那有沒有什麼方法接近O（m）呢？
是不是很明顯了？矩陣b中第i行的數字所代表的就是i與第i行的若干個結點相互連線。
每次遍歷的時候也只需要O（m）的時間複雜度，是不是很優秀？
當然一個演算法不可能面面俱到。雖然鄰接表時間複雜度低，佔用空間小，但我們考慮下面問題：
如果我們要查詢i和j兩點是否連線的時候。我們該用哪種方式儲存比較好？
首先考慮鄰接矩陣，根據定義，ai，j代表了i和j是否連線。時間複雜度O（1）。
然後我們考慮鄰接表，先找到第i行，然後將第i行所有的數字全部掃描一遍，看第i行是否出現數字j。時間複雜度最高為O（n）
所以我們不能盲目地只使用鄰接矩陣或者鄰接表，而是應該遇到題目選擇最適合的使用。
