Trang 1 trên tổng số 4 123... Cuối cùngCuối cùng
Từ 1 tới 10 trên tổng số 32 kết quả

Đề tài: Lý thuyết C++ | Giải thuật đồ thị cài đặt bằng C++

  1. #1
    Ngày gia nhập
    12 2006
    Nơi ở
    US
    Bài viết
    1,917

    Mặc định Lý thuyết C++ | Giải thuật đồ thị cài đặt bằng C++

    Trong topic này mình sẽ post những những thuật toán cơ bản trong đồ thị, full-code được cài đặt bằng C++. Vì mình nhận thấy lý thuyết đồ thị khá trừu tượng và rất khó cài khi ta chưa hiểu rõ bản chất. Mình hi vọng qua topic này, các bạn có thể sử dụng những đoạn code sau để hiểu rõ hơn thuật toán. Tuy nhiên lời khuyên chân thành của mìh đối với các bạn mới học là đừng chỉ copy code thôi, mà hãy giành ra chút thời gian để nghịch với chúng. Sau khi đã hiểu rõ rồi, thì hãy tự viết lại thì sẽ tốt hơn.
    Một lưu ý nhỏ là về phần lý thuyết mình chỉ tóm tắt sơ lược và để link tới wiki cho các bạn tìm và đọc thêm vì tài liệu về đồ thị trên mạng rất nhiều và kĩ năng viết của mình cũng chẳng có hay gì cho mấy. Tuy nhiên nếu bạn nào có thắc mắc thì cứ hỏi, mình sẽ cố gắng trả lời trong sự hiểu biết của mình.

    @ps: Nếu có bug trong đoạn code nào thì các bạn cứ báo cho mình biết, mình sẽ fix.

    Update 01/09/2013
    1) Khi xưa mình chuyển code từ Pascal sang C++ nên code khá rối răm và khó sử dụng, vì vậy mình quyết định sẽ viết lại toàn bộ các giải thuật trong topic này sử dụng chuẩn C++11.
    2) Đồng thời mình sẽ thêm vào cách giải thuật khác như Prim, Kruskal (Minimum Spanning Tree) và các ứng dụng của những giải thuật này để chúng ta có thể hiểu rõ hơn bản chất của chúng.
    3) Lưu ý để biên dịch các đoạn chương trình sau thì bạn phải dùng ít nhất là gcc/g++ bản 4.5 trở lên.


    Sau đây là một số biến quan trọng được dùng phần lớn cho các giải thuật:
    1. Danh sách cạnh kề:
    C++ Code:
    1. std::vector<std::vector<int>> adj(MAX_VERTEX);
    Ở đây nếu chúng ta có adj[u][v] nghĩa là có một cạnh từ đỉnh u sang đỉnh v.

    2. Thêm cạnh vào đồ thị:
    - Vô hướng (undirected)
    C++ Code:
    1. adj[u].push_back(v);
    2. adj[v].push_back(u);
    - Có hướng (directed)
    C++ Code:
    1. adj[u].push_back(v);

    3. Đánh dấu đỉnh đã duyệt:
    C++ Code:
    1. bool seen[MAX_VERTEX];
    Nếu seen[u] == true thì đỉnh u đã được duyệt qua

    4. Ma trận chi phí cho các bài toán tìm đường đi ngắn nhất
    C++ Code:
    1. const int oo = std::numeric_limits<int>::max();
    2. std::vector<std::vector<int>> cost;
    Ví dụ cost[u][v] = 10, có nghĩa là chi phí cho cạnh đi từ u sang v tốn 10 unit.



    Breadth First Search - Graph Traversal
    Mở đầu sẽ là thuật toán tìm kiếm theo chiều rộng dựa trên sự vận hành của queue (FIFO)

    I. Lý thuyết
    http://en.wikipedia.org/wiki/Breadth-first_search

    II. Cài đặt bằng C++
    C++ Code:
    1. #include <iostream>
    2. #include <queue>
    3. #include <vector>
    4.  
    5. const int MAX_VERTEX = 100;
    6. bool seen[MAX_VERTEX];
    7. std::vector<std::vector<int>> adj(MAX_VERTEX);
    8.  
    9. void visit(int u) {
    10.     std::cout << u << "\n";
    11. }
    12.  
    13. void bfs(int s) {
    14.     std::queue<int> q;
    15.     q.push(s);
    16.     seen[s] = true;
    17.     while (!q.empty()) {
    18.         int u = q.front();
    19.         visit(u);
    20.         q.pop();
    21.         for (auto v : adj[u]) {
    22.             if (!seen[v]) {
    23.                 seen[v] = true;
    24.                 q.push(v);
    25.             }
    26.         }
    27.     }
    28. }
    29.  
    30. /**
    31.  * For undirected graph
    32.  */
    33. void add_edge(int u, int v) {
    34.     adj[u].push_back(v);
    35.     adj[v].push_back(u);
    36. }
    37.  
    38. int main() {
    39.     add_edge(0, 1);
    40.     add_edge(0, 2);
    41.     add_edge(0, 3);
    42.     add_edge(1, 4);
    43.     add_edge(1, 5);
    44.     add_edge(2, 3);
    45.     bfs(0);
    46.     return 0;
    47. }

    III. Ứng dụng
    1. Tìm đường đi ngắn nhất (số cạnh) cho từng cặp đỉnh
    C++ Code:
    1. #include <iostream>
    2. #include <queue>
    3. #include <vector>
    4. #include <limits>
    5.  
    6. const int MAX_VERTEX = 100;
    7. const int oo = std::numeric_limits<int>::max();
    8. bool seen[MAX_VERTEX];
    9. std::vector<std::vector<int>> adj(MAX_VERTEX);
    10. std::vector<int> distance(MAX_VERTEX, oo);
    11.  
    12. void bfs(int s) {
    13.     std::queue<int> q;
    14.     q.push(s);
    15.     seen[s] = true;
    16.     distance[s] = 0;
    17.     while (!q.empty()) {
    18.         int u = q.front();
    19.         q.pop();
    20.         for (auto v : adj[u]) {
    21.             if (!seen[v]) {
    22.                 // recompute distance to v
    23.                 distance[v] = distance[u] + 1;
    24.                 seen[v] = true;
    25.                 q.push(v);
    26.             }
    27.         }
    28.     }
    29. }
    30.  
    31. /**
    32.  * For undirected graph
    33.  */
    34. void add_edge(int u, int v) {
    35.     adj[u].push_back(v);
    36.     adj[v].push_back(u);
    37. }
    38.  
    39. void shortest_distance() {
    40.     add_edge(0, 1);
    41.     add_edge(0, 2);
    42.     add_edge(0, 3);
    43.     add_edge(1, 4);
    44.     add_edge(4, 5);
    45.     bfs(0);
    46.     for (int v = 0; v < 6; ++v) {
    47.         std::cout << "shortest distance from 0->" << v << ": " << distance[v] << std::endl;
    48.     }
    49. }
    50.  
    51. int main() {
    52.     shortest_distance();
    53.     return 0;
    54. }

    2. Check bipartite graph (2-coloring)
    C++ Code:
    1. #include <iostream>
    2. #include <queue>
    3. #include <vector>
    4. #include <limits>
    5.  
    6. enum class color {
    7.     NONE, BLACK, WHITE
    8. };
    9.  
    10. const int MAX_VERTEX = 100;
    11. const int oo = std::numeric_limits<int>::max();
    12. std::vector<std::vector<int>> adj(MAX_VERTEX);
    13. std::vector<color> colors(MAX_VERTEX, color::NONE);
    14. bool is_bipartite = true;
    15.  
    16. color other(const color &c) {
    17.     if (c == color::NONE) {
    18.         return c;
    19.     }
    20.     return (c == color::BLACK) ? color::WHITE : color::BLACK;
    21. }
    22.  
    23. void bfs(int s) {
    24.     std::queue<int> q;
    25.     q.push(s);
    26.     colors[s] = color::WHITE;
    27.     while (!q.empty()) {
    28.         int u = q.front();
    29.         q.pop();
    30.         for (auto v : adj[u]) {
    31.             if (colors[v] == color::NONE) {
    32.                 colors[v] = other(colors[u]);
    33.                 q.push(v);
    34.             } else if (colors[v] == colors[u]) {
    35.                 is_bipartite = false;
    36.                 break;
    37.             }
    38.         }
    39.     }
    40. }
    41.  
    42. void add_edge(int u, int v) {
    43.     adj[u].push_back(v);
    44.     adj[v].push_back(u);
    45. }
    46.  
    47. void check_bipartite() {
    48.     add_edge(0, 3);
    49.     add_edge(0, 4);
    50.     add_edge(0, 5);
    51.     add_edge(0, 6);
    52.  
    53.     // add this edge will break bipartite property
    54.     // add_edge(0, 1);
    55.  
    56.     add_edge(1, 3);
    57.     add_edge(1, 4);
    58.     add_edge(1, 5);
    59.     add_edge(1, 6);
    60.  
    61.     add_edge(2, 3);
    62.     add_edge(2, 4);
    63.     add_edge(2, 5);
    64.     add_edge(2, 6);
    65.     bfs(0);
    66.     if (is_bipartite) {
    67.         std::cout << "G is bipartite." << std::endl;
    68.     } else {
    69.         std::cout << "G is non-bipartite." << std::endl;
    70.     }
    71. }
    72.  
    73. int main() {
    74.     check_bipartite();
    75.     return 0;
    76. }
    Đã được chỉnh sửa lần cuối bởi rox_rook : 03-09-2013 lúc 02:06 PM. Lý do: Bug fix, update to C++11

  2. #2
    Ngày gia nhập
    12 2006
    Nơi ở
    US
    Bài viết
    1,917

    Depth First Search - Graph Traversal
    Thuật toán kế tiếp là thuật toán tìm kiếm theo chiều sâu (DFS), nó cũng là một thuật toán dùng để viếng thăm các đỉnh của đồ thị. Điều khác biệt rõ ràng nhất với BFS là DFS hoạt động dựa trên sự vận hành của stack (FILO) thay vì queue (FIFO). Vì bản chất của DFS là dùng lời gọi đệ qui để gọi hàm, cho nên mình sẽ implement DFS dùng đệ qui thay vì dùng stack.

    I. Lý thuyết
    http://en.wikipedia.org/wiki/Depth-first_search

    II. Cài đặt bằng C++
    C++ Code:
    1. #include <iostream>
    2. #include <vector>
    3.  
    4. const int MAX_VERTEX = 100;
    5. bool seen[MAX_VERTEX];
    6. std::vector<std::vector<int>> adj(MAX_VERTEX);
    7.  
    8. void visit(int u) {
    9.     std::cout << u << "\n";
    10. }
    11.  
    12. void dfs(int u) {
    13.     visit(u);
    14.     seen[u] = true;
    15.     for (auto v : adj[u]) {
    16.         if (!seen[v]) {
    17.             dfs(v);
    18.         }
    19.     }
    20. }
    21.  
    22. /**
    23.  * For undirected graph
    24.  */
    25. void add_edge(int u, int v) {
    26.     adj[u].push_back(v);
    27.     adj[v].push_back(u);
    28. }
    29.  
    30. int main() {
    31.     add_edge(0, 1);
    32.     add_edge(0, 2);
    33.     add_edge(0, 3);
    34.     add_edge(1, 4);
    35.     add_edge(1, 5);
    36.     add_edge(2, 3);
    37.     dfs(0);
    38.     return 0;
    39. }

    III. Ứng dụng
    1. Tìm thành phần liên thông của đồ thị (connected components)
    C++ Code:
    1. #include <iostream>
    2. #include <vector>
    3.  
    4. const int MAX_VERTEX = 100;
    5. bool seen[MAX_VERTEX];
    6. std::vector<std::vector<int>> adj(MAX_VERTEX);
    7.  
    8. void dfs(int u) {
    9.     seen[u] = true;
    10.     for (auto v : adj[u]) {
    11.         if (!seen[v]) {
    12.             dfs(v);
    13.         }
    14.     }
    15. }
    16.  
    17. int count_connected_components(int no_vertex) {
    18.     int cnt = 0;
    19.     // for all vertex that has not been visited
    20.     for (int v = 0; v < no_vertex; ++v) {
    21.         if (!seen[v]) {
    22.             // increase the number of components
    23.             cnt++;
    24.             // visit
    25.             dfs(v);
    26.         }
    27.     }
    28.     return cnt;
    29. }
    30.  
    31. void add_edge(int u, int v) {
    32.     adj[u].push_back(v);
    33.     adj[v].push_back(u);
    34. }
    35.  
    36. int main() {
    37.     add_edge(0, 1);
    38.     add_edge(0, 2);
    39.     add_edge(3, 4);
    40.     add_edge(4, 5);
    41.     std::cout << count_connected_components(6) << std::endl;
    42.     return 0;
    43. }

    2. Toposort
    C++ Code:
    1. #include <iostream>
    2. #include <vector>
    3.  
    4. const int MAX_VERTEX = 100;
    5. bool seen[MAX_VERTEX];
    6. std::vector<std::vector<int>> adj(MAX_VERTEX);
    7. std::vector<int> topo_order;
    8.  
    9. void dfs(int u) {
    10.     seen[u] = true;
    11.     for (auto v : adj[u]) {
    12.         if (!seen[v]) {
    13.             dfs(v);
    14.         }
    15.     }
    16.     // keep track the order of visited
    17.     topo_order.push_back(u);
    18. }
    19.  
    20. void add_edge(int u, int v) {
    21.     adj[u].push_back(v);
    22.     adj[v].push_back(u);
    23. }
    24.  
    25. void toposort(int no_vertex) {
    26.     for (int v = 0; v < no_vertex; ++v) {
    27.         if (!seen[v]) {
    28.             dfs(v);
    29.         }
    30.     }
    31.     // print out topo order
    32.     for (auto v : topo_order) {
    33.         std::cout << v << " ";
    34.     }
    35. }
    36.  
    37. int main() {
    38.     add_edge(0, 1);
    39.     add_edge(0, 2);
    40.     add_edge(3, 4);
    41.     add_edge(4, 5);
    42.     toposort(6);
    43.     return 0;
    44. }

    3. Cycle detection
    C++ Code:
    1. #include <iostream>
    2. #include <vector>
    3. #include <algorithm>
    4.  
    5. enum class color {
    6.     WHITE, GRAY, BLACK
    7. };
    8.  
    9. const int MAX_VERTEX = 100;
    10. std::vector<std::vector<int>> adj(MAX_VERTEX);
    11. std::vector<color> colors(MAX_VERTEX);
    12. bool is_cyclic = false;
    13.  
    14. void dfs(int u) {
    15.     // start exploring
    16.     colors[u] = color::GRAY;
    17.     for (auto v : adj[u]) {
    18.         if (colors[v] == color::WHITE) {
    19.             dfs(v);
    20.         } else {
    21.             // check if back-edge exists
    22.             if (colors[v] == color::BLACK && colors[u] == color::GRAY) {
    23.                 is_cyclic = true;
    24.                 return;
    25.             }
    26.         }
    27.     }
    28.     // finish exploring
    29.     colors[u] = color::BLACK;
    30. }
    31.  
    32. void add_edge(int u, int v) {
    33.     adj[u].push_back(v);
    34.     adj[v].push_back(u);
    35. }
    36.  
    37. void check_cycle(int no_vertex) {
    38.     // initially, all vertex are not visited
    39.     std::fill(colors.begin(), colors.end(), color::WHITE);
    40.     is_cyclic = false;
    41.     for (int v = 0; v < no_vertex; ++v) {
    42.         if (colors[v] == color::WHITE) {
    43.             dfs(v);
    44.         }
    45.     }
    46.     if (is_cyclic) {
    47.         std::cout << "There is a cycle in this graph." << std::endl;
    48.     } else {
    49.         std::cout << "No cycle found." << std::endl;
    50.     }
    51. }
    52.  
    53. void test_cycle() {
    54.     add_edge(0, 1);
    55.     add_edge(1, 2);
    56.     add_edge(2, 0);
    57.     add_edge(4, 5);
    58.     check_cycle(6);
    59. }
    60.  
    61. void test_non_cycle() {
    62.     add_edge(0, 1);
    63.     add_edge(1, 2);
    64.     add_edge(4, 5);
    65.     check_cycle(6);
    66. }
    67.  
    68. int main() {
    69.     test_non_cycle();
    70.     // test_cycle();
    71.     return 0;
    72. }
    Đã được chỉnh sửa lần cuối bởi rox_rook : 03-09-2013 lúc 01:21 PM. Lý do: Bug fix, update to C++11

  3. #3
    Ngày gia nhập
    12 2006
    Nơi ở
    US
    Bài viết
    1,917

    Roy Warshall's Algorithm - Shortest Path Problem
    Thuật toán tiếp theo có tên là Floyd Warshall dùng để tìm đường với chi phi thấp nhất từ 2 cặp đỉnh (u, v). Running time cho giải thuật này là O(n^3) khá chậm so với Dijsktra, tuy nhiên nếu chúng ta cần query nhiều lần với những cặp đỉnh khác nhau thì việc precompute trước cho toàn bộ các cặp đỉnh thì thuật toán này sẽ nhanh hơn Dijkstra rất nhiều.
    Giả sử chúng ta đồ thị với V đỉnh, E cạnh, và M query thì:
    - Floyd Warshall sẽ có running time O(V^3) + M
    - Dijsktra Heap: M * O(E * log(V))

    I. Lý thuyết
    http://en.wikipedia.org/wiki/Floyd%E...hall_algorithm

    II. Cài đặt bằng C++
    C++ Code:
    1. #include <iostream>
    2. #include <vector>
    3. #include <limits>
    4.  
    5. const int oo = std::numeric_limits<int>::max();
    6. std::vector<std::vector<int>> cost;
    7.  
    8. void floyd_warshall(int no_vertex) {
    9.     for (int bridge = 0; bridge < no_vertex; ++bridge) {
    10.         for (int u = 0; u < no_vertex; ++u) {
    11.             for (int v = 0; v < no_vertex; ++v) {
    12.                 cost[u][v] = std::min(cost[u][v], cost[u][bridge] + cost[bridge][v]);
    13.             }
    14.         }
    15.     }
    16. }
    17.  
    18. std::vector<std::vector<int>> generate_sample_cost() {
    19.     return std::vector<std::vector<int>> {
    20.         std::vector<int> {0, 2, 1, 3},
    21.         std::vector<int> {1, 0, 4, 5},
    22.         std::vector<int> {3, 1, 0, 3},
    23.         std::vector<int> {1, 1, 1, 0},
    24.     };
    25. }
    26.  
    27. void query(int u, int v) {
    28.     std::cout << "shortest path from " << u << "->" << v << ": " << cost[u][v] << "\n";
    29. }
    30.  
    31. int main() {
    32.     cost = generate_sample_cost();
    33.     floyd_warshall(cost.size());
    34.     query(0, 2);
    35.     query(1, 2);
    36.     return 0;
    37. }
    Đã được chỉnh sửa lần cuối bởi rox_rook : 03-09-2013 lúc 01:19 PM. Lý do: Fix bug, update to C++11

  4. #4
    Ngày gia nhập
    08 2006
    Bài viết
    59

    Tui xin góp 1 chút ý kiến:

    DFS khác với BFS ở chỗ nó dùng đệ qui để tìm các đỉnh cần tới, trong khi BFS thì sử dụng cấu trúc dữ liệu hàng đợi.
    => 1 cách khác để cài đặt DFS là thay đổi 1 chỗ rất nhỏ trong chương trình BFS ở trên: xài ngăn xếp (stack) thay cho hàng đợi (queue) (khi mình xài đệ qui là mình đã gián tiếp xài stack)

    P.S.: không biết kiểu dữ liệu queue ở trong chương trình BFS có phải là từ STL hay không ? Thông thường thì 2 phương thức thêm vô/xóa từ queue được gọi là enqueue & dequeue; còn tương ứng với stack thì là push/pop; nhưng đây chỉ là tiểu tiết mà thôi

    (hiểu biết nông cạn; có gì sai sót mong được góp ý; xin cám ơn)

    -thân

  5. #5
    Ngày gia nhập
    12 2006
    Nơi ở
    US
    Bài viết
    1,917

    Prim's Algorithm - Minimum Spanning Tree
    Thuật toán tiếp theo là thuật toán Prim, dùng để giải bài toán tìm cây khung nhỏ nhất trong đồ thị vô hướng. Thuật toán Prim là một dạng của thuật toán "tham lam" (greedy) vì nó luôn chọn cạnh với chi phí thấp nhất nhờ vào sự trợ giúp của min-heap. Về phần lý thuyết, các bạn có thể tham khảo những link sau.

    I. Lý thuyết

    http://en.wikipedia.org/wiki/Prim's_algorithm
    http://en.wikipedia.org/wiki/Minimum_spanning_tree

    II. Cài đặt bằng C++
    C++ Code:
    1. #include <algorithm>
    2. #include <iostream>
    3. #include <queue>
    4. #include <vector>
    5. #include <utility>
    6.  
    7. struct edge {
    8.     int v;
    9.     int cost;
    10.  
    11.     edge(int v, int cost)
    12.         :v(v), cost(cost) {
    13.     }
    14.  
    15.     // sort by cost first then vertex
    16.     bool operator >(const edge &e) const {
    17.         return (cost != e.cost ? cost > e.cost : v > e.v);
    18.     }
    19. };
    20.  
    21. // alias for min priority queue
    22. typedef std::priority_queue<edge, std::vector<edge>, std::greater<edge>> min_heap;
    23. // infinity
    24. const int oo = std::numeric_limits<int>::max();
    25. // maximum # of vertex
    26. const int MAX_VERTEX = 100;
    27. // mark array
    28. bool seen[MAX_VERTEX];
    29. // adjacency list
    30. std::vector<std::vector<int>> adj(MAX_VERTEX);
    31. // cost matrix, initially all cost are infinity
    32. std::vector<std::vector<int>> cost(MAX_VERTEX, std::vector<int>(MAX_VERTEX, oo));
    33. // minimum cost heap
    34. min_heap pq;
    35.  
    36. /**
    37.  * For all vertex that are adjacent to u,
    38.  * if it's not visited, we add them to
    39.  * our queue with its cost
    40.  */
    41. void relax(int u) {
    42.     seen[u] = true;
    43.     for (auto v : adj[u]) {
    44.         if (!seen[v]) {
    45.             pq.push(edge(v, cost[u][v]));
    46.         }
    47.     }
    48. }
    49.  
    50. /**
    51.  * Prim algorithm for finding the minimum
    52.  * spanning tree of undirected graph
    53.  */
    54. int prim(int s) {
    55.     int min_cost = 0;
    56.     relax(s);
    57.     while (!pq.empty()) {
    58.         // get the minimum cost edge
    59.         edge e = pq.top();
    60.         pq.pop();
    61.         // if we have seen v
    62.         // visit v, and update new cost
    63.         if (!seen[e.v]) {
    64.             min_cost += e.cost;
    65.             relax(e.v);
    66.         }
    67.     }
    68.     return min_cost;
    69. }
    70.  
    71. void add_edge(int u, int v, int c) {
    72.     adj[u].push_back(v);
    73.     adj[v].push_back(u);
    74.     cost[u][v] = c;
    75.     cost[v][u] = c;
    76. }
    77.  
    78. void test_minimum_spanning_tree() {
    79.     add_edge(0, 1, 3);
    80.     add_edge(0, 2, 3);
    81.     add_edge(0, 3, 1);
    82.     add_edge(0, 4, 2);
    83.     add_edge(1, 2, 2);
    84.     add_edge(2, 3, 11);
    85.     add_edge(3, 4, 9);
    86.     std::cout << "min cost: " << prim(0) << std::endl;
    87. }
    88.  
    89. int main() {
    90.     test_minimum_spanning_tree();
    91.     return 0;
    92. }
    Đã được chỉnh sửa lần cuối bởi rox_rook : 03-09-2013 lúc 01:20 PM.

  6. #6
    Ngày gia nhập
    11 2006
    Bài viết
    633

    Mặc định Lý thuyết C++ | Giải thuật đồ thị cài đặt bằng C++

    bản thân đệ quy nó sẽ tạo 1 stack ở trong vùng stack của chương trình còn stack thì ta tự tạo cho riêng mình. Ý nghĩa ko khác nhau nhưng việc sử dụng sẽ có vấn đề khi đệ quy quá lớn

  7. #7
    Ngày gia nhập
    12 2006
    Nơi ở
    US
    Bài viết
    1,917

    Kruskal's Algorithm - Minimum Spanning Tree
    Thuật toán này cũng là một dạng thuật toán tham lam dùng để giải bài toán cây khung nhỏ nhất (giống như Prim). Điểm khác biệt giữa Kruskal và Prim là Kruskal hoạt động dựa trên cấu trúc dữ liệu có tên là "Disjoint Set".

    I. Lý thuyết
    http://en.wikipedia.org/wiki/Kruskal's_algorithm
    http://en.wikipedia.org/wiki/Disjoin...data_structure

    II. Cài đặt bằng C++
    C++ Code:
    1. #include <algorithm>
    2. #include <iostream>
    3. #include <vector>
    4. #include <utility>
    5.  
    6. const int MAX_SIZE = 100;
    7.  
    8. class disjoint_set {
    9. private:
    10.     int components;
    11.     int id[MAX_SIZE];
    12.     int sizeof_ids[MAX_SIZE];
    13.     int n;
    14.  
    15. public:
    16.     disjoint_set(int n)
    17.         :components(n), n(n) {
    18.         for (int i = 0; i < components; ++i) {
    19.             id[i] = i;
    20.             sizeof_ids[i] = 1;
    21.         }
    22.     }
    23.  
    24.     void join(int p, int q) {
    25.         int i = find(p);
    26.         int j = find(q);
    27.         if (i == j) {
    28.             return;
    29.         }
    30.         if (sizeof_ids[i] < sizeof_ids[j]) {
    31.             id[i] = j;
    32.             sizeof_ids[j] += sizeof_ids[i];
    33.             sizeof_ids[i] = 1;
    34.         } else {
    35.             id[j] = i;
    36.             sizeof_ids[i] += sizeof_ids[j];
    37.             sizeof_ids[j] = 1;
    38.         }
    39.         components--;
    40.     }
    41.  
    42.     int find(int p) {
    43.         if (p != id[p]) {
    44.             id[p] = find(id[p]);
    45.         }
    46.         return id[p];
    47.     }
    48.  
    49.     bool is_connected(int p, int q) {
    50.         return find(p) == find(q);
    51.     }
    52.  
    53.     int size() const {
    54.         return components;
    55.     }
    56. };
    57.  
    58. struct edge {
    59.     int u;
    60.     int v;
    61.     int cost;
    62.  
    63.     edge(int u, int v, int cost)
    64.         :u(u), v(v), cost(cost) {
    65.     }
    66.  
    67.     // sort by cost
    68.     bool operator <(const edge &e) const {
    69.         return cost < e.cost;
    70.     }
    71. };
    72.  
    73. std::vector<edge> edges;
    74.  
    75. int kruskal(int no_vertex) {
    76.     int min_cost = 0;
    77.     std::sort(edges.begin(), edges.end());
    78.     disjoint_set ds(no_vertex);
    79.     for (auto e : edges) {
    80.         if (!ds.is_connected(e.u, e.v)) {
    81.             min_cost += e.cost;
    82.             ds.join(e.u, e.v);
    83.         }
    84.     }
    85.     return min_cost;
    86. }
    87.  
    88. void test_minimum_spanning_tree() {
    89.     edges.push_back(edge(0, 1, 3));
    90.     edges.push_back(edge(0, 2, 3));
    91.     edges.push_back(edge(0, 3, 1));
    92.     edges.push_back(edge(0, 4, 2));
    93.     edges.push_back(edge(1, 2, 2));
    94.     edges.push_back(edge(2, 3, 11));
    95.     edges.push_back(edge(3, 4, 9));
    96.     std::cout << "min cost: " << kruskal(5) << std::endl;
    97. }
    98.  
    99. int main() {
    100.     test_minimum_spanning_tree();
    101.     return 0;
    102. }
    Đã được chỉnh sửa lần cuối bởi rox_rook : 03-09-2013 lúc 01:20 PM. Lý do: Fix bug, update to C++11

  8. #8
    Ngày gia nhập
    12 2006
    Nơi ở
    US
    Bài viết
    1,917

    Dijkstra's Algorithm - Shortest Path Problem
    Tiếp theo là giải thuật Dijkstra dùng để giải bài toán tìm đường đi ngắn nhất giữa các đỉnh trên đồ thị có trọng số. Cho đồ thị G = (V, E) thì Dijkstra có running time là O(E log(V)).

    I. Lý thuyết
    http://en.wikipedia.org/wiki/Dijkstra's_algorithm

    II. Cài đặt bằng C++
    C++ Code:
    1. #include <iostream>
    2. #include <vector>
    3. #include <limits>
    4.  
    5. #include <iostream>
    6. #include <queue>
    7. #include <vector>
    8. #include <limits>
    9. #include <queue>
    10.  
    11. // priority queue
    12. typedef std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int> >, std::greater<std::pair<int, int>> > min_heap;
    13. // cost and vertex
    14. typedef std::pair<int, int> vertex;
    15.  
    16. const int oo = std::numeric_limits<int>::max();
    17. const int MAX_VERTEX = 100;
    18. std::vector<std::vector<int>> adj(MAX_VERTEX);
    19. std::vector<std::vector<int>> cost(MAX_VERTEX, std::vector<int>(MAX_VERTEX, oo));
    20. std::vector<int> dist(MAX_VERTEX, oo);
    21.  
    22. void dijkstra(int s) {
    23.     min_heap pq;
    24.     dist[s] = 0;
    25.     pq.push(vertex(0, s));
    26.     while (!pq.empty()) {
    27.         int u = pq.top().second;
    28.         int cost_to_u = pq.top().first;
    29.         pq.pop();
    30.         if (dist[u] == cost_to_u) {
    31.             for (auto v : adj[u]) {
    32.                 if (dist[v] > dist[u] + cost[u][v]) {
    33.                     dist[v] = dist[u] + cost[u][v];
    34.                     pq.push(vertex(dist[v], v));
    35.                 }
    36.             }
    37.         }
    38.     }
    39. }
    40.  
    41. void add_edge(int u, int v, int c) {
    42.     adj[u].push_back(v);
    43.     cost[u][v] = c;
    44. }
    45.  
    46. int main() {
    47.     add_edge(0, 1, 13);
    48.     add_edge(1, 2, 8);
    49.     add_edge(2, 4, 1);
    50.     add_edge(0, 2, 18);
    51.     add_edge(0, 3, 20);
    52.     add_edge(0, 4, 23);
    53.     dijkstra(0);
    54.     for (int v = 0; v <= 4; ++v) {
    55.         std::cout << "shortest path from 0->" << v << ": " << dist[v] << "\n";
    56.     }
    57.     return 0;
    58. }
    Đã được chỉnh sửa lần cuối bởi rox_rook : 03-09-2013 lúc 01:20 PM. Lý do: Bug fix, update to C++11

  9. #9
    Ngày gia nhập
    12 2006
    Nơi ở
    US
    Bài viết
    1,917

    Tarjan's Algorithm - Strongly Connected Component
    ... work in progress
    Đã được chỉnh sửa lần cuối bởi rox_rook : 03-09-2013 lúc 01:24 PM.

  10. #10
    Ngày gia nhập
    04 2008
    Bài viết
    4

    Bạn có thể làm một bài tìm cây khung (cây bao trùm) nhỏ nhất - theo hướng thủ tục- sử dụng hai thuật toán Prim và Kruskal ko
    Cám ơn bạn trước nha

Các đề tài tương tự

  1. Các giải thuật tìm kiếm - Lý thuyết và cài đặt trên C
    Gửi bởi PoPoPoPo trong diễn đàn Thủ thuật, Tutorials CTDL & Giải thuật
    Trả lời: 5
    Bài viết cuối: 24-02-2015, 05:21 PM
  2. Các giải thuật sắp xếp - Lý thuyết và cài đặt trên C
    Gửi bởi PoPoPoPo trong diễn đàn Thủ thuật, Tutorials CTDL & Giải thuật
    Trả lời: 28
    Bài viết cuối: 15-05-2013, 11:10 AM
  3. Lý thuyết đồ thị | Giải thuật DFS (Depth First Search)
    Gửi bởi vie_kainznz trong diễn đàn Thủ thuật, Tutorials CTDL & Giải thuật
    Trả lời: 1
    Bài viết cuối: 14-01-2013, 10:48 PM
  4. [Lý thuyết giải thuật] Một số bài tập về giải thuật và cách giải
    Gửi bởi hailoc12 trong diễn đàn Thủ thuật, Tutorials CTDL & Giải thuật
    Trả lời: 6
    Bài viết cuối: 27-01-2010, 04:10 PM
  5. Lý thuết đồ thị | Bài tập Lý thuyết đồ thị
    Gửi bởi soda_chanhmuoi trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 3
    Bài viết cuối: 11-02-2008, 08:01 AM

Quyền hạn của bạn

  • Bạn không thể gửi đề tài mới
  • Bạn không thể gửi bài trả lời
  • Bạn không thể gửi các đính kèm
  • Bạn không thể chỉnh sửa bài viết của bạn