Algorithms-K58-PM: Đồ thị

2 bình luận cho Algorithms-K58-PM: Đồ thị

• 

  10/11/2020 - 15:15

  admin  says:

  #include <iostream> #include <queue> using namespace std; const int MAX = 100; const int INF = 100000; int a[MAX][MAX], b[MAX][MAX], c[MAX][MAX]; int n, m, u, v, d, p, q; void nhap_du_lieu() { cin >> n >> m; for (int i = 0; i < n; a[i][i] = 0, i++) for (int j = 0; j < n; j++) a[i][j] = INF; for (int i = 0; i < m; i++) { cin >> u >> v >> d; a[u][v] = a[v][u] = d; } cin >> p >> q; } void floyd_warshall() { for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) b[i][j] = a[i][j], c[i][j] = j; for (int k = 0; k < n; k++) for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) if (b[i][j] > b[i][k] + b[k][j]) { b[i][j] = b[i][k] + b[k][j]; c[i][j] = c[i][k]; } if (b[p][q] == INF) cout << "Khong ton tai duong di"; else { cout << "Duong di ngan nhat: " << b[p][q] << endl; while (p != q) { cout << p << " --> "; p = c[p][q]; } cout << q; } } int main() { nhap_du_lieu(); floyd_warshall(); } /* Test 1: 6 10 0 1 5 0 2 2 1 2 2 1 3 4 1 4 7 2 3 20 2 4 6 3 4 2 3 5 1 4 5 5 0 5 */ <pre>

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66

  #include <iostream> #include <queue> using namespace std;   const int MAX = 100; const int INF = 100000;   int a[MAX][MAX], b[MAX][MAX], c[MAX][MAX]; int n, m, u, v, d, p, q;   void nhap_du_lieu() { cin >> n >> m; for (int i = 0; i < n; a[i][i] = 0, i++) for (int j = 0; j < n; j++) a[i][j] = INF; for (int i = 0; i < m; i++) { cin >> u >> v >> d; a[u][v] = a[v][u] = d; } cin >> p >> q; }   void floyd_warshall() { for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) b[i][j] = a[i][j], c[i][j] = j; for (int k = 0; k < n; k++) for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) if (b[i][j] > b[i][k] + b[k][j]) { b[i][j] = b[i][k] + b[k][j]; c[i][j] = c[i][k]; } if (b[p][q] == INF) cout << "Khong ton tai duong di"; else { cout << "Duong di ngan nhat: " << b[p][q] << endl; while (p != q) { cout << p << " --> "; p = c[p][q]; } cout << q; } }   int main() { nhap_du_lieu(); floyd_warshall(); }   /* Test 1: 6 10 0 1 5 0 2 2 1 2 2 1 3 4 1 4 7 2 3 20 2 4 6 3 4 2 3 5 1 4 5 5 0 5 */ <pre>

  Trả lời
• 

  10/11/2020 - 14:27

  admin  says:

  #include <iostream> using namespace std; const int MAX = 100; bool g[MAX][MAX]; bool v[MAX]; int n, m, p, q; void nhap_du_lieu() { cin >> n >> m; for (int i = 0; i < n; v[i] = false, i++) for (int j = 0; j < n; j++) g[i][j] = false; for (int i = 0; i < m; i++) { cin >> p >> q; g[p][q] = g[q][p] = true; } } void dfs(int s) { v[s] = true; cout << " " << s; for (int i = 0; i < n; i++) if (g[s][i] && !v[i]) dfs(i); } int main() { nhap_du_lieu(); cout << "Tu thu duyet cac dinh:"; dfs(0); } /* Test 2: 5 5 0 1 0 3 1 2 1 4 2 4 Test 1: 6 9 0 2 1 2 1 3 1 4 2 3 2 4 3 4 3 5 4 5 */ </iostream>

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54

  #include <iostream> using namespace std;   const int MAX = 100;   bool g[MAX][MAX]; bool v[MAX]; int n, m, p, q;   void nhap_du_lieu() { cin >> n >> m; for (int i = 0; i < n; v[i] = false, i++) for (int j = 0; j < n; j++) g[i][j] = false; for (int i = 0; i < m; i++) { cin >> p >> q; g[p][q] = g[q][p] = true; } }   void dfs(int s) {     v[s] = true;     cout << " " << s;     for (int i = 0; i < n; i++)         if (g[s][i] && !v[i]) dfs(i); }   int main() { nhap_du_lieu(); cout << "Tu thu duyet cac dinh:"; dfs(0); }   /* Test 2: 5 5 0 1 0 3 1 2 1 4 2 4 Test 1: 6 9 0 2 1 2 1 3 1 4 2 3 2 4 3 4 3 5 4 5 */ </iostream>

  Trả lời