Bài giảng Thuật toán ứng dụng - Chương 6, Phần 2: Graphs - Phạm Quang Dũng

PHAM QUANG DUNG Graphs THUẬT TOÁN ỨNG DỤNG 1 Phạm Quang Dũng Bộ môn KHMT dungpq@soict.hust.edu.vn Nội dung  Đồ thị và các thuật ngữ liên quan  Tìm kiếm theo chiều sâu  Tìm kiếm theo chiều rộng  Chu trình Euler  Thuật toán Dijkstra sử dụng hàng đợi ưu tiên  Thuật toán Kruskal sử dụng disjoint-set structure  Exercises 2 Đồ thị  Đối tượng toán học bao gồm các đỉnh (node) và các liên kết giữa các đỉnh (cạnh, cung)  Đồ thị G = (V,E), trong đó V là tập đỉnh, E là tập cạnh (cung)  (u,v)  E, chúng ta nói u kề với v 3 Undirected graph  V = {1, 2, 3, 4, 5, 6}  E = {(1, 3), (1,6), (2, 4), (2, 5), (2, 6), (3, 4), (3, 6), (4, 5)} 1 6 3 2 4 5 Directed graph  V = {1, 2, 3, 4, 5, 6}  E = {(1, 3), (1,6), (2, 4), (2, 5), (6, 2), (3, 4), (6, 3), (4, 5)} 1 6 3 2 4 5 Đồ thị  Bậc của một đỉnh là số đỉnh kề với nó deg(v) = #{u | (u, v)  E}  Bán bậc vào (bán bậc ra) của một đỉnh là số cung đi vào (đi ra) khỏi đỉnh đó trên đồ thị có hướng: deg-(v) = #{u | (u, v)  E}, deg+(v) = #{u | (v, u) E} 4 Undirected graph  deg(1) = 2, deg(6) = 3 1 6 3 2 4 5 Directed graph  deg-(1) = 0, deg+(1) = 2 1 6 3 2 4 5 Đồ thị  Cho đồ thị G=(V, E) và 2 đỉnh s, t V, một đường đi từ s đến t trên G là chuỗi s = x0, x1, , xk = t trong đó (xi, xi+1)E,  i = 0, 1, , k-1 5 Path from 1 to 5:  1, 3, 4, 5  1, 6, 2, 5 1 6 3 2 4 5 Path from 1 to 5:  1, 3, 4, 5  1, 6, 4, 5 1 6 3 2 4 5 Đồ thị đặc biệt 6 2 1 5 3 4 2 1 5 3 4 6 1 4 3 2 Đồ thị đầy đủ Đồ thị hai phía Đồ thị phẳng Đồ thị 7 1 6 3 2 4 5 0 0 1 0 0 1 0 0 0 1 1 1 1 0 0 1 0 1 0 1 1 0 1 0 0 1 0 1 0 0 1 1 1 0 0 0 1 2 3 4 5 6 1 2 3 4 5 6 1 6 3 2 4 5 0 0 7 0 0 3 0 0 0 9 6 4 7 0 0 8 0 5 0 9 8 0 2 0 0 6 0 4 0 0 3 4 5 0 0 0 1 2 3 4 5 6 1 2 3 4 5 3 4 7 5 8 9 6 2  Ma trận kề  Ma trận trọng số 6 Biểu diễn đồ thị 8  Danh sách kề  Với mỗi v  V, A(v) là tập các bộ (v, u, w) trong đó w là trọng số cung (v, u)  A(1) = {(1, 6, 3), (1, 3, 7)}  A(2) = {(2, 4, 9), (2, 5, 6)}  A(3) = {(3, 4, 8)}  A(4) = {(4, 5, 2)}  A(5) = {}  A(6) = {(6, 3, 5), (6, 2, 4)} 1 6 3 2 4 5 3 4 7 5 8 9 6 2 Duyệt đồ thị  Thăm các đỉnh của đồ thị theo một thứ tự nào đó  Mỗi đỉnh thăm đúng 1 lần  Có 2 phương pháp chính  Duyệt theo chiều sâu: Depth-First Search (DFS)  Duyệt theo chiều rộng: Breadth-First Search (BFS) 9 Depth-First Search (DFS)  DFS(u): DFS bắt đầu thăm từ đỉnh u  Nếu tồn tại một đỉnh v trong danh sách kề của u mà chưa được thăm → tiền hành thăm v và gọi DFS(v)  Nếu tất cả các đỉnh kề với u đã được thăm → DFS quay lui trở lại đỉnh x từ đó thuật toán thăm u và tiến hành thăm các đỉnh khác kề với x (gọi DFS(x)) mà chưa được thăm. Lúc này, đỉnh u được gọi là đã duyệt xong 10 Depth-First Search (DFS)  Các thông tin liên quan đến mỗi đỉnh v  p(v): là đỉnh mà từ đó, DFS thăm đỉnh v  d(v): thời điểm đỉnh v được thăm nhưng chưa duyệt xong  f(v): thời điểm đỉnh v đã duyệt xong  color(v)  WHITE: chưa thăm  GRAY: đã được thăm nhưng chưa duyệt xong  BLACK: đã duyệt xong 11 Depth First Search - DFS DFS(u) { t = t + 1; d(u) = t; color(u) = GRAY; foreach(adjacent node v to u) { if(color(v) = WHITE) { p(v) = u; DFS(v); } } t = t + 1; f(u) = t; color(u) = BLACK; } 12 DFS() { foreach (node u of V) { color(u) = WHITE; p(u) = NIL; } t = 0; foreach(node u of V) { if(color(u) = WHITE) { DFS(u); } } } Depth First Search - DFS 13 Node 1 2 3 4 5 6 7 d f p - - - - - - - color W W W W W W W 1 6 3 2 4 5 7 Depth First Search - DFS 14 Node 1 2 3 4 5 6 7 d 1 f p - - - - - - - color G W W W W W W 1 DFS(1) 1 6 3 2 4 5 7 Depth First Search - DFS 15 Node 1 2 3 4 5 6 7 d 1 2 f p - - 1 - - - - color G W G W W W W DFS(1) 1 3 1 6 3 2 4 5 7 Depth First Search - DFS 16 Node 1 2 3 4 5 6 7 d 1 2 3 f p - - 1 3 - - - color G W G G W W W DFS(1) 1 3 4 1 6 3 2 4 5 7 Depth First Search - DFS 17 Node 1 2 3 4 5 6 7 d 1 2 3 4 f p - - 1 3 4 - - color G W G G G W W DFS(1) 1 3 4 5 1 6 3 2 4 5 7 Depth First Search - DFS 18 Node 1 2 3 4 5 6 7 d 1 2 3 4 f 5 p - - 1 3 4 - - color G W G G B W W DFS(1) 1 3 4 5 1 6 3 2 4 5 7 Depth First Search - DFS 19 Node 1 2 3 4 5 6 7 d 1 2 3 4 6 f 5 p - - 1 3 4 - 4 color G W G G B W G DFS(1) 1 3 4 5 7 1 6 3 2 4 5 7 Depth First Search - DFS 20 Node 1 2 3 4 5 6 7 d 1 2 3 4 6 f 5 7 p - - 1 3 4 - 4 color G W G G B W B DFS(1) 1 3 4 5 7 1 6 3 2 4 5 7 Depth First Search - DFS 21 Node 1 2 3 4 5 6 7 d 1 2 3 4 6 f 8 5 7 p - - 1 3 4 - 4 color G W G B B W B DFS(1) 1 3 4 5 7 1 6 3 2 4 5 7 Depth First Search - DFS 22 Node 1 2 3 4 5 6 7 d 1 2 3 4 6 f 9 8 5 7 p - - 1 3 4 - 4 color G W B B B W B DFS(1) 1 3 4 5 7 1 6 3 2 4 5 7 Depth First Search - DFS 23 Node 1 2 3 4 5 6 7 d 1 2 3 4 10 6 f 9 8 5 7 p - - 1 3 4 1 4 color G W B B B G B DFS(1) 1 6 3 4 5 7 1 6 3 2 4 5 7 Depth First Search - DFS 24 Node 1 2 3 4 5 6 7 d 1 11 2 3 4 10 6 f 9 8 5 7 p - 6 1 3 4 1 4 color G G B B B G B DFS(1) 1 6 3 2 4 5 7 1 6 3 2 4 5 7 Depth First Search - DFS 25 Node 1 2 3 4 5 6 7 d 1 11 2 3 4 10 6 f 12 9 8 5 7 p - 6 1 3 4 1 4 color G B B B B G B DFS(1) 1 6 3 2 4 5 7 1 6 3 2 4 5 7 Depth First Search - DFS 26 Node 1 2 3 4 5 6 7 d 1 11 2 3 4 10 6 f 12 9 8 5 13 7 p - 6 1 3 4 1 4 color G B B B B B B DFS(1) 1 6 3 2 4 5 7 1 6 3 2 4 5 7 Depth First Search - DFS 27 Node 1 2 3 4 5 6 7 d 1 11 2 3 4 10 6 f 14 12 9 8 5 13 7 p - 6 1 3 4 1 4 color B B B B B B B DFS(1) 1 6 3 2 4 5 7 1 6 3 2 4 5 7 Depth First Search - DFS  Kết quả của DFS là tập các cây DFS  Phân loại cạnh  tree edge: (u,v) là cạnh cây nếu v được thăm từ u  back edge: (u,v) là cạnh ngược nếu v là tổ tiên của u  forward edge: (u,v) là cạnh xuôi nếu u là tổ tiên của v  crossing edge: cạnh ngang (các cạnh còn lại) 28 Depth First Search - DFS  Phân loại cạnh  Cạnh cây: (1, 6), (1, 3), (6, 2), (3, 4), (4, 5), (4, 7)  Cạnh ngược:  Cạnh xuôi: (3, 7)  Cạnh ngang: (6, 3), (6, 4), (2, 4), (2,5) 29 1 6 3 2 4 5 7 1 6 3 2 4 5 7 Breadth First Search - BFS  BFS(u): BFS xuất phát từ đỉnh u  Thăm u  Thăm các đỉnh kề với u và chưa được thăm (gọi là đỉnh mức 1)  Thăm các đỉnh kề với đỉnh mức 1 mà chưa được thăm (gọi là đỉnh mức 2)  Thăm các đỉnh kề với đỉnh ở mức 2 mà chưa được thăm (gọi là đỉnh mức 3)  . . .  Cài đặt sử dụng cấu trúc hàng đợi 30 Breadth First Search - BFS 31 BFS(u) { d(u) = 0; Init a queue Q; enqueue(Q,u); color(u) = GRAY; while(Q not empty) { v = dequeue(Q); foreach(x adjacent node to v) { if(color(x) = WHITE){ d(x) = d(v) + 1; color(x) = GRAY; enqueue(Q,x); } } } } BFS() { foreach (node u of V) { color(u) = WHITE; p(u) = NIL; } foreach(node u of V) { if(color(u) = WHITE) { BFS(u); } } } Breadth First Search - BFS 32 1 6 3 2 4 5 7 BFS(1) Breadth First Search - BFS 33 1 BFS(1) 1 6 3 2 4 5 7 Breadth First Search - BFS 34 BFS(1) 1 6 3 1 6 3 2 4 5 7 Breadth First Search - BFS 35 BFS(1) 1 6 3 2 4 7 1 6 3 2 4 5 7 Breadth First Search - BFS 36 BFS(1) 1 6 3 2 4 5 7 1 6 3 2 4 5 7 Ứng dụng DFS, BFS 37  Tính toán thành phần liên thông của đồ thị vô hướng  Tính thành phần liên thông mạnh của đồ thị có hướng  Kiểm tra đồ thị hai phía  Phát hiện chu trình  Sắp xếp topo  Tìm đường đi dài nhất trên cây EXERCISE CONNECTED COMPONENT 38  Given a undirected graph G=(V, E) in which set of nodes V = {1,2,,N}. Compute number of connected components.  Example: following graph has 3 connected components  {1, 2, 7, 8}  {3}  {4, 5, 6} 1 8 2 7 3 6 4 5 EXERCISE CONNECTED COMPONENT 39  Input  Line 1: N and M (1 ≤ N ≤ 106, 1 ≤ M ≤ 107)  Line i+1 (i = 1,,M): ui and vi which are endpoints of the i th edge  Ouput  Number of connected components Stdin stdout 8 8 1 2 1 7 1 8 2 7 4 5 4 6 5 6 7 8 3 EXERCISE CONNECTED COMPONENT 40 #include #include #include #define MAX_N 100001 using namespace std; int N,M; vector A[MAX_N];// A[v] la vector ds cac dinh ke voi v int visited[MAX_N]; int ans; void input(){ cin >> N >> M; for(int i = 1; i <= M; i++){ int u,v; cin >> u >> v; A[u].push_back(v); A[v].push_back(u); } } EXERCISE CONNECTED COMPONENT 41 void init(){ for(int i = 1; i<=N; i++) visited[i] = 0; } void DFS(int u){ for(int j = 0; j < A[u].size(); j++){ int v = A[u][j]; if(!visited[v]){ visited[v] = 1; DFS(v); } } } EXERCISE CONNECTED COMPONENT 42 void solve(){ init(); ans = 0; for(int v = 1; v <= N; v++)if(!visited[v]){ ans++;// chuan bi dem mot thanh phan lien thong tiep theo DFS(v); } cout << ans; } int main(){ input(); solve(); } EXERCISE STRONGLY CONNECTED COMPONENT 43  Given a directed graph G = (V,E) where V = {1,. . ., N} is the set of nodes. Compute the number of strongly connected components of G.  Example, the graph below has 3 strongly connected components  {1,7,8}  {2}  {3,4,5,6} 1 8 2 7 3 6 4 5 EXERCISE STRONGLY CONNECTED COMPONENT 44  Input  Line 1: N and M (1 ≤ N ≤ 106, 1 ≤ M ≤ 107)  Line i+1 (i = 1,,M): ui and vi which are endpoints of the ith arc  Ouput  Number of strongly connected components stdin stdout 8 13 1 2 1 8 2 3 2 6 3 6 4 3 4 6 5 4 6 5 7 1 7 2 7 6 8 7 3 EXERCISE STRONGLY CONNECTED COMPONENT 45 #include #include #include using namespace std; #define MAX_N 100001 int n; vector A[MAX_N]; vector A1[MAX_N];// residual graph // data structure for DFS int f[MAX_N];// finishing time char color[MAX_N]; int t; int icc[MAX_N];// icc[v] index of the strongly connected component containing v int ncc;// number of connected components in the second DFS int x[MAX_N];// sorted-list (inc finishing time) of nodes visited by DFS int idx; EXERCISE STRONGLY CONNECTED COMPONENT 46 void buildResidualGraph(){// xay dung do thi bu for(int u = 1; u <= n; u++){ for(int j = 0; j < A[u].size(); j++){ int v = A[u][j]; A1[v].push_back(u); } } } void init(){ for(int v = 1; v <= n; v++){ color[v] = 'W'; } t = 0; } EXERCISE STRONGLY CONNECTED COMPONENT 47 // DFS on the original graph void dfsA(int s){ t++; color[s] = 'G'; for(int j = 0; j < A[s].size(); j++){ int v = A[s][j]; if(color[v] == 'W'){ dfsA(v); } } t++; f[s] = t; color[s] = 'B'; idx++; x[idx] = s; } EXERCISE STRONGLY CONNECTED COMPONENT 48 void dfsA(){ init(); idx = 0; for(int v = 1; v <= n; v++){ if(color[v] == 'W'){ dfsA(v); } } } EXERCISE STRONGLY CONNECTED COMPONENT 49 // DFS on the residual graph void dfsA1(int s){ t++; color[s] = 'G'; icc[s] = ncc; for(int j = 0; j < A1[s].size(); j++){ int v= A1[s][j]; if(color[v] == 'W'){ dfsA1(v); } } color[s] = 'B'; } EXERCISE STRONGLY CONNECTED COMPONENT 50 void dfsA1(){ init(); ncc = 0; for(int i = n; i >= 1; i--){ int v = x[i]; if(color[v] == 'W'){ ncc++; dfsA1(v); } } } EXERCISE STRONGLY CONNECTED COMPONENT 51 void solve(){ dfsA(); buildResidualGraph(); dfsA1(); cout << ncc; } void input(){ int m; cin >> n >> m; for(int k = 1; k <= m; k++){ int u,v; cin >> u >> v; A[u].push_back(v); } } int main(){ input(); solve(); } EXERCISE STRONGLY CONNECTED COMPONENT 52 void input(){ int m; cin >> n >> m; for(int k = 1; k <= m; k++){ int u,v; cin >> u >> v; A[u].push_back(v); } } int main(){ input(); solve(); } EXERCISE BIPARTIE GRAPH 53  Given undirected graph G = (V, E). Check whether or not G is a bipartie graph. 1 5 6 3 2 4 EXERCISE BIPARTIE GRAPH 54  Input  Line 1: N and M (1 ≤ N ≤ 105, 1 ≤ M ≤ 105)  Line i+1 (i = 1,,M): ui and vi which are endpoints of the i th edge  Ouput  Write 1 if G is bipartie graph, and write 0, otherwise stdin stdout 6 6 1 2 1 3 2 5 2 6 4 5 4 6 1 EXERCISE BIPARTIE GRAPH 55 #include #include #include #include using namespace std; #define MAX_N 100001 int N, M; vector A[MAX_N]; int d[MAX_N];// d[v] is the level of d void input(){ cin >> N >> M; for(int i = 1; i <= M; i++){ int u,v; cin >> u >> v; A[u].push_back(v); A[v].push_back(u); } } EXERCISE BIPARTIE GRAPH 56 int BFS(int u){ queue Q; Q.push(u); d[u] = 0; while(!Q.empty()){ int v = Q.front(); Q.pop(); for(int i = 0; i < A[v].size(); i++){ int x = A[v][i]; if(d[x] > -1){ if(d[v] % 2 == d[x] % 2) return 0; }else{ d[x] = d[v] + 1; Q.push(x); } } } } EXERCISE BIPARTIE GRAPH 57 void solve(){ init(); int ans = 1; for(int v= 1; v <= N; v++) if(d[v]== -1){ if(!BFS(v)){ ans = 0; break; } } cout << ans ; } int main(){ input(); solve(); } EXERCISE LONGEST PATH ON A TREE 58  Given a undirected tree G = (V, E) in which V = {1,,N} is the set of nodes. Each edge (u,v)  E has weight w(u,v). The length of a path is defined to be the sum of weights of edges of this path. Find the longest elementary path on G. 1 6 3 2 4 5 5 2 1 2 3 EXERCISE LONGEST PATH ON A TREE 59  Input  Line 1: N (1 ≤ N ≤ 105)  Line i + 1 (i = 1,,N-1): u, v, w in which w is the weight of edge (u,v) (1 ≤ w ≤ 100)  Output  The weight of the longest path on the given tree stdin stdout 6 1 3 3 1 6 2 2 6 5 4 5 2 4 6 1 10 EXERCISE LONGEST PATH ON A TREE 60 #include #include #include using namespace std; #define MAX_N 100001 int N; vector A[MAX_N];// A[v][i] is the i^th adjacent node to v vector c[MAX_N];// c[v][i] is the weight of the i^th adjacent edge to v int d[MAX_N];// d[v] is the distance from the source node to v in BFS int p[MAX_N];// p[v] is the parent of v in BFS EXERCISE LONGEST PATH ON A TREE 61 void input(){ std::ios::sync_with_stdio(false); cin >> N; for(int i = 1; i <= N-1; i++){ int u,v,w; cin >> u >> v >> w; A[v].push_back(u); A[u].push_back(v); c[v].push_back(w); c[u].push_back(w); } } EXERCISE LONGEST PATH ON A TREE 62 void BFS(int u){ queue Q; d[u] = 0; Q.push(u); while(!Q.empty()){ int v = Q.front(); Q.pop(); for(int i = 0; i < A[v].size(); i++){ int x = A[v][i]; if(d[x] > -1){ if(p[v] != x) cout << "FALSE" << endl;continue;} int w = c[v][i]; Q.push(x); d[x] = d[v] + w; p[x] = v; } } } EXERCISE LONGEST PATH ON A TREE 63 int findMax(){ int max_d = -1; int u = -1; for(int v = 1; v <= N; v++){ if(max_d < d[v]){ max_d = d[v]; u = v; } } return u; } void init(){ for(int v = 1; v <= N; v++){ d[v] = -1; p[v] = -1;} } EXERCISE LONGEST PATH ON A TREE 64 void solve(){ init(); BFS(1); int u = findMax(); init(); BFS(u); u = findMax(); cout << d[u]; } int main(){ input(); solve(); } Eulerian and Hamiltonian cycles  Eulerian cycle: 1, 6, 3, 7, 6, 2, 5, 4, 2, 7, 4, 3, 1  Hamiltonian cycle: 1, 6, 2, 5, 4, 7, 3, 1 65 1 6 3 2 4 57  Given undirected graph G = (V, E)  Eulerian cycle of G is a cycle that passes each edge of G exactly once  Hamiltonian cycle of G is a cycle that visits each node of G exactly once  A graph containing an Eulerian cycle is called Eulerian graph  A graph containing a Hamiltonian cycle is called Hamiltonian graph Algorithm for finding an Eulerian cycle 66 euler(G = (V, A)) { Init stacks S, CE; select v of V; push(S,v); while(S is not empty) { x = top(S); if(A(x) is not empty) { select y  A(x); push(S,y); remove (x,y) from G; }else{ x = pop(S); push(CE,x); } } sequence of nodes in CE forms an euler; } Algorithm for finding a Hamiltonian cycle 67 TRY(k) {// try values for x[k] being aware of // x[1],,x[k-1] for(v  A(x[k-1]) { if(not mark[v]) { x[k] = v; mark[v] = true; if(k == n) { if(v  A(x[1]) { retrieve a Hamiltonian cycle x; } }else{ TRY(k+1); } mark[v] = false; } } }  Use backtracking  Input G = (V, E) in which  V = {1, 2, , n}  A(v) set of adjacent nodes to v  Solution representation: x[1..n], the cycle will be x[1] → x[2] → . . . → x[n] → x[1] Minimum Spanning Tree  Given a undirected graph G = (V, E, w).  Each edge (u, v) E has weight w(u, v)  If (u, v)  E then w(u, v) =   A Spanning tree of G is a undirected connected graph with no cycle, and contains all node of G.  T = (V, F) in which F E  Weight of T: w(T) =σ𝑒∈𝐹𝑤(𝑒)  Find a spanning tree such that the weight is minimal 68 Minimum Spanning Tree - KRUSKAL  Main idea (greedy)  Each step, select the minimum-cost edge and insert it into the spanning tree (under construction) if no cycle is created. 69 KRUSKAL(G = (V,E)){ ET = {}; C = E; while(|ET| 0){ e = select minimum-cost edge of C; C = C \ {e}; if(ET  {e} create no cycle){ ET = ET  {e}; } } if(|ET| = |V|-1) return ET; else return null; } Minimum Spanning Tree - KRUSKAL 70 #include #define MAX 100001 using namespace std; // data structure for input graph int N, M; int u[MAX]; int v[MAX]; int c[MAX]; int ET[MAX]; int nET; // data structure for disjoint-set int r[MAX];// r[v] is the rank of the set v int p[MAX];// p[v] is the parent of v long long rs; Minimum Spanning Tree - KRUSKAL 71 void link(int x, int y){ if(r[x] > r[y]) p[y] = x; else{ p[x] = y; if(r[x] == r[y]) r[y] = r[y] + 1; } } void makeSet(int x){ p[x] = x; r[x] = 0; } int findSet(int x){ if(x != p[x]) p[x] = findSet(p[x]); return p[x]; } Minimum Spanning Tree - KRUSKAL 72 void swap(int& a, int& b){ int tmp = a; a = b; b = tmp; } void swapEdge(int i, int j){ swap(c[i],c[j]); swap(u[i],u[j]); swap(v[i],v[j]); } int partition(int L, int R, int index){ int pivot = c[index]; swapEdge(index,R); int storeIndex = L; for(int i = L; i <= R-1; i++){ if(c[i] < pivot){ swapEdge(storeIndex,i); storeIndex++; } } swapEdge(storeIndex,R); return storeIndex; } Minimum Spanning Tree - KRUSKAL 73 void quickSort(int L, int R){ if(L < R){ int index = (L+R)/2; index = partition(L,R,index); if(L < index) quickSort(L,index-1); if(index < R) quickSort(index+1,R); } } void quickSort(){ quickSort(0,M-1); } Minimum Spanning Tree - KRUSKAL 74 void solve(){ for(int x = 1; x <= N; x++) makeSet(x); quickSort(); rs = 0; int count = 0; nET = 0; for(int i = 0;i < M; i++){ int ru = findSet(u[i]); int rv = findSet(v[i]); if(ru != rv){ link(ru,rv); nET++; ET[nET] = i; rs += c[i]; count++; if(count == N-1) break; } } cout << rs; } Minimum Spanning Tree - KRUSKAL 75 void input(){ cin >> N >> M; for(int i = 0; i < M; i++){ cin >> u[i] >> v[i] >> c[i]; } } int main(){ input(); solve(); } Minimum Spanning Tree - PRIM  Main idea (greedy)  Each step, select a node having minimum distance to the tree under construction for insertion  Data structures  Each v VT  d(v) is the distance from v to VT: d(v) = min{w(v, u) | uVT, (u, v)E}  near(v): the node  VT having w(v, near(v)) = d(v); 76 Minimum Spanning Tree - PRIM PRIM(G = (V,E,w)) { select a random node s of V; for(v  V) { d(v) = w(s,v); near(v) = s; } ET = {}; VT = {s}; while(|VT|  |V|) { v = select a node  V \ VT having minimum d(v); VT = VT{v}; ET = ET  {(v, near(v))}; for(x  V \ VT) { if(d(x) > w(x,v) { d(x) = w(x,v); near(x) = v; } } } return (VT, ET); } 77 Minimum Spanning Tree - PRIM 78 1 2 3 4 5 6 ET Init (0,1) (,1) (7, 1) (, 1) (, 1) (3,1) Step 1 - Step 2 - Step 3 - Step 4 - Step 5 - 1 6 3 2 4 5 3 4 7 5 8 9 6 2 1 • Each cell associated with a node v has label (d(v), near(v)) • Starting node s = 1 Minimum Spanning Tree - PRIM 79 1 2 3 4 5 6 ET Init (0,1) (,1) (7, 1) (, 1) (, 1) (3,1) * (1,6) Step 1 - (4,6) (5,6) (1,6) (,1) - Step 2 - - Step 3 - - Step 4 - - Step 5 - - 1 6 3 2 4 5 3 4 7 5 8 9 6 2 1 Minimum Spanning Tree - PRIM 80 1 2 3 4 5 6 ET Init (0,1) (,1) (7, 1) (, 1) (, 1) (3,1) * (1,6) Step 1 - (4,6) (5,6) (1,6) * (,1) - (1,6), (4,6) Step 2 - (4,6) (5,6) - (2,4) - Step 3 - - - Step 4 - - - Step 5 - - - 1 6 3 2 4 5 3 4 7 5 8 9 6 2 1 Minimum Spanning Tree - PRIM 81 1 2 3 4 5 6 ET Init (0,1) (,1) (7, 1) (, 1) (, 1) (3,1) * (1,6) Step 1 - (4,6) (5,6) (1,6) * (,1) - (1,6),(4,6) Step 2 - (4,6) (5,6) - (2,4) * - (1,6),(4,6),(4,5) Step 3 - (4,6) (5,6) - - - Step 4 - - - - Step 5 - - - - 1 6 3 2 4 5 3 4 7 5 8 9 6 2 1 Minimum Spanning Tree - PRIM 82 1 2 3 4 5 6 ET Init (0,1) (,1) (7, 1) (, 1) (, 1) (3,1) * (1,6) Step 1 - (4,6) (5,6) (1,6) * (,1) - (1,6),(4,6) Step 2 - (4,6) (5,6) - (2,4) * - (1,6),(4,6),(4,5) Step 3 - (4,6) * (5,6) - - - (1,6),(4,6),(4,5),(2,6) Step 4 - - (5,6) - - - Step 5 - - - - - 1 6 3 2 4 5 3 4 7 5 8 9 6 2 1 Minimum Spanning Tree - PRIM 83 1 2 3 4 5 6 ET Init (0,1) (,1) (7, 1) (, 1) (, 1) (3,1) Step 1 - (4,6) (5,6) (1,6) * (,1) - (1,6) Step 2 - (4,6) (5,6) - (2,4) * - (1,6), (4,6) Step 3 - (4,6) * (5,6) - - - (1,6), (4,6), (4,5) Step 4 - - (5,6) * - - - (1,6), (4,6), (4,5), (2,6) Step 5 - - - - - - (1,6), (4,6), (4,5), (2,6), (3,6) 1 6 3 2 4 5 3 4 7 5 8 9 6 2 1 Shortest Path Problem - Dijkstra  Given a weighted graph G = (V, E, w).  Each edge (u, v) E has weight w(u, v) which is non-negative  If (u, v)  E then w(u, v) =   Given a node s of V, find the shortest path from s to other nodes of G 84 Shortest Path Problem - Dijkstra  Main idea Dijkstra:  Each v  V:  P(v) upper bound of the shortest path from s to v  d(v): weight of P(v)  p(v): predecessor of v on P(v)  Initialization  P(v) = s, v, d(v) = w(s,v), p(v) = s  Upper bound improvement  If there exists a node u such that d(v) > d(u) + w(u, v) then update:  d(v) = d(u) + w(u, v)  p(v) = u 85 Shortest Path Problem - Dijkstra 86 Dijkstra(G = (V,E,w)) { for(v  V) { d(v) = w(s,v); p(v) = s; } S = V \ {s}; while(S  {}) { u = select a node  S having minimum d(u); S = S \ {u}; for(v  S) { if(d(v) > d(u) + w(u,v) { d(v) = d(u) + w(u,v); p(v) = u; } } } } Shortest Path Problem - Dijkstra 87 1 2 3 4 5 6 Init (0,1) (,1) (7, 1) (, 1) (, 1) (3,1) Step 1 - Step 2 - Step 3 - Step 4 - Step 5 - 1 6 3 2 4 5 3 4 7 5 8 9 6 2 1 • Each cell associated with v of the table has label (d(v), p(v)) • Starting node s = 1 Shortest Path Problem - Dijkstra 88 1 2 3 4 5 6 Init (0,1) (,1) (7, 1) (, 1) (, 1) (3,1) * Step 1 - (7,6) (7,1) (4,6) (,1) - Step 2 - - Step 3 - - Step 4 - - Step 5 - - 1 6 3 2 4 5 3 4 7 5 8 9 6 2 1 Shortest Path Problem - Dijkstra 89 1 2 3 4 5 6 Init (0,1) (,1) (7, 1) (, 1) (, 1) (3,1) * Step 1 - (7,6) (7,1) (4,6) * (,1) - Step 2 - (7,6) (7,1) - (6, 4) - Step 3 - - - Step 4 - - - Step 5 - - - 1 6 3 2 4 5 3 4 7 5 8 9 6 2 1 Shortest Path Problem - Dijkstra 90 1 2 3 4 5 6 Init (0,1) (,1) (7, 1) (, 1) (, 1) (3,1) * Step 1 - (7,6) (7,1) (4,6) * (,1) - Step 2 - (7,6) (7,1) - (6, 4) * - Step 3 - (7,6) (7,1) - - - Step 4 - - - - Step 5 - - - - 1 6 3 2 4 5 3 4 7 5 8 9 6 2 1 Shortest Path Problem - Dijkstra 91 1 2 3 4 5 6 Init (0,1) (,1) (7, 1) (, 1) (, 1) (3,1) * Step 1 - (7,6) (7,1) (4,6) * (,1) - Step 2 - (7,6) (7,1) - (6, 4) * - Step 3 - (7,6) (7,1) * - - - Step 4 - (7,6) - - - - Step 5 - - - - - 1 6 3 2 4 5 3 4 7 5 8 9 6 2 1 Shortest Path Problem - Dijkstra 92 1 2 3 4 5 6 Init (0,1) (,1) (7, 1) (, 1) (, 1) (3,1) * Step 1 - (7,6) (7,1) (4,6) * (,1) - Step 2 - (7,6) (7,1) - (6, 4) * - Step 3 - (7,6) (7,1) * - - - Step 4 - (7,6) * - - - - Step 5 - - - - - - 1 6 3 2 4 5 3 4 7 5 8 9 6 2 1 Shortest Path Problem - Dijkstra 93  Priority queues  Data structure storing elements and their keys  Efficient operations  (e,k) = deleteMin(): extract element e having minimum key k  insert(v,k): insert element e and its key k into the queue  updateKey(v,k): update the element with new key k  Implementation as binary min-heap  Elements are organized in a complete binary tree  Key of each element is less than or equal to the keys of its children Shortest Path Problem - Dijkstra 94 3,2 1,5 4,8 6,7 7,9 5,10 2,12 8,10 9,11 Mỗi nút của min-heap chứa (v,d(v)) trong đó v là đỉnh của đồ thị và d(v) là cận trên của độ dài đường đi ngắn nhất từ đỉnh xuất phát đến v Shortest Path Problem - Dijkstra 95 3,2 1,5 4,8 6,7 7,9 5,10 2,12 8,10 9,11 9,11 1,5 4,8 6,7 7,9 5,10 2,12 8,10 3,2 swap (3,2) and (9,11) Thao tác deleteMin Shortest Path Problem - Dijkstra 96 9,11 1,5 4,8 6,7 7,9 5,10 2,12 8,10 3,2 1,5 9,11 4,8 6,7 7,9 5,10 2,12 8,10 3,2 1,5 6,7 4,8 9,11 7,9 5,10 2,12 8,10 3,2 1,5 6,7 4,8 8,10 7,9 5,10 2,12 9,11 3,2 Down Heap from (9,11) Cut and return this node Shortest Path Problem - Dijkstra 97 #include #include #define MAX 100001 #define INF 1000000 using namespace std; vector A[MAX]; // A[v][i] is the i^th adjacent node to v vector c[MAX]; // c[v][i] is the weight of the i^th adjacent arc // (v,A[v][i]) to v int n,m; // number of nodes and arcs of the given graph int s,t; // source and destination nodes // priority queue data structure (BINARY HEAP) int d[MAX];// d[v] is the upper bound of the length of the shortest path from s to v (key) int node[MAX];// node[i] the i^th element in the HEAP int idx[MAX];// idx[v] is the index of v in the HEAP (idx[node[i]] = i) int sH;// size of the HEAP bool fixed[MAX]; Shortest Path Problem - Dijkstra 98 void swap(int i, int j){ int tmp = node[i]; node[i] = node[j]; node[j] = tmp; idx[node[i]] = i; idx[node[j]] = j; } void upHeap(int i){ if(i == 0) return; while(i > 0){ int pi = (i-1)/2; if(d[node[i]] < d[node[pi]]){ swap(i,pi); }else{ break; } i = pi; } } Shortest Path Problem - Dijkstra 99 void downHeap(int i){ int L = 2*i+1; int R = 2*i+2; int maxIdx = i; if(L < sH && d[node[L]] < d[node[maxIdx]]) maxIdx = L; if(R < sH && d[node[R]] < d[node[maxIdx]]) maxIdx = R; if(maxIdx != i){ swap(i,maxIdx); downHeap(maxIdx); } } void insert(int v, int k){ // add element key = k, value = v into HEAP d[v] = k; node[sH] = v; idx[node[sH]] = sH; upHeap(sH); sH++; } Shortest Path Problem - Dijkstra 100 int inHeap(int v){ return idx[v] >= 0; } void updateKey(int v, int k){ if(d[v] > k){ d[v] = k; upHeap(idx[v]); }else{ d[v] = k; downHeap(idx[v]); } } Shortest Path Problem - Dijkstra 101 int deleteMin(){ int sel_node = node[0]; swap(0,sH-1); sH--; downHeap(0); return sel_node; } Shortest Path Problem - Dijkstra 102 void input(){ scanf("%d%d",&n,&m); for(int k = 1; k <= m; k++){ int u,v,w; scanf("%d%d%d",&u,&v,&w); A[u].push_back(v); c[u].push_back(w); } scanf("%d%d",&s,&t); } Shortest Path Problem - Dijkstra 103 void init(int s){ sH = 0; for(int v = 1; v <= n; v++){ fixed[v] = false; idx[v] = -1; } d[s] = 0; fixed[s] = true; for(int i = 0; i < A[s].size(); i++){ int v = A[s][i]; insert(v,c[s][i]); } } Shortest Path Problem - Dijkstra 104 void solve(){ init(s); while(sH > 0){ int u = deleteMin(); fixed[u] = true; for(int i = 0; i < A[u].size(); i++){ int v = A[u][i]; if(fixed[v]) continue; if(!inHeap(v)){ int w = d[u] + c[u][i]; insert(v,w); }else{ if(d[v] > d[u] + c[u][i]){ updateKey(v,d[u]+c[u][i]); } } } } int rs = d[t]; if(!fixed[t]) rs = -1; printf("%d",rs); } Shortest Path Problem - Dijkstra 105 int main(){ input(); solve(); } Exercises COUNT SPANNING TREE  Given a undirected connected graph G = (V,E) in which V = {1,,N} is the set of nodes. Count the number of spanning trees of G.  There are 8 spanning trees represented by list of edges as follows  (1,2) (1,3) (1,4)  (1,2) (1,3) (3,4)  (1,2) (1,4) (2,3)  (1,2) (1,4) (3,4)  (1,2) (2,3) (3,4)  (1,3) (1,4) (2,3)  (1,3) (2,3) (3,4)  (1,4) (2,3) (3,4) 106 1 2 4 3 Exercises COUNT SPANNING TREE  Input  Line 1: contains positive integers N and M (1 ≤ N ≤ 20, 1 ≤ M ≤ 25)  Line i+1 (i = 1,,M): contains u and v which are endpoints of the ith edge of G  Output  Write the number of spanning trees of G 107 stdin stdout 4 5 1 2 1 3 1 4 2 3 3 4 8 Exercises COUNT SPANNING TREE 108 #include #define MAX_N 101 #define MAX_M 1000 using namespace std; int N,M; int b[MAX_M]; int e[MAX_M];// (b[i],e[i]) la canh thu i cua do thi int X[MAX_N];// model solution, set of indices of edges of spanning trees long long ans; // data structure for disjoint-set int r[MAX_N];// r[v] is rank of set v int p[MAX_N];// p[v] is parent of v long long rs; Exercises COUNT SPANNING TREE 109 void link(int x, int y){ if(r[x] > r[y]) p[y] = x; else{ p[x] = y; if(r[x] == r[y]) r[y] = r[y] + 1; } } void makeSet(int x){ p[x] = x; r[x] = 0; } int findSet(int x){ if(x != p[x]) p[x] = findSet(p[x]); return p[x]; } Exercises COUNT SPANNING TREE 110 void input(){ cin >> N >> M; for(int i = 1; i<= M; i++){ cin >> b[i] >> e[i]; } } void solution(){ ans++; } Exercises COUNT SPANNING TREE 111 int checkNoCycle(int val, int k){ // check if set edges (b[X[1]],e[X[1]]), (b[X[2]],e[X[2]]), // ..., (b[X[val]],e[X[val]]) induces a cycle for(int i =1; i <= N; i++) makeSet(i); for(int j = 1; j < k; j++){ int u = b[X[j]]; int v = e[X[j]]; int ru = findSet(u); int rv = findSet(v); if(ru == rv) return 0;// node u and v belong to the // same set --> creating a cycle link(ru,rv);// otherwise, link two sets together } if(findSet(b[val]) == findSet(e[val])) return 0; return 1; } Exercises COUNT SPANNING TREE 112 void TRY(int k){ for(int v = X[k-1] + 1; v <= M; v++){ if(checkNoCycle(v,k)){ X[k] = v; if(k == N-1){ solution(); }else{ TRY(k+1); } } } } Exercises COUNT SPANNING TREE 113 void solve(){ ans = 0; X[0] = 0; TRY(1); cout << ans; } int main(){ input(); solve(); } Exercises K-MST  Given a undirected graph G=(V,E), w(e) is the weight of the edge e (e  E). Given a positive integer K, find the subgraph of G which is a tree containing exactly K edges having minimal weight. 114 1 2 4 3 5 4 1 3 5 2 6 5 1 2 4 3 1 3 2 K = 3 Exercises K-MST 115 #include #define MAX_N 101 #define MAX_M 1000 #define INF 10000000 using namespace std; int N,M,K; vector A[MAX_N]; int b[MAX_M]; int e[MAX_M]; int w[MAX_M]; int X[MAX_N];// model solution, set of indices of edges of spanning trees set Ax[MAX_N];// Ax[v] is the set of adjacent nodes to v in the solution int ans; int W; // data structures for DFS int visited[MAX_N]; // data structure for disjoint-set int r[MAX_N];// r[v] is rank of set v int p[MAX_N];// p[v] is parent of v long long rs; Exercises K-MST 116 void DFS(int u){ visited[u] = 1; for(set::iterator it = Ax[u].begin(); it != Ax[u].end(); it++){ int v = *it; if(!visited[v]){ DFS(v); } } } Exercises K-MST 117 int checkConnected(){ set Vx; for(int i = 1; i <= K; i++){ Vx.insert(b[X[i]]); Vx.insert(e[X[i]]); } for(set::iterator it = Vx.begin(); it != Vx.end(); it++){ int u = *it; visited[u] = 0; } int cnt = 0; for(set::iterator it = Vx.begin(); it != Vx.end(); it++){ int u = *it; if(visited[u] == 0){ cnt++; DFS(u); } } return cnt == 1; } Exercises K-MST 118 void swap(int&a, int&b){ int tmp = a; a = b; b = tmp; } void swapEdge(int i, int j){ swap(w[i],w[j]); swap(b[i],b[j]); swap(e[i],e[j]); } int partition(int L, int R, int index){ int pivot = w[index]; swapEdge(index,R); int storeIndex = L; for(int i = L; i <= R-1; i++){ if(w[i] < pivot){ swapEdge(storeIndex,i); storeIndex++; } } swapEdge(storeIndex,R); return storeIndex; } Exercises K-MST 119 void quickSort(int L, int R){ if(L < R){ int index = (L+R)/2; index = partition(L,R,index); if(L < index) quickSort(L,index-1); if(index < R) quickSort(index+1,R); } } void quickSort(){ quickSort(1,M); } Exercises K-MST 120 void input(){ cin >> N >> M >> K; for(int i = 1; i<= M; i++){ int u,v,wuv; cin >> u >> v >> wuv; A[u].push_back(v); A[v].push_back(u); b[i] = u; e[i] = v; w[i] = wuv; } } Exercises K-MST 121 int check(int val, int k){ // check if set edges (b[X[1]],e[X[1]]), (b[X[2]],e[X[2]]), // ..., (b[X[val]],e[X[val]]) // induces a cycle for(int i =1; i <= N; i++) makeSet(i); for(int j = 1; j < k; j++){ int u = b[X[j]]; int v = e[X[j]]; int ru = findSet(u); int rv = findSet(v); if(ru == rv) return 0; link(ru,rv); } if(findSet(b[val]) == findSet(e[val])) return 0; return 1; } Exercises K-MST 122 void solution(){ if(checkConnected()) if(W < ans) ans = W; } Exercises K-MST 123 void TRY(int k){ for(int v = X[k-1] + 1; v <= M - K + k; v++){ if(check(v,k)){ X[k] = v; W += w[v]; Ax[b[v]].insert(e[v]); Ax[e[v]].insert(b[v]); if(k == K){ solution(); }else{ int g = W; for(int j = 1; j <= K-k; j++) g += w[X[k] + j]; if(g < ans) TRY(k+1); } Ax[b[v]].erase(e[v]); Ax[e[v]].erase(b[v]); W -= w[v]; } } } Exercises K-MST 124 void solve(){ quickSort(); ans = INF; X[0] = 0; W = 0; TRY(1); cout << ans; } int main(){ input(); solve(); } Exercises BOUNDED-MST  The diameter of a tree is defined to be the length of the longest path (in term of number of edges of the path) on that tree. Given a undirected graph G=(V,E), w(e) is the weight of the edge e (e  E). Given a positive integer K, find the minimum spanning tree T of G such that the diameter of T is less than or equal to K. 125 1 2 4 3 5 4 1 3 5 7 1 5 6 2 5 1 2 4 3 5 3 5 1 6 2 5 K = 3 Exercises BOUNDED-MST 126 #include #define MAX_N 101 #define MAX_M 1000 #define INF 10000000 using namespace std; int N,M,K; //vector A[MAX_N]; int b[MAX_M]; int e[MAX_M]; int c[MAX_M];// c[i] is the weight of edge (b[i],e[i]) int X[MAX_N];// model solution, set of indices of edges of spanning trees int W; int ans; // data structure for disjoint-set int r[MAX_N];// r[v] is rank of set v int p[MAX_N];// p[v] is parent of v long long rs; Exercises BOUNDED-MST 127 void link(int x, int y){ if(r[x] > r[y]) p[y] = x; else{ p[x] = y; if(r[x] == r[y]) r[y] = r[y] + 1; } } void makeSet(int x){ p[x] = x; r[x] = 0; } int findSet(int x){ if(x != p[x]) p[x] = findSet(p[x]); return p[x]; } Exercises BOUNDED-MST 128 void input(){ cin >> N >> M >> K; for(int i = 1; i<= M; i++){ int u,v,w; cin >> u >> v >> w; b[i] = u; e[i] = v; c[i] = w; } } Exercises BOUNDED-MST 129 int check(int val, int k){ // check if set edges (b[X[1]],e[X[1]]), (b[X[2]],e[X[2]]), ..., // (b[X[val]],e[X[val]]) // induces a cycle for(int i =1; i <= N; i++) makeSet(i); for(int j = 1; j < k; j++){ int u = b[X[j]]; int v = e[X[j]]; int ru = findSet(u); int rv = findSet(v); if(ru == rv) return 0; link(ru,rv); } if(findSet(b[val]) == findSet(e[val])) return 0; return 1; } Exercises BOUNDED-MST 130 int selectMax(int d[],int N){ int max_d = -1; int u = -1; for(int v = 1; v <= N; v++){ if(max_d < d[v]){ max_d = d[v]; u = v;} } return u; } Exercises BOUNDED-MST 131 int diameter(){ vector A[MAX_N]; for(int i= 1; i <= N-1; i++){ int u = b[X[i]]; int v = e[X[i]]; A[u].push_back(v); A[v].push_back(u); } queue Q; int d[MAX_N] = {-1}; for(int v = 1; v <= N; v++) d[v] = -1; int s = 1; d[s] = 0; Q.push(s); while(!Q.empty()){ int u = Q.front(); Q.pop(); for(int i = 0; i < A[u].size(); i++){ int v = A[u][i]; if(d[v] < 0){ d[v] = d[u] + 1; Q.push(v); } } } Exercises BOUNDED-MST 132 int x = selectMax(d,N); for(int v = 1; v <= N; v++) d[v] = -1; while(!Q.empty()) Q.pop(); d[x] = 0; Q.push(x); while(!Q.empty()){ int u = Q.front(); Q.pop(); for(int i = 0; i < A[u].size(); i++){ int v = A[u][i]; if(d[v] < 0){ d[v] = d[u] + 1; Q.push(v); } } } int y = selectMax(d,N); return d[y]; } Exercises BOUNDED-MST 133 void solution(){ int dia = diameter(); if(dia <= K){ if(W < ans){ ans = W; } } } Exercises BOUNDED-MST 134 void TRY(int k){ for(int v = X[k-1] + 1; v <= M; v++){ int ok = check(v,k); if(ok){ X[k] = v; W += c[v]; if(k == N-1){ solution(); }else{ TRY(k+1); } W -= c[v]; } } } Exercises BOUNDED-MST 135 void solve(){ ans = INF; X[0] = 0; TRY(1); cout << ans; } int main(){ input(); solve(); } Exercises MaxClique  Cho đồ thị vô hướng G=(V,E). Một đồ thị G’=(V’, E’) được gọi là đồ thị con của G nếu V’ là tập con của V và E’ là tập con của E. Hãy tìm đồ thị con của G là đồ thị đầy đủ và có số đỉnh lớn nhất 136 Exercises MaxClique 137 #include #define MAX 1000 using namespace std; int N,M; set A[MAX]; // Adj[v] la list cac dinh ke voi v int X[MAX]; int best;// kich thuoc be lon nhat int X_best[MAX];// luu tap dinh cua be cuc dai Exercises MaxClique 138 void input(){ cin >> N >> M; for(int i = 0; i < M; i++){ int u,v; cin >> u >> v; A[u].insert(v); A[v].insert(u); } } Exercises MaxClique 139 bool check(int v, int k){ for(int i = 1; i <= k-2; i++){ if(A[X[i]].find(v) == A[X[i]].end()){ return false; } } return true; } Exercises MaxClique 140 void TRY(int k){// thu gia tri cho X[k] // da biet X[1,. . ., k-1] for(set::iterator it = A[X[k-1]].begin(); it != A[X[k-1]].end(); it++){ int v = *it; if(check(v,k)){ X[k] = v; if(k > best){ best = k; for(int i = 1; i <= k; i++) X_best[i] = X[i]; //printf("Best = %d\n",best); } if(k < N){ TRY(k+1); } } } } Exercises MaxClique 141 void solve(){ best = 1; for(int v = 1; v <= N; v++){ X[1] = v; TRY(2); } cout << best; //printf("maxclique: "); //for(int i = 1; i <= best; i++) printf("%d ",X_best[i]); printf("\n"); } int main(){ input(); solve(); }