最後更新日期 2024 / 01 / 01

圖論入門

什麼是圖

首先
我們要先來了解什麼是圖

簡單來說
圖 (Graph) 就是由多個節點 (Node) 並透過邊 (Edge) 連結成的我們 像是下面的示意圖

建立一張圖

在知道圖是什麼之後
我們要來看的是如何在 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);

拜訪圖上的節點

在很多的情境下
我們會需要拜訪整張圖上面的所有節點來得知一些資訊

這邊會簡單的介紹一下 DFS (深度優先搜尋) 演算法的作法
這個演算法就是利用遞迴的特性遍歷整張圖

這個演算法會儘可能深的搜尋圖的分支
當節點的所有邊都已經被搜尋過
則會回溯到上個節點
這個過程會一直重複到搜尋完整張圖為止

程式碼應該不難理解
直截來看看吧:

vector<int> graph[MAXN]; // 存圖
bool vis[MAXN]; // 紀錄哪些節點拜訪過

void dfs(int v) {
    // 枚舉每一個 v 可以走到的節點
    for (int u : graph[v]) {
        // 如果走過就略過
        if (vis[u]) continue;
        // 標記為走過
        vis[u] = true;
        // 造放進節點 u
        dfs(u);
    }
}

樹狀圖

樹其實就是圖的一種
有一些特性:

  • 不存在環
  • 每個節點均可以走到其他每個節點
  • 若有 n 個節點,邊就是 n1

這邊先補充一下
環就是指像是最上面的示意圖 1 -> 2 -> 3 那部分的結構

然後樹的其他部分都跟圖差不多
不過 DFS 可以寫的比圖簡單

void dfs(int v, int p) {
    // 枚舉每一個 v 可以走到的節點
    for (int u : graph[v]) {
        // 不能走回上個節點
        if (u == p) continue;
        // 造放進節點 u
        dfs(u, v);
    }
}

練習

這裡是一些簡單的練習題:

延伸閱讀

或者你也可以在這邊了解一些更進階的內容:

推薦文章

C++ 常見 STL 教學

pair 是一種可以儲存兩個元素的資料結構通常用來儲存二維座標或者是陣列的 index 與 value 而且常數較小 如果用 array vector 替代有些題目真的會被卡 TLEcpp 宣告一個第一個欄位為 1 第二個欄位為 5 的 pair 在一些 c++ 版本較舊的環境下要使用 makepair1, 5pairint, int pos = {1, 5}; 取得第一個欄位的值cout pos.first endl; 取得第二個欄位的值cout pos.second endl; 將 pos 的第一個欄位的 1 改成 2pos.first = 2; 將 pos 的第二個欄位的 5 改成 4pos.second = 4;在比較兩個 pair 時會先比第一個元素 如果第一個元素相同才會比第二個元素跟傳統陣列差不多 不過長度是可變的 會因為加入更多元素讓 vector 變得更長不用多說了吧 就是可以像陣列一樣儲存 n 個元素cpp 直接宣告 vector 的方式vectorint v1; 宣告長度為 n 的 vectorvectorint v2n; 宣告長度為 n 且每個元素都是 5 的 vectorvectorint v3n, 5; 宣告一個有元素 {1, 2, 3, 4} 的 vectorvectorint v4 = {1, 2, 3, 4} 宣告一個跟其他 vector 一樣的 vector 複製vectorint v5v4; 加入元素在尾端v1.pushback7; 從尾端移除元素v1.popback; 存取 vector 中的某一項cout v42 endl; 取得大小cout v2.size endl;從第一個元素開始比較 如果相同就繼續往後比 直到第一個不同為止像是一個排隊的隊伍 可以從一端進入 從另一端離開 也就是先進去的會先離開大部分情況用來實作一些較複雜的演算法 比如 BFS、拓撲排序等等cpp 宣告一個 queuequeueint q; 將元素 5 推入 queue 後端q.push5; 取得 queue 前端的元素cout q.front endl; 取得 queue 後端的元素cout q.back endl; 將隊伍前端的元素彈出移除q.pop; 檢查 queue 是否為空if q.empty { cout "empty" endl;} 取得 queue 的大小cout q.size endl;類似於一疊盤子 最後放上去的盤子會最先被取走 而你不能從中間拿走盤子 也就是說後進去的會先出去stack 常用來會處理一些匹配類問題 或者是模擬遞迴 更進階一點還有單調堆疊之類的玩法cpp 宣告一個 stackstackint stk; 將元素 3 推入 stackstk.push3; 從 stack 頂端取出元素cout stk.top endl; 將 stack 頂端的元素彈出移除stk.pop; 檢查 stack 是否為空if stk.empty { cout "empty" endl;} 取得 stack 的大小cout stk.size endl;就是集合的意思 用來儲存不重複的元素 並會按照元素的大小自動排序主要用於快速插入和查找元素cpp 宣告一個 setsetint st; 插入元素st.insert5;st.insert3;st.insert7; 檢查 set 是否包含某元素if st.find3 = st.end { cout "set contains 3" endl;} else { cout "set does not contain 3" endl;} 刪除元素st.erase5; 遍歷 set 中的元素for int e : st { cout e " ";} 取得 set 的大小cout st.size endl; 取得 set 的第一項 因為回傳的是 iterator 所以要加 cout st.begin endl; 取得 set 的最後一項 由於 back 是開區間所以要 -1cout --st.end endl;語法根陣列有點像 不過可以接受整數以外的型態來當作索引值有些時候需要使用負數、非常大的數字、字串等等來當索引值 map 就會是一個很方便的工具cpp 宣告一個以 string 為索引,int 為值的 mapmapstring, int mp; 把字串對應到數字mp"one" = 1;mp"two" = 2;mp"three" = 3; 輸出 one 的值cout mp"one" endl; 在 map 中刪除 onemp.erase"one"; 遍歷 mapfor auto key, value : mp { cout key ", " value endl;} 取得 map 的大小cout mp.size endl;又稱為 heap 可以支援快速地插入及查詢最大最小值很常使用在一些複雜的演算法內 比如最短路徑、最小生成樹等等cpp 宣告一個 priority queuepriorityqueueint pq; 宣告一個 priority queue 並且頂部為最小值priorityqueueint, vectorint, greaterint pq; 插入元素pq.push3;pq.push1;pq.push5; 取得頂端的元素最大值cout pq.top endl; 移除頂端的元素pq.pop; 檢查 priority queue 是否為空if pq.empty { cout "empty" endl;} 取得 priority queue 的大小cout pq.size endl;

Algorithms

題解 CSES Restaurant Customers

給你 n 位客人的進入和離開餐廳的時間 輸出最多同時有幾位客人同時在餐廳- n le 2 times 10^5把每個人加入時間和離開的時間分別看成兩個時間點 並把所有時間點加入陣列後一起排序 然後用一個變數來維護目前餐廳人數 每次遇到加入就增加 反之遇到離開就減少 維護中遇到的最大值就是答案了 時間複雜度:Oncpp using namespace std; signed main { int n; cin n; vectorpii v; for int i = 0; i n; i++ { int s, t; cin s t; v.pushback{s, true}; v.pushback{t, false}; } sortv.begin, v.end; int cur = 0; int ans = 0; for auto e : v { if e.ss == true cur++; else cur--; ans = maxcur, ans; } cout ans endl;}

CSES

題解 CSES Sum of Divisors

定義 sigmax 為 x 的所有因數之和 給予一個 n 求 sum^n{k=1}sigmak 之值以 12 為例 先看一下這張圖列出了 1 sim 12 的所有因數可以發現每兩個數字就會出現一次 2 每三次數字就會出現一次 3 觀察後可知 對於一個數字 x 它的出現次數會是 lfloor frac{n}{x} rfloor 因為每 x 個數字就會出現一個 x 的倍數 用這個做法枚舉每個數字計算就可以得到一個 On 的算法 但這樣還不夠快到足以處理這題 10^{12} 的資料量如果我們把剛剛那張圖的呈現方式改一下 上面那一橫排代表因數 1 sim 12 下面那一行排代表該因數出現的次數可以發現這張圖內有幾串連續的因數出現次數相同 因為事實上在計算這個的過程中只會出現最多 2 sqrt n 個相異數字 證明上面那張圖每個紅色圈起來代表一塊 如果我們可以塊為單位來計算就可以把時間複雜度降到 Osqrt{n} 了想像一下 如果 n 除以 x 可以剛好整除的話 令 k = lfloor frac{n}{x} rfloor 則 lfloor frac{n}{k} rfloor 必定等於 k 那如果不是剛好整除的呢? lfloor frac{12}{5} rfloor = 2 ,quadlfloor frac{12}{2} rfloor = 6 再試試看 6 lfloor frac{12}{6} rfloor = 2 ,quadlfloor frac{12}{2} rfloor = 6 觀察後發現 這裡的 6 就是最大的 x 滿足 frac{n}{x} 為 2 於是這樣我們就可以找到最後一個連續出現次數相同的因數 最後只要把每次一塊的第一個數和最後一個數用梯形公式求總和乘上共同的出現次數就可以得到答案了不過這邊要注意的是 因為答案很大所以題目要我們對 10^9 + 7 取模 但梯形公式中又會用到除法 所以我們不能直接除 需要先求出模反元素.modulo-inverse再乘進去才行cppusing namespace std;const int mod = 1e9 + 7;const int inv = 500000004; signed main { int n; cin n; int cur = 1; int ans = 0; while cur = n { int cnt = n cur; int last = n cnt; int sum = last + cur % mod last - cur + 1 % mod % mod inv % mod; ans += sum % mod cnt % mod % mod; cur = last + 1; } cout ans % mod endl;}

CSES