# 基礎圖論 (四): 圖的表示與儲存 之前都是在講偏數學的觀點。這篇要把目光移回電腦上，在電腦中要儲存一張圖，需要使用相對應的資料結構，才能用點腦處理圖論問題 備註 : 這篇在沒有特別註明的情況下，圖都是 simple graph 備註 : 因為這是競程筆記，所以實作一定是 C/C++ ## 鄰接矩陣 Adjacency Matrix ### 無向簡單圖 Undirected Simple Graph 從[此系列的第一篇](https://hackmd.io/@ShanC/basic-graph-theory-1)就一直強調，邊是由 relation 定義。離散數學的課本也說，relation 可以用矩陣來表示。根據此性質，一張 simple graph 用矩陣來表示是很正常的一件事。然而，要將圖以矩陣表示，每個節點就必須有編號，才能使得每個行列具有意義 我們可以定義矩陣 $A_{i, j}=\begin{cases} 1 \text{, if } (i, j)\in E\\ 0 \text{, otherwise} \end{cases}$。對於以下右圖而言，他可以用右邊的矩陣表示 <center> <img src="https://hackmd.io/_uploads/ByUJrU8Deg.png" style="margin: 0 auto; display: block; width: 400px"> </center> $~$ 這個矩陣是對稱的。此外，若允許自環 (loop)，鄰接矩陣仍然可以表達，但是多重邊卻難以用矩陣表達，有時數字代表邊數，但**很多時候要視情況而定**。所以大多時候討論的都會是簡單圖 ### 有向簡單圖 Directed Simple Graph 想當然，有向圖是由 function 表示，因此也可以用鄰接矩陣表示，但矩陣不一定會對稱 <center> <img src="https://hackmd.io/_uploads/SySd9IUveg.png" style="margin: 0 auto; display: block; width: 400px"> </center> ### 程式實作 沒有很難，就只是二維陣列而已 ```cpp int n = 50; // 節點數 int graph[n][n]; ``` 空間複雜度沒什麼好說的，就是 $O(n^2)$，因此若要以鄰接矩陣確認整張圖的樣貌，時間也是 $O(n^2)$ ### 鄰接矩陣的缺點 在鄰接矩陣中，如果不是完全圖，那就一定會有為 $0$ 的元素。但大多數的狀況是，我們其實不需要知道「哪些點對有連邊」，因此儲存 $0$ 的那些空間顯然很浪費。若今天存的是一張邊數與點數差不多的圖，那麼這個效果會更明顯。可以想像，若有一個邊數是 $O(n)$ 的圖，但我們卻每次都用 $O(n^2)$ 的時間去遍歷整個資料結構，那麼一定會花非常多時間 ### 鄰接矩陣的優點 矩陣畢竟是一個數學物件，具有數學上的一些運算性質，像是行運算、列運算、冪次、生成函數或是特徵值等都是值得探討的事情，因此也很重要。只是電腦實作上我們更關心連通的狀況，相較之下，鄰接串列比較符合我們寫程式的需求 ## 圖同構 Isomorphism 由於矩陣與圖本質上是等價的，大多圖的性質都可以從鄰接矩陣找到。其實這算是代數圖論的範疇，不是競程會去討論的內容，以下就舉幾個例子讓你有點感覺 ### 定義 給定兩張圖 $A$ 與 $B$，若我們可以找出一個 bijection $f: V(A)\rightarrow V(B)$ 使得 $(u, v)\in E(A)$ 若且唯若 $(f(u), f(v))\in E(B)$，則稱為同構 ||事實上，群論中的同構也差不多是這樣定義|| ### 舉例說明 如下圖，$G$ 與 $H$ 就是同構 <center> <img src="https://hackmd.io/_uploads/ryWVpIUwgx.png" style="margin: 0 auto; display: block; width: 400px"> </center> 因為我們只要將 $G$ 的 $1$ 對應到 $H$ 的 $4$、$G$ 的 $2$ 對應到 $H$ 的 $2$、$G$ 的 $3$ 對應到 $H$ 的 $3$、$G$ 的 $4$ 對應到 $H$ 的 $1$ 他們的鄰接矩陣分別為 $A_G=\left[ \begin{array}{cccc} 0 & 0 & 1 & 0\\ 0 & 0 & 1 & 1\\ 1 & 1 & 0 & 0\\ 0 & 1 & 0 & 0\\ \end{array} \right]$ 與 $A_H=\left[ \begin{array}{cccc} 0 & 1 & 0 & 0\\ 1 & 0 & 1 & 0\\ 0 & 1 & 0 & 1\\ 0 & 0 & 1 & 0\\ \end{array} \right]$ 如上，若要判別是否同構，可以將 $A_G$ 的行與列的 $1$ 跟 $4$ 做交換，就可以得到相同的矩陣 ### 判斷同構 若要設計演算法來判別，可以窮舉所有的節點編號的排列組合，只要其中一種會使得矩陣長的一樣，則就是同構 ## 邊的數量 Number of Edges 完全圖擁有一張圖最多的邊數。有了資料結構，要推出一張 $n$ 個節點的圖最多的邊數就不是個問題。以下假設無向圖有 $n$ 個節點 ### 方法一 : 用矩陣計算邊數 鄰接矩陣總共有 $n^2$ 個元素，每個元素都代表行與列是否有邊相連。由於圖不存在自環，扣掉自環的邊數有 $n$ 條邊。因矩陣是對稱的，$r$ 連到 $c$ 與 $c$ 連到 $r$ 其實是相同一條邊，所以最後要除 $2$。因此得到共有 $\cfrac{n^2-n}{2}=\cfrac{n(n-1)}{2}$ 條邊 ### 方法二 : 算組合數 注意到每兩點之間必有一條邊，因此是 $C^{n}_{2}=\cfrac{n(n-1)}{2}$ ## 鄰接串列 Adjacency List 有人稱這個為鄰接表，反正都一樣 ### 說明 在這個資料結構裡面，我們只記錄兩節點的連接狀況，有邊就紀錄，沒邊就不理他。對於每個節點 $u$，鄰接串列只記錄 $u$ 有連到的節點 $v$。以下就給個圖，自行意會一下吧! <center> <img src="https://hackmd.io/_uploads/rk4W2LuDeg.png" style="margin: 0 auto; display: block; width: 400px"> </center> ### 程式實作 傳統上應該要用 linked list，但是因為這是競程筆記，所以我們還是用一些 vector 把他們都串起來就好。實際上，這算是一個二維陣列，只是因為 vector 可以調整大小、插入元素的緣故，因此這樣存就相當於用 linked list 存，效果差不多，只是空間可能會大一點，但還是跑得動 ```cpp int n = 50; // 節點數 vector<int> g[n]; ``` 若我們想要存入上面的例子，那可以做以下的操作 ```cpp g[1].push_back(2), g[1].push_back(4); g[2].push_back(1), g[2].push_back(6); g[3].push_back(5), g[3].push_back(6); g[4].push_back(1), g[4].push_back(5); g[5].push_back(3), g[5].push_back(4), g[1].push_back(6); g[6].push_back(2), g[6].push_back(3), g[6].push_back(5); ``` 以上例子是無向圖，如果是有向圖的話，可以自己想想看 ## 儲存帶權有向圖 有時候，我們要儲存的對象可能不是單純的有向 / 無向圖，像是若要計算兩點最短距離，那可能會在邊上賦值。圖上附加其他屬性的例子百百種，所以我們很常需要配合其他的資料結構來儲存圖的附加屬性 ### 點權 由於在電腦中，節點都是有編號的，因此一個一維陣列就足夠了 其他像是度數等性質也都是這樣完成儲存 ### 邊權 通常邊權在數學上的定義是 $f:E\rightarrow \mathbb{R}$，但是在競程通常只會碰整數，所以是 $f:E\rightarrow \mathbb{Z}$，但是這要如何儲存呢? 直觀上，從鄰接矩陣的定義來說，開一個二維陣列就可以解決，但是往往我們都是用鄰接串列來存才能避免用到太大的空間。因此我們只需要在鄰接串列上附加一個空間專門來存邊權即可 在實作上我們可以用 pair 來解決，剩下都一樣 ```cpp typedef pair<int, int> pii; vector<pii> vec[N]; // vec[u] = {v, w}: u 為起點, v 為終點, w 為路權 ``` 但凡事必有例外，像是 Floyd-Warshall 演算法就必須使用二維陣列 (矩陣) 來實作，而非鄰接串列 ## 邊陣列 Edge Array 不難發現其實一條邊其實就兩個終點而已，頂多再加上邊權，因此可以考慮直接開一個 pair / struct 陣列把所有邊的資訊儲存起來。要注意的是這種儲存方法並不適合遍歷。在 [Bellman-Ford 演算法](https://hackmd.io/@ShanC/Bellman-Ford-Algorithm)時會用到這種儲存方法 ### 無權邊 ```cpp= pair<int, int> edges[MXN]; // 這裡儲存邊的兩個終點 for(int i = 0; i < m; i++){ // 輸入可以這樣處理 cin >> edges[i].first >> edges[i].second; } ``` ### 帶權邊 ```cpp= struct Edge{ // 儲存兩終點 u, v 與邊的權重 w int u, v, w; }edge[MXN]; for(int i = 0; i < m; i++){ // 輸入可以這樣處理 cin >> edge[i].u >> edge[i].v >> edge[i].w; } ``` ## 題目練習 [Atcoder abc_232 C - Graph Isomorphism](https://atcoder.jp/contests/abc232/tasks/abc232_c) (圖同構裸題) ---- ## 參考資料 - Introduction to Algorithms, Fourth Edition - D.B.West - Introduction to Graph Theory 2/e ---- > 上一篇: [基礎圖論 (三)](https://hackmd.io/@ShanC/basic-graph-theory-3) > [ShanC 程式競賽筆記](https://hackmd.io/@ShanC/B1ouGxqcC) > 作者: ShanC > 更新: 2025/8/1