沈奕呈、陳睿倬Apr 15,2022
DSA
Data Structure and Algorithm
資料結構
演算法
Data Structure
Algorithm
tcirc39th
社課
臺中一中電研社
社網:tcirc.tw
online judge:judge.tcirc.tw
IG:TCIRC_39th
社課點名表單:google 表單
圖(graph),是一種用來表示關聯、關係的概念,由數個點(vertex)與數個邊(edge)組成,邊可以用來連接任兩點,表示兩點之間有關係
個別的資料點,若沒有邊,每個點都是獨立的(與其他點沒有關係)
ex.車站、人
用來連通兩個點,表示點與點的關係,分成有向邊和無向邊
有向邊:代表兩個點之間具有單向關係,只有一個方向有通(可以從A點走到B點,但不能從B點走到A點)
無向邊:代表兩個點之間具有雙向關係,雙向互通
ex.鐵路、朋友關係
有些情況下,點與點的關係與數值有關,這時可以幫邊加上權重
沒有學會如何儲存圖,就沒辦法做圖的題目,所以先來看看圖的儲存方式吧
圖的實用儲存方式有以下2種
Adjacency matrix
Adjacency list
中文叫「相鄰矩陣」,當點的數量為N,用一個N*N的二維陣列儲存,適合用於邊比點多很多的情況
#include <bits/stdc++.h> using namespace std; const int max_n=1e2; const int max_m=3e4; int n,m,s; int graph[max_n][max_n];//紀錄n個點的圖 int main() { cin>>n>>m>>s; for(int i=0;i<m;i+=1){//注意是要輸入m條邊,所以放m int a,b;//起點、終點 cin>>a>>b; graph[a][b]+=1;//無向圖時須寫下一行 //graph[b][a]+=1; } for(int i=0; i<n;i+=1){ for(int j=0;j<n;j+=1) cout<<graph[i][j]<<' '; cout<<'\n'; } return 0; }
/*INTPUT---
7 6
1
5 1
1 3
1 4
2 3
4 6
6 0
------------*/
可以看到,當點多而邊少(相對),Adjacency matrix浪費了不少空間
但是當邊的數量接近或超過N*N,或是重複的邊常常出現的話,Adjacency matrix可以將重復的那一格加1,就能節省不少空間
/*OUTPUT---
0 0 0 0 0 0 0
0 0 0 1 1 0 0
0 0 0 1 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 1
0 1 0 0 0 0 0
1 0 0 0 0 0 0
------------*/
中文叫「相鄰列表」,當點的數量為N,儲存方式為,宣告一個長度為N的一維陣列,陣列資料型態使用vector或list ,適合用於點多,而邊不多的情況
#include <bits/stdc++.h> using namespace std; const int max_n=1e2; const int max_m=3e4; int n,m,s; vector<int> graph[max_n]; int main() { ios::sync_with_stdio(0); cin.tie(0); cin>>n>>m>>s; for(int i=0;i<m;i+=1){//注意是要輸入m條邊,所以放m int a,b;//起點、終點 cin>>a>>b; graph[a].push_back(b);//無向圖時須寫下一行 //graph[b].push_back(a); } for(int i=0; i<n;i+=1){ cout<<i<<':'; for(int j=0;j<graph[i].size();j+=1) cout<<graph[i][j]<<' '; cout<<'\n'; } return 0; }
/*INTPUT---
7 6
1
5 1
1 3
1 4
2 3
4 6
6 0
---------*/
可以看到,當點多而邊少(相對),Adjacency list節省了不少空間
但是當邊的數量接近或超過N*N,或是重複的邊常常出現的話,Adjacency list就會浪費不少空間
/*OUTPUT---
0:
1:3 4
2:3
3:
4:6
5:1
6:0
------------*/
樹的定義較為嚴格,樹的每個點須與其他點連通,且不能形成環,圖則無此規定
全名為最小權重生成樹,也就是把一個無向圖中取出一顆樹,且樹包含所有點。
下面將簡單介紹如何求出最小生成樹。
這裡有個新的概念,叫DSU演算法,又稱併查集。可用於分類的問題。由兩個功能組成,查詢和合併。
套用到圖論,我們可以將起始的每個節點視為獨立的樹,而我們的目標就是將這些樹結合為最小生成樹。
在DSU裡,我們會開一個陣列root紀錄每個節點屬於哪顆樹,若兩個節點在同個樹裡,則它們的根節點相同,所以會有同一個root。
查詢的部分,就是查詢每個節點的root。
至於將兩棵樹合併成同一棵樹時,只需要將兩棵樹的root變成同一個就好。但是要先檢查它們的root是否不同,否則最後會求出一個環。
#include <bits/stdc++.h> using namespace std; int N, S; int root[100]; struct side{ int a = a, b = b; int s = s; }; side Side[100]; bool cmp(side a, side b){ return a.s < b.s; } int FindRoot(int x){ // 查詢樹的root if (root[x] == x)return x; else return root[x] = FindRoot(root[x]); } int DSA(int a, int b){ int ra = FindRoot(a); int rb = FindRoot(b); if (ra == rb)return false; root[rb] = ra; // 兩棵不同的樹合併 return true; } int main() { cin >> N >> S; for(int i=0;i<N;i++) root[i] = i; for (int i = 0;i<S;i++){ cin >> Side[i].a >> Side[i].b >> Side[i].s; } sort(Side, Side+S, cmp); // 先將邊由小到大排好 for (int i=0;i<S;i++){ // cout << Side[i].s << ' '; int a = Side[i].a, b = Side[i].b; cout << a << ' ' << b << ' ' << Side[i].s << endl; if (DSA(a, b)){ cout << "combine successfully\n"; }else{ cout << "combine fail\n"; } } return 0; }
https://ideone.com/LBgxEo
輸出太長,這裡就先不放
選擇任一樹根作為樹根(起點)。接著,尋找尚未加入樹的點中,離樹根最近的點加入樹。重複此步驟直到所有點加進樹裡。
來源
#include <bits/stdc++.h> using namespace std; #define ppii pair<pair<int, int>, int> int N, S; int n[10]; int G[11][11]; struct cmp{ bool operator()(ppii a, ppii b){ return a.second > b.second; // 由於pq會將cmp 視為 !cmp, // 所以我們倒著寫 } }; int main() { char ch[10]; // 數字轉換成字母 for (int i=0;i<10;i++){ ch[i] = 'a'+i; } cin >> N >> S; memset(G, -1, sizeof(G)); for (int i=0;i<S;i++){ int a, b, s; cin >> a >> b >> s; G[a][b] = s; // a to b, w = s G[b][a] = s; // b to a, w = s } int cnt = 0; // 若所有點都加進樹 --> cnt == N int v[10] = {0};// 紀錄是否以加進樹裡 // init 先將a (0) 加入 priority_queue<ppii , vector<ppii>, cmp> pq; // 紀錄和樹連結的點 cnt+=1; v[0] = 1; for (int i=0;i<N;i++){ if (G[0][i] != -1) pq.push({{0, i}, G[0][i]}); } while (cnt < N){ // all nodes are in tree , then stop int a = pq.top().first.first; int b = pq.top().first.second; int s = pq.top().second; pq.pop(); if (v[b] == 1)continue; // already in tree, pass // else add it into the tree v[b] = 1;cnt++; //cout << a << ' ' << b << ' ' << s << endl; cout << ch[a] << ' ' << ch[b] << ' ' << s << endl; cout << "combine successfully\n"; for (int i=0;i<N;i++){ // 新增和樹連結的邊 if (G[b][i] != -1) pq.push({{b, i}, G[b][i]}); } } return 0; }
output
https://ideone.com/dQel5R
圖的便利方式有兩種
BFS:廣度優先搜尋
DFS:深度優先搜尋
又稱廣度優先搜尋,是一種遍歷整個圖的演算法。一開始先選擇一個點最為起始點,並往周圍連結的點散開。持續上述步驟直到所有的點都被讀取過。
連結
圖論和樹的廣度優先搜尋一樣,我們可以拿queue實作。先挑選一個點,把他加進queue裡,接著讀取queue第一個元素,將和它連結的點加進queue。
所以整個流程就是:
讀取 –>pop –>加進周圍的點 –>讀取
直到沒有元素在queue裡時,我們可以停止了,因為已經拜訪過每個和出發點有連通的點了。
要注意的是,不要將已被拜訪過的元素加進queue裡,否則程式不會停止(因為會永遠讀不完)。所以可以開個陣列紀錄是否已走訪過該元素。
為了實際了解bfs的應用,我們參考下面的例題。
套用到圖論也是相同概念
來源
這題是非常典型的bfs應用,雖然不明顯看出他是一個圖。不過可以把每個水管看成是一個點,所以此圖變成一個有向圖(方向由上而下,往右或往左),兩相鄰的點形成一邊。
0 0 1 0 0
0 0 1 1 0
0 1 1 1 1
1 1 0 0 0
由於題目已經指定由上面倒水,所以我們將第一排的點都設為1。接著將第一排的水管都加進queue裡。
後面就簡單了,重複執行上述我們所說的步驟。
至於往上的水管,就只是要多拜訪一個元素。
#include <bits/stdc++.h> using namespace std; int const MaxN = 101; int N, M; int S; int G[101][101]; int a[101][101]; bool Inrange(int r, int c){ if (r >= 0 and r < N and c >= 0 and c < M)return true; else return false; } void bfs1(){ int dc[3] = {1, -1, 0}; int dr[3] = {0,0, 1}; deque<pair<int, int>> dq; // 設定空queue for (int i=0;i<M;i++){ // 初始化第一排的水管 if (G[0][i] == 0)cout << 0 << ' '; else{ cout << 1 << ' '; a[0][i] = 1; dq.push_back({0, i}); // 將水管加進dq } }cout << endl; //cout << "=================\n"; while (dq.empty() == 0){ //cout << dq.size() << endl; int r = dq.front().first; // 讀取dq節點 int c = dq.front().second; //cout << r << ' ' << c << endl; dq.pop_front(); for (int k=0;k<3;k++){ // 拜訪周圍的點 int nxt_r = r + dr[k]; int nxt_c = c + dc[k]; if (Inrange(nxt_r, nxt_c) and G[nxt_r][nxt_c] == 1 and a[nxt_r][nxt_c] == 0){ // 若該點為水管,則時間就是上個節點+1 a[nxt_r][nxt_c] = a[r][c] + 1; dq.push_back({nxt_r, nxt_c}); // 記得加進queue }else{ continue; // 若不是水管,代表無節點,跳過 } } } for (int i=1;i<N;i++){// 輸出answer for (int j=0;j<M;j++){ if (a[i][j] == 0)cout << '0' << ' '; else cout << a[i][j] << ' '; }cout << endl; } } void bfs2(){ int dc[4] = {1, -1, 0, 0}; int dr[4] = {0, 0, -1, 1}; deque<pair<int, int>> dq; for (int i=0;i<M;i++){ if (G[0][i] == 0)cout << 0 << ' '; else{ cout << 1 << ' '; a[0][i] = 1; dq.push_back({0, i}); } }cout << endl; //cout << "=================\n"; while (dq.empty() == 0){ //cout << dq.size() << endl; int r = dq.front().first; int c = dq.front().second; //cout << r << ' ' << c << endl; dq.pop_front(); for (int k=0;k<4;k++){ int nxt_r = r + dr[k]; int nxt_c = c + dc[k]; if (Inrange(nxt_r, nxt_c) and G[nxt_r][nxt_c] == 1 and a[nxt_r][nxt_c] == 0){ a[nxt_r][nxt_c] = a[r][c] + 1; dq.push_back({nxt_r, nxt_c}); }else{ continue; } } } for (int i=1;i<N;i++){ for (int j=0;j<M;j++){ if (a[i][j] == 0)cout << '0' << ' '; else cout << a[i][j] << ' '; }cout << endl; } } int main() { ios::sync_with_stdio(0); cin.tie(0); int t = 1; while (cin >> S){ cin >> N >> M; memset(a, 0, sizeof(a)); for (int i=0;i<N;i++){ for (int j=0;j<M;j++) cin >> G[i][j]; } cout << "Case " << t++ <<":" << endl; if (S == 1) bfs2(); else bfs1(); } return 0; }
又稱深度優先搜尋
圖源
造訪順序
1.由root當起點,選擇一個child拜訪,再由這個node(節點)繼續選擇一個child拜訪,不斷重複直到遇到leaf(沒有子節點)
2.從現在這一層sbiling(同層的其他節點)中選一個當起點,執行步驟1,不斷重複直到該層的sbiling都已經拜訪過
3.處理往上一層的其他sbiling,執行步驟2,不斷重複直到回到root那一層
可以發現我們在過程中都是先處理剛加入的節點,所以適合用stack–先進先出的概念來實做
作法:
有n個點,n-1個邊,任兩點間一定會有單一路徑連通(代表這是一棵樹),請求出與起點相關性大於等於q的景點數量(不包含起點本身)
兩景點間的相關性為沿路的邊中,權重最小的,所以如果在行經的路線中遇到權重小於題目要求的,就不用再走下去了(因為之後遇到的景點關連性都會小於q)
換句話說,當邊的權重<q,那條邊就可以直接不要連了,反正通過那條路後的所有景點都不符合題目要求,所以我們不須額外紀錄邊的權重,只需要遍歷與起點連通的所有點,並記錄這些點的數量就可以了。
注意!:需要另外開一個一維陣列紀錄每個點有沒有被走訪過,有被走訪過的點不能再走(不然你的遍歷永遠不會結束)
我們這次試試看用dfs的方式遍歷吧(要用 bfs 或是 dsu 也可以)
邊和點差不多,且不用紀錄權重,可以用adjacency list,不過點的數量不算太多,要用adjacency matrix也行
#include <bits/stdc++.h> using namespace std; const int max_n=5e3; const int max_e=5e3-1; const int max_q=1e9; int n,v,q; vector<int> to[max_n+1];//點從1開始 vector<int> stk; bool flag[max_n+1];//紀錄點有沒有拜訪過 int main() { cin>>n>>v>>q;//點的數量,起點,相關性 n-=1;//邊的數量 while(n-->0){ int i,j,r; cin>>i>>j>>r;//兩點,權重 if(r<q) continue; to[i].push_back(j); to[j].push_back(i);//無向圖 } int ans=0; stk.push_back(v);//起點放入stack while(stk.empty()==0){//當stack不是空的 int now=stk.back(); stk.pop_back(); flag[now]=1;//紀錄已經拜訪過此點 //等同於 int nxt=to[now].begin;nxt!=to[now].end();nxt++ for(int nxt : to[now]){ if(flag[nxt]) continue;//此點已拜訪過 stk.push_back(nxt); ans+=1; } } cout<<ans<<'\n'; return 0; }