建立一張圖

鄰接串列

在知道圖是什麼之後，接著要來看的是如何在 C++ 中儲存一張圖。

在大部分的情況下，我們會以節點關係來儲存一張圖，不過「關係」究竟是指什麼呢？

這裡先繼續沿用上個章節的圖來當例子：

仔細觀察上面的圖，我們可以發現這些「關係」：

節點 1 會連接到節點 2 跟 3
節點 2 會連接到節點 1 跟 3
節點 3 會連接到節點 2 跟 4
節點 4 會連接到節點 3 跟 5
節點 5 會連接到節點 4 

而我們實際上在程式要存的資料大概長這樣：

節點 -> [連接到哪些節點]

1 -> [2, 3]
2 -> [1, 3]
3 -> [2, 4]
4 -> [3, 5]
5 -> [4]

C++ 中可以使用傳統陣列套 vector 來實現：

// MAXN 最大節點數量
vector<int> graph[MAXN];

// 下面的操作就是相當於我們從節點 1 建立了兩條邊分別指向 2 跟 3
graph[1].push_back(2);
graph[1].push_back(3);

這種存法就叫做「鄰接串列」。

邊權與點權

在一些題目中，可能會出現「邊權」與「點權」的概念。在題目的情境中，邊權常常是用來指路徑的長度，而點權有時候是用來代表某個地方上有價值多少的寶藏之類的。

如下圖，通常會把邊權（紅色）寫在邊旁邊，點權（藍色）寫在點旁邊。

先來談談點權，如果要儲存點權的話，一般會直接利用一個陣列來存，index 為節點編號，值為點權。

// 節點 1 的點權是 2
w[1] = 2;
// 節點 2 的點權是 4
w[2] = 4;
// 節點 3 的點權是 1
w[3] = 1;
// 節點 4 的點權是 7
w[4] = 7;
// 節點 5 的點權是 3
w[5] = 3;

再來是邊權，如果我們要儲存邊權的話，需要稍微修改一下鄰接串列的存法。

在前面，我們說這樣代表點 1 存在一條連接到點 2 的邊：

graph[1].push_back(2);

加上邊權的話我們通常會使用一個 pair 來同時紀錄邊權與連接到哪個點。像是下面這段程式碼的意思就是：節點 1 存在一條連接到點 2 的邊，且該條邊的權重為 5。

graph[1].push_back({2, 5});

鄰接矩陣

接下來我們要介紹另一種圖的存法，雖然較不常出現，但在某些特定的演算法或題目中還是非常重要的，這種存法就要做 「鄰接矩陣」。

鄰接矩陣的概念就是透過一個矩陣來儲存每個點之間的關係，假設 $mat[1][2]$ 為 5 就代表存在一條 1 連到 2 的邊，且權重為 5。

繼續拿這張圖舉例，如果把它存在鄰接矩陣就會變成下圖這樣（空白格子代表不存在路徑，程式中通常使用一個非常大的數字或 -1 來表示）：

可以發現整個矩陣是沿著一條左上到右下的線對稱的，這是因為我們存的圖是無向的，所以對於每個 $mat[x][y]$ 都等於 $mat[y][x]$，因為從 $x$ 可以走到 $y$ 而且 $y$ 也可以通過同一條邊走回 x。

如果沒有邊權的話，一般就會直接儲存 1 代表有路徑 0 代表沒路徑。

而點權的存法跟鄰接串列一樣。