goupee.vn goupee.com THUẬT TOÁN ỨNG DỤNG Tarjan DFS algorithm for finding Bridges and Articulation Points cuu duong than cong . com Phạm Quang Dũng Bộ môn KHMT dungpq@soict.hust.edu.vn 1 fb.com/goupee.vn CuuDuongThanCong.com https://fb.com/tailieudientucntt
goupee.vn goupee.com Duyệt theo chiều sâu Cây DFS DFS xuất phát từ một đỉnh cho phép thăm các đỉnh con cháu của nó trên cây DFS Cấu trúc dữ liệu duy trì num[v]: thời điểm đỉnh v được thăm low[v]: giá trị num nhỏ nhất của các đỉnh x sao cho có cạnh ngược (u,x) với u là 1 đỉnh con cháu nào đó của v cuu duong than cong . com 2 fb.com/goupee.vn CuuDuongThanCong.com https://fb.com/tailieudientucntt
goupee.vn goupee.com DFS(6) 6 1 4 3 2 8 5 cuu duong than cong . com 9 7 3 fb.com/goupee.vn CuuDuongThanCong.com https://fb.com/tailieudientucntt
goupee.vn goupee.com DFS(6) 6 num[6] = 1, low[6] = 1 cuu duong than cong . com 4 fb.com/goupee.vn CuuDuongThanCong.com https://fb.com/tailieudientucntt
goupee.vn goupee.com DFS(6) 6 num[6] = 1, low[6] = 1 num[1] = 2, low[[1] = 2 1 cuu duong than cong . com 5 fb.com/goupee.vn CuuDuongThanCong.com https://fb.com/tailieudientucntt
goupee.vn goupee.com DFS(6) 6 num[6] = 1, low[6] = 1 num[1] = 2, low[[1] = 2 1 num[3] = 3, low[3] = 3 3 cuu duong than cong . com 6 fb.com/goupee.vn CuuDuongThanCong.com https://fb.com/tailieudientucntt
goupee.vn goupee.com DFS(6) 6 num[6] = 1, low[6] = 1 num[1] = 2, low[[1] = 2 1 num[3] = 3, low[3] = 3 num[2] = 4, low[2] = 4 3 2 cuu duong than cong . com 7 fb.com/goupee.vn CuuDuongThanCong.com https://fb.com/tailieudientucntt
goupee.vn goupee.com DFS(6) 6 num[6] = 1, low[6] = 1 num[1] = 2, low[[1] = 2 1 num[3] = 3, low[3] = 3 num[2] = 4, low[2] = 4 num[8] = 5, low[8] = 5 3 2 8 cuu duong than cong . com 8 fb.com/goupee.vn CuuDuongThanCong.com https://fb.com/tailieudientucntt
goupee.vn goupee.com DFS(6) 6 num[6] = 1, low[6] = 1 num[1] = 2, low[[1] = 2 1 num[3] = 3, low[3] = 3 num[2] = 4, low[2] = 4 num[8] = 5, low[8] = 5 3 num[5] = 6, low[5] = 6 2 8 5 cuu duong than cong . com 9 fb.com/goupee.vn CuuDuongThanCong.com https://fb.com/tailieudientucntt
goupee.vn goupee.com DFS(6) 6 num[6] = 1, low[6] = 1 num[1] = 2, low[[1] = 2 1 num[3] = 3, low[3] = 3 num[2] = 4, low[2] = 4 num[8] = 5, low[8] = 5 3 num[5] = 6, low[5] = 6 num[9] = 7, low[9] = 7 2 8 5 cuu duong than cong . com 9 10 fb.com/goupee.vn CuuDuongThanCong.com https://fb.com/tailieudientucntt
goupee.vn goupee.com DFS(6) 6 num[6] = 1, low[6] = 1 num[1] = 2, low[[1] = 2 1 num[3] = 3, low[3] = 3 num[2] = 4, low[2] = 4 num[8] = 5, low[8] = 5 3 num[5] = 6, low[5] = 6 num[9] = 7, low[9] = num[2] = 4 2 8 5 cuu duong than cong . com 9 11 fb.com/goupee.vn CuuDuongThanCong.com https://fb.com/tailieudientucntt
goupee.vn goupee.com DFS(6) 6 num[6] = 1, low[6] = 1 num[1] = 2, low[[1] = 2 1 num[3] = 3, low[3] = 3 num[2] = 4, low[2] = 4 num[8] = 5, low[8] = 5 3 num[5] = 6, low[5] = 6 num[9] = 7, low[9] = num[2] = 4 2 num[7] = 8, low[7] = 8 8 5 cuu duong than cong . com 9 7 12 fb.com/goupee.vn CuuDuongThanCong.com https://fb.com/tailieudientucntt
goupee.vn goupee.com DFS(6) 6 num[6] = 1, low[6] = 1 num[1] = 2, low[[1] = 2 1 num[3] = 3, low[3] = 3 num[2] = 4, low[2] = 4 num[8] = 5, low[8] = 5 3 num[5] = 6, low[5] = 6 num[9] = 7, low[9] = num[2] = 4 2 num[7] = 8, low[7] = num[8] = 5 8 5 cuu duong than cong . com 9 7 13 fb.com/goupee.vn CuuDuongThanCong.com https://fb.com/tailieudientucntt
goupee.vn goupee.com DFS(6) 6 num[6] = 1, low[6] = 1 num[1] = 2, low[[1] = 2 1 num[3] = 3, low[3] = 3 num[2] = 4, low[2] = 4 num[8] = 5, low[8] = 5 3 num[5] = 6, low[5] = low[9] = 4 num[9] = 7, low[9] = num[2] = 4 2 num[7] = 8, low[7] = num[8] = 5 8 5 cuu duong than cong . com 9 7 14 fb.com/goupee.vn CuuDuongThanCong.com https://fb.com/tailieudientucntt
goupee.vn goupee.com DFS(6) 6 num[6] = 1, low[6] = 1 num[1] = 2, low[[1] = 2 1 num[3] = 3, low[3] = 3 num[2] = 4, low[2] = 4 num[8] = 5, low[8] = low[5] = 4 3 num[5] = 6, low[5] = low[9] = 4 num[9] = 7, low[9] = num[2] = 4 2 num[7] = 8, low[7] = num[8] = 5 8 5 cuu duong than cong . com 9 7 15 fb.com/goupee.vn CuuDuongThanCong.com https://fb.com/tailieudientucntt
goupee.vn goupee.com DFS(6) 6 num[6] = 1, low[6] = 1 num[1] = 2, low[[1] = 2 1 num[3] = 3, low[3] = num[6] = 1 num[2] = 4, low[2] = 4 num[8] = 5, low[8] = low[5] = 4 3 num[5] = 6, low[5] = low[9] = 4 num[9] = 7, low[9] = num[2] = 4 2 num[7] = 8, low[7] = num[8] = 5 8 5 cuu duong than cong . com 9 7 16 fb.com/goupee.vn CuuDuongThanCong.com https://fb.com/tailieudientucntt
goupee.vn goupee.com DFS(6) 6 num[6] = 1, low[6] = 1 num[1] = 2, low[[1] = low[3] = 1 1 num[3] = 3, low[3] = num[6] = 1 num[2] = 4, low[2] = 4 num[8] = 5, low[8] = low[5] = 4 3 num[5] = 6, low[5] = low[9] = 4 num[9] = 7, low[9] = num[2] = 4 2 num[7] = 8, low[7] = num[8] = 5 8 5 cuu duong than cong . com 9 7 17 fb.com/goupee.vn CuuDuongThanCong.com https://fb.com/tailieudientucntt
goupee.vn goupee.com DFS(6) 6 num[6] = 1, low[6] = 1 num[1] = 2, low[[1] = low[3] = 1 1 num[3] = 3, low[3] = num[6] = 1 4 num[2] = 4, low[2] = 4 num[8] = 5, low[8] = low[5] = 4 3 num[5] = 6, low[5] = low[9] = 4 num[9] = 7, low[9] = num[2] = 4 2 num[7] = 8, low[7] = num[8] = 5 num[4] = 9, low[4] = 9 8 5 cuu duong than cong . com 9 7 18 fb.com/goupee.vn CuuDuongThanCong.com https://fb.com/tailieudientucntt
goupee.vn goupee.com Sample code #include <bits/stdc++.h> using namespace std; const int N = 10000; int n,m; vector<int> A[N]; bool visited[N]; int num[N]; int low[N]; int t; vector<pair<int,int> > bridges; void input(){ ios_base::sync_with_stdio(0); cin.tie(0); cin >> n >> m; for(int i = 1; i <= m; i++){ int u,v; cin >> u >> v;cuu duong than cong . com A[u].push_back(v); A[v].push_back(u); } } 19 fb.com/goupee.vn CuuDuongThanCong.com https://fb.com/tailieudientucntt
goupee.vn goupee.com Sample code void dfs(int s, int ps){ // DFS from s with ps is the parent of s in the DFS tree t++; num[s] = t; low[s] = num[s]; visited[s] = true; for(int i = 0;i < A[s].size(); i++){ int v = A[s][i]; if(v == ps) continue; if(visited[v]){ low[s] = min(low[s],num[v]); }else{ dfs(v,s); low[s] = min(low[s],low[v]); if(low[v] > num[s]){ // discover a bridge (s,v)cuu duong than cong . com bridges.push_back(make_pair(s,v)); } } } } 20 fb.com/goupee.vn CuuDuongThanCong.com https://fb.com/tailieudientucntt
显示前 20 页。下载资料查看完整内容。
暂无评论。快来抢沙发吧！
评论 (0)
暂无评论。快来抢沙发吧！