10.4K 779 121

Đã đăng vào Thứ Sáu, 9:45 SA 19 phút đọc

Bài toán cây khung nhỏ nhất

I. Giới thiệu chung

Những giải thuật trên đồ thị luôn luôn là một chủ đề khiến cho chúng ta phải đau đầu, đặc biệt là với những ai đang nghiên cứu về chủ đề Cấu trúc dữ liệu & Giải thuật. Một trong số những bài toán kinh điển của chủ đề Đồ thị là Bài toán tìm cây khung nhỏ nhất (Minimum Spanning Tree). Đây là một bài toán có lịch sử lâu đời và có ứng dụng nhiều trong thực tế đời sống. Tuy nhiên, trước hết chúng ta sẽ cùng tìm hiểu về một số khái niệm cần thiết trong chuyên đề này.

Lưu ý rằng, trong bài toán này sẽ sử dụng tới cấu trúc dữ liệu Disjoint Sets Union (DSU).

1. Cây khung của đồ thị (Spanning Trees)

Như ta đã biết, đồ thị vô hướng $G(V, E)$ là một đồ thị có tập đỉnh là $V$ và tập cạnh là $E,$ với các cạnh đều vô hướng. Một cây khung của đồ thị là một tập các cạnh của đồ thị thỏa mãn hai điều kiện:

Tập cạnh này không chứa chu trình.
Tập cạnh này liên thông và chứa tất cả các đỉnh của đồ thị.

Nói cách khác, nếu đồ thị gồm $n$ đỉnh thì cây khung của đồ thị là một đồ thị con liên thông chứa đủ $n$ đỉnh và $n - 1$ cạnh của đồ thị ban đầu.

Một đồ thị có thể có một hoặc nhiều cây khung. Hình vẽ dưới đây minh họa các cây khung có thể có trên một đồ thị vô hướng không có trọng số:

</center>

Trong chuyên đề này, chúng ta sẽ chỉ làm việc với cây khung trên đồ thị vô hướng. Thực tế thì các bài toán về cây khung cũng chỉ hầu hết cho trên đồ thị vô hướng mà thôi.

2. Cây khung nhỏ nhất (Minimum Spanning Tree)

Xét một đồ thị vô hướng $G(V, E)$ có trọng số, cây khung nhỏ nhất của đồ thị là cây khung có tổng trọng số các cạnh trên cây là nhỏ nhất.

Hình vẽ dưới đây minh họa một cây khung nhỏ nhất trên đồ thị có trọng số:

</center>

3. Bài toán tìm cây khung nhỏ nhất

Bài toán tìm cây khung nhỏ nhất trên đồ thị được phát biểu như sau: Cho đơn đồ thị $G$ vô hướng có trọng số gồm $n$ đỉnh và $m$ cạnh. Với một cây khung $T$ của đồ thị, ta gọi trọng số của cây $T$ là tổng trọng số của các cạnh trên cây. Hãy xác định cây khung có trọng số nhỏ nhất?

Input:

Dòng đầu tiên chứa hai số nguyên dương $n, m$ - số đỉnh và số cạnh của đồ thị.
$m$ dòng tiếp theo, mỗi dòng chứa ba số nguyên dương $u, v, c$ - thể hiện một cạnh của đồ thị nối hai đỉnh $u, v$ có trọng số là $c$ .

Ràng buộc:

$1 \le n, m \le 10^6$ .
$1 \le u \ne v \le n$ .
$1 \le c \le 10^6$ .

Output:

In ra trọng số của cây khung nhỏ nhất, theo sau đó là các cạnh của cây khung kèm theo trọng số, mỗi cạnh trên một dòng. Còn nếu đồ thị không liên thông thì đưa ra thông báo Unconnected Graph.

Sample Input:

Sample Output:

Giải thích:

Cây khung của đồ thị được thể hiện ở hình bên dưới:

</center>

Có hai giải thuật phổ biến để tìm cây khung nhỏ nhất trên đồ thị, và dưới đây chúng ta sẽ cùng phân tích cả hai giải thuật đó.

II. Giải thuật Kruskal (Joseph Kruskal - 1956)

1. Ý tưởng

Giải thuật Kruskal được phát minh vào năm $1956$ bởi nhà khoa học cùng tên người Hoa Kỳ, lấy cấu trúc dữ liệu Disjoint Sets Union làm nền tảng. Ý tưởng sẽ là khởi tạo một cây khung $T$ rỗng, rồi tuần tự thêm các cạnh vào cây cho tới khi tạo được một cây khung của đồ thị gồm $n - 1$ cạnh. Tuy nhiên, ta sẽ không thêm cạnh theo thứ tự tùy ý, mà sẽ chọn các cạnh lần lượt theo thứ tự tăng dần của trọng số.

Kế tiếp, lần lượt thử thêm các cạnh vào cây $T$ . Nếu như cạnh $(u, v)$ thêm vào cây $T$ mà không tạo ra chu trình đơn, thì kết nạp cạnh đó vào cây. Cứ làm như vậy cho tới khi:

Hoặc đã kết nạp đủ $n - 1$ cạnh vào cây, khi đó ta thu được $T$ là cây khung nhỏ nhất của đồ thị.
Hoặc chưa kết nạp đủ $n - 1$ cạnh vào cây nhưng trong các cạnh còn lại, thêm cạnh nào vào cây cũng tạo ra chu trình đơn. Khi đó đồ thị ban đầu là không liên thông, đồng nghĩa với việc không thể tìm thấy cây khung.

Việc sắp xếp lại các cạnh của đồ thị theo thứ tự tăng dần của trọng số rất đơn giản, chỉ cần sử dụng một danh sách cạnh kiểu bản ghi gồm ba thông số: $(u, v, c)$ lần lượt là hai đầu mút của cạnh và trọng số của cạnh đó, rồi sắp xếp danh sách đó theo trường $c$ là xong. Nhưng làm sao để xác định một cạnh khi thêm vào cây có tạo thành chu trình đơn hay không? Nhận xét rằng, tập cạnh trong $T$ ở các bước sẽ tạo thành một rừng các cây phân biệt (đồ thị không có chu trình đơn). Muốn thêm một cạnh $(u,v)$ vào rừng $T$ mà không tạo thành chu trình đơn thì cạnh đó phải nối hai cây khác nhau trong $T$ (nếu nối giữa hai đỉnh trong cùng một cây thì sẽ tạo thành chu trình đơn trong cây đó). Áp dụng cấu trúc dữ liệu DSU, ta có một cách nhanh để xây dựng giải thuật Kruskal:

Xét cạnh $(u,v),$ xác định gốc của hai đỉnh $u$ và $v$ là $r_1$ và $r_2$ .
Nếu $r_1=r_2,$ tức là $u$ và $v$ thuộc chung một cây, việc thêm cạnh $(u,v)$ vào $T$ sẽ tạo ra chu trình đơn. Trường hợp này ta không thu nhận cạnh $(u,v)$ vào cây khung.
Nếu $r1≠r2,$ tức là $u$ và $v$ thuộc hai cây khác nhau, ta hợp nhất hai cây gốc $r_1$ và $r_2,$ thêm cạnh $(u,v)$ vào cây khung.
<center>

Hợp nhất hai cây gốc $r_1$ và $r_2$
</center>
Nếu số lượng cạnh của $T$ đã đủ $n-1,$ dừng thuật toán và đưa ra cây khung tương ứng. Ngược lại nếu đã duyệt hết các cạnh của đồ thị mà vẫn không chọn đủ $n-1$ cạnh vào $T,$ trường hợp này đồ thị không liên thông, việc tìm kiếm cây khung thất bại.

2. Cài đặt

Ngôn ngữ C++:

#include <bits/stdc++.h>

using namespace std;

struct Edge
{
    int u, v, c;
};

void enter(int &n, int &m, vector < Edge> &edges)
{
    cin >> n >> m;

    edges.resize(m);
    for (int i = 0; i < m; ++i)
        cin >> edges[i].u >> edges[i].v >> edges[i].c;
}

// Hàm so sánh để sắp xếp lại cạnh của đồ thị theo trọng số.
bool cmp(Edge a, Edge b)
{
    return a.c < b.c;
}

// Tìm gốc của đỉnh u.
int find_root(int u, vector < int > &lab)
{
    return (lab[u] < 0) ? u : lab[u] = find_root(lab[u], lab);
}

// Hợp nhất hai cây con gốc r1 và r2.
void union_trees(int r1, int r2, vector < int > &lab)
{
    int child_r1 = -lab[r1], child_r2 = -lab[r2];

    if (child_r1 < child_r2)
        swap(r1, r2);

    lab[r1] += lab[r2];
    lab[r2] = r1;
}

void kruskal(int n, int m, vector < Edge > &edges)
{
    // Khởi tạo rừng các cây ban đầu gồm n đỉnh phân biệt, coi như n cây.
    // Ban đầu gốc của các cây là chính nó, khởi tạo bằng -1 theo DSU.
    vector < int > lab(n + 1, -1);
    // Sắp xếp các cạnh của đồ thị theo thứ tự tăng dần về trọng số.
    sort(edges.begin(), edges.end(), cmp);

    int mst_weight = 0;
    vector < Edge > mst_edges;
    for (int i = 0; i < m; ++i)
    {
        int r1 = find_root(edges[i].u), r2 = find_root(edges[i].v);

        // Thêm cạnh (u, v) vào đồ thị nếu cạnh này không tạo ra chu trình đơn.
        // Hợp nhất hai cây chứa hai đỉnh u và v.
        if (r1 != r2)
        {
            union_trees(r1, r2, lab);
            mst_weight += edges[i].c;
            mst_edges.push_back(edges[i]);
        }

        // Đã kết nạp đủ n - 1 cạnh, dừng thuật toán.
        if (mst_edges.size() == n - 1)
            break;
    }

    // Kết luận có tìm được cây khung hay không và đưa ra cây khung nếu có.
    if (mst_edges.size() != n - 1)
        cout << "Unconnected Graph";
    else 
    {
        cout << mst_weight << endl;
        for (auto e: mst_edges)
            cout << e.u << ' ' << e.v << ' ' << e.c << endl;
    }
}

main()
{
    int n, m;
    vector < Edge > edges;

    enter(n, m, edges);
    kruskal(n, m, edges);

    return 0;
}

Ngôn ngữ Python:

# Tìm gốc của đỉnh u.
def find_root(u, lab):
    if lab[u] < 0:
        return u
    else:
        lab[u] = find_root(lab[u], lab)
        return lab[u]


# Hợp nhất hai cây con gốc r1 và r2.
def union_trees(r1, r2, lab):
    child_r1, child_r2 = -lab[r1], -lab[r2]

    if child_r1 < child_r2:
        r1, r2 = r2, r1

    lab[r1] += lab[r2]
    lab[r2] = r1


# Hàm so sánh để sắp xếp lại cạnh của đồ thị theo trọng số.
def take_weight(element):
    return element[2]


def kruskal(n, m, edges):
    # Khởi tạo rừng các cây ban đầu gồm n đỉnh phân biệt, coi như n cây.
    # Ban đầu gốc của các cây là chính nó, khởi tạo bằng -1 theo DSU.
    lab = [-1] * (n + 1)
    # Sắp xếp các cạnh của đồ thị theo thứ tự tăng dần về trọng số.
    edges = sorted(edges, key=take_weight)

    mst_weight = 0
    mst_edges = []
    for i in range(m):
        r1, r2 = find_root(edges[i][0], lab), find_root(edges[i][1], lab)

        # Thêm cạnh (u, v) vào đồ thị nếu cạnh này không tạo ra chu trình đơn.
        # Hợp nhất hai cây chứa hai đỉnh u và v.
        if r1 != r2:
            union_trees(r1, r2, lab)
            mst_weight += edges[i][2]
            mst_edges.append(edges[i])
        
        if len(mst_edges) == n - 1:
            break

    # Kết luận có tìm được cây khung hay không và đưa ra cây khung nếu có.
    if len(mst_edges) != n - 1:
        print('Unconnected Graph')
    else:
        print(mst_weight)
        for (u, v, c) in mst_edges:
            print(u, v, c)


if __name__ == '__main__':
    n, m = map(int, input().split())
    
    edges = []
    for _ in range(m):
        u, v, c = map(int, input().split())
        edges.append((u, v, c))

    kruskal(n, m, edges)

III. Giải thuật Prim (Robert Prim - 1957)

1. Ý tưởng

Trong trường hợp đồ thị dày (có nhiều cạnh), thì giải thuật Kruskal sẽ hoạt động hơi chậm (bởi vì bắt buộc phải sắp xếp lại các cạnh trước khi thực hiện giải thuật). Nhà khoa học Robert C. Prim đã phát triển hoàn chỉnh thuật toán Prim vào năm $1957,$ cho phép tìm kiếm cây khung nhỏ nhất của đồ thị một cách hiệu quả trong trường hợp đồ thị dày và có số đỉnh vừa phải.

Giải thuật có thể phát biểu như sau: Trên đơn đồ thị vô hướng $G=(V,E)$ có $n$ đỉnh, quy ước $w_{u,v}$ là trọng số cạnh $(u,v)$ . Xét cây $T$ trong $G$ và một đỉnh $v$ bất kỳ, gọi khoảng cách từ $v$ tới $T$ là trọng số nhỏ nhất trong số các cạnh nối trực tiếp của $v$ với một đỉnh nào đó trong $T$ :

$d[v]=\text{min}{w_{u,v} | u \in T}$

Ban đầu ta khởi tạo cây $T$ chỉ gồm đỉnh $\{1\}$ . Sau đó, cứ chọn trong số các đỉnh không thuộc $T$ một đỉnh $u$ gần $T$ nhất, kết nạp đỉnh đó vào $T,$ đồng thời kết nạp luôn cạnh nối tạo ra khoảng cách gần nhất đó. Cứ làm như vậy cho tới khi:

Hoặc đã kết nạp được $n$ đỉnh thì ta có $T$ chính là cây khung nhỏ nhất.
Hoặc chưa kết nạp được hết $n$ đỉnh, nhưng đã xét hết cạnh của đồ thị. Khi đó đồ thị đã cho không liên thông, việc tìm cây khung thất bại.

Về kĩ thuật cài đặt, ban đầu gán $d[1]=1$ và $d[u]=\infty; \forall u≠1$ . Tại mỗi bước chọn đỉnh, ta tìm đỉnh $u$ không thuộc $T$ có $d[u]$ nhỏ nhất. Khi kết nạp $u$ vào $T,$ cập nhật lại khoảng cách từ các đỉnh còn lại tới cây $T$ :

$d[v]=\text{min}\big(d[v],w_{u,v}\big),$ với $v$ là các đỉnh kề với $u$ .

</center>

Sử dụng một mảng lưu vết, gán $trace[v]=u$ khi tìm được đỉnh $v$ gần $T$ nhất ở mỗi bước kết nạp, mục đích lưu lại đỉnh $u$ thuộc $T$ nối với $v$ đã tạo ra khoảng cách gần nhất đó, sau này ta sẽ sử dụng để truy vết. Nếu số lượng đỉnh của đồ thị không nhiều, ta có thể sử dụng ma trận kề để biểu diễn, và thuật toán khi đó có độ phức tạp $O(n^2)$ .

Việc tìm ra đỉnh $u$ gần $T$ nhất (có $d[u]$ nhỏ nhất) có thể được cải tiến bằng cách sử dụng Heap (trong C++/Python đã được cài đặt sẵn bằng hàng đợi ưu tiên) cùng với danh sách kề để biểu diễn đồ thị. Tuy nhiên, thông thường trên đồ thị có số cạnh vừa phải, người ta sẽ sử dụng giải thuật Kruskal thay vì dùng Prim Heap.

Khi đó, độ phức tạp giải thuật sẽ là: $O\big((n + m) \times \log(n)\big)$ .

3. Cài đặt

Cài đặt cơ bản không sử dụng Heap

Ngôn ngữ C++:

#include <bits/stdc++.h>

using namespace std;

const int INFTY = 2e6;

// Nhập đồ thị, lưu trọng số các cạnh bằng một ma trận kề.
// Cách làm phù hợp với đồ thị có số đỉnh khoảng 5000 trở xuống.
void enter(int &n, int &m, vector < vector < int > > &weight)
{
    cin >> n >> m;

    weight = vector < vector < int > >(n + 1, vector < int >(n + 1));
    for (int u = 1; u <= n; ++u)
        for (int v = 1; v <= n; ++v)
            weight[u][v] = (u == v) ? 0 : INFTY;

    for (int i = 1; i <= m; ++i)
    {
        int u, v;
        cin >> u >> v >> weight[u][v];

        weight[v][u] = weight[u][v];
    }
}

// Giải thuật Prim chưa cải tiến bước tìm đỉnh u có d[u] nhỏ nhất.
void basic_prim(int n, int m, vector < vector < int > > &weight)
{
    vector < int > d(n + 1, INFTY);
    vector < bool > is_free(n + 1, true);
    vector < int > trace(n + 1);
    is_free[1] = false;
    d[1] = 0;

    for (int i = 1; i <= n; ++i)
    {
        // Tìm đỉnh u chưa bị kết nạp vào cây khung có d[u] nhỏ nhất.
        int u = 0, flag = INFTY;
        for (int v = 1; v <= n; ++v)
            if (is_free[v] && d[v] < flag)
            {
                flag = d[v];
                u = v;
            }

        // Nếu không tìm được u thì đồ thị không liên thông, việc tìm
        // cây khung thất bại và ta dừng thuật toán tại đây.
        if (u == 0)
        {
            cout << "Unconnected Graph";
            return;
        }

        // Kết nạp u vào cây khung nếu tìm thấy u, đánh dấu nó đã kết nạp.
        is_free[u] = false;

        // Duyệt các đỉnh v kề u và chưa được kết nạp vào cây.
        // Tối ưu các khoảng cách d[v] bằng trọng số cạnh (u, v).
        for (int v = 1; v <= n; ++v)
            if (is_free[v] && d[v] > weight[u][v])
            {
                // Cập nhật lại d[v] nhỏ nhất, đồng thời lưu vết đỉnh 
                // nối với v tạo khoảng cách ngắn nhất tới cây T là u.
                d[v] = weight[u][v];
                trace[v] = u;
            }
    }

    // Truy vết và in ra cây khung tìm được.
    long long mst_weight = 0;
    vector < pair < int, int > > mst_edges;
    for (int v = 2; v <= n; ++v)
    {
        mst_edges.push_back({trace[v], v});
        mst_weight += weight[trace[v]][v];
    }

    cout << mst_weight << endl;
    for (auto e: mst_edges)
        cout << e.first << ' ' << e.second << ' ' << weight[e.first][e.second] << endl;
}

main()
{
    int n, m;
    vector < vector < int > > weight;

    enter(n, m, weight);
    basic_prim(n, m, weight);

    return 0;
}

Ngôn ngữ Python:

INFTY = 2 * (10 ** 6)


def basic_prim(n, m, weight):
    d = [INFTY] * (n + 1)
    is_free = [True] * (n + 1)
    trace = [0] * (n + 1)
    is_free[1], d[1] = False, 0

    for i in range(n):
        # Tìm đỉnh u chưa bị kết nạp vào cây khung có d[u] nhỏ nhất.
        u = 0, flag = INFTY
        for v in range(1, n + 1):
            if is_free[v] and flag > d[v]:
                flag = d[v]
                u = v

        # Nếu không tìm được u thì đồ thị không liên thông, việc tìm
        # cây khung thất bại và ta dừng thuật toán tại đây.
        if u == 0:
            print('Unconnected Graph')
            return

        # Kết nạp u vào cây khung nếu tìm thấy u, đánh dấu nó đã kết nạp.
        is_free[u] = False

        # Duyệt các đỉnh v kề u và chưa được kết nạp vào cây.
        # Tối ưu các khoảng cách d[v] bằng trọng số cạnh (u, v).
        for v in range(1, n + 1):
            if is_free[v] and d[v] > weight[u][v]:
                # Cập nhật lại d[v] nhỏ nhất, đồng thời lưu vết đỉnh 
                # nối với v tạo khoảng cách ngắn nhất tới cây T là u.
                d[v] = weight[u][v]
                trace[v] = u

    # Truy vết và in ra cây khung tìm được.
    mst_weight = 0
    mst_edges = []
    for v in range(2, n + 1):
        mst_edges.append((trace[v], v, weight[trace[v]][v]))
        mst_weight += weight[trace[v]][v]

    print(mst_weight)
    for (u, v, c) in mst_edges:
        print(u, v, c)


if __name__ == '__main__':
    # Nhập đồ thị, lưu trọng số các cạnh bằng một ma trận kề.
    # Cách làm phù hợp với đồ thị có số đỉnh khoảng 5000 trở xuống.
    n, m = map(int, input().split())

    weight = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, n + 1):
        for j in range(1, n + 1):
            weight[u][v] = 0 if u == v else INFTY

    for i in range(m):
        u, v, c = map(int, input().split())
        weight[u][v] = weight[v][u] = c

    basic_prim(n, m, weight)

Cải tiến bằng hàng đợi ưu tiên

Ngôn ngữ C++:

#include <bits/stdc++.h>

using namespace std;

// Định danh lại kiểu pair < int, int > để viết cho ngắn gọn.
typedef pair < int, int > II;

const MAX_WEIGHT = 2e6;

// Nhập dữ liệu đồ thị, sử dụng danh sách kề để cải tiến thuật toán.
// Cách làm phù hợp với đồ thị có số đỉnh khoảng 10^6.
void enter(int &n, int &m, vector < vector < II > > &adj)
{
    cin >> n >> m;

    // Danh sách kề adj[u]: Lưu các đỉnh kề của u kèm theo trọng số cạnh.
    adj.resize(n + 1);
    for (int i = 1; i <= m; ++i)
    {
        int u, v, c;
        cin >> u >> v >> c;

        adj[u].push_back({v, c});
        adj[v].push_back({u, c});
    }
}

void prim_heap(int n, int m, vector < vector < II > > &adj)
{
    // Hàng đợi ưu tiên lưu các cặp giá trị (d[u], u). 
    // Cặp nào có d[u] nhỏ nhất tự động được đẩy lên top của hàng đợi.
    priority_queue < II, vector < II >, greater < II > > qu_min;
    vector < int > d(n + 1, MAX_WEIGHT);
    vector < bool > is_free(n + 1, true);
    vector < II > trace(n + 1);
    d[1] = 0;
    is_free[1] = false;
    qu_min.push({d[1], 1});

    int mst_vertexes = 0;
    while (!qu_min.empty())
    {
        int cur_dis = qu_min.top().first;
        int u = qu_min.top().second();
        qu_min.pop();

        // Đỉnh u đã được kết nạp vào cây khung rồi thì không sử dụng lại
        // nhãn d[u] nữa, bỏ qua nó luôn.
        if (d[u] != cur_dis)
            continue;

        // Kết nạp u vào cây khung và tăng số đỉnh của cây khung lên 1.
        is_free[u] = false;
        ++mst_vertexes;

        // Tối ưu nhãn d[v] của các đỉnh v kề với u, đỉnh nào tối ưu được
        // thì đưa nó vào trong hàng đợi ưu tiên và lưu vết luôn. Tuy nhiên,
        // khi lưu vết cần lưu cả đỉnh nối với v trên cây và trọng số cạnh nối.
        for (auto e: adj[u])
        {
            int v = e.first, w = e.second;
            if (is_free[v] && d[v] > w)
            {
                d[v] = w;
                trace[v] = {u, w};
                qu_min.push({d[v], v});
            }
        }
    }

    // Nếu cây T không có đủ n đỉnh thì đồ thị không liên thông, việc
    // tìm cây khung thất bại.
    if (mst_vertexes < n)
    {
        cout << "Unconnected Graph";
        return;
    }

    // Truy vết và in ra cây khung tìm được.
    long long mst_weight = 0;
    vector < pair < II , int > > mst_edges;
    for (int v = 2; v <= n; ++v)
    {
        mst_edges.push_back({{trace[v].first, v}, trace[v].second});
        mst_weight += trace[v].second;
    }

    cout << mst_weight << endl;
    for (auto e: mst_edges)
        cout << e.first.first << ' ' << e.first.second << ' ' << e.second << endl; 
}

main()
{
    int n, m;
    vector < vector < int > > adj;

    enter(n, m, adj);
    prim_heap(n, m, adj);

    return 0;
}

Ngôn ngữ Python:

from queue import PriorityQueue


def prim_heap(n, m, adj):
    # Hàng đợi ưu tiên lưu các cặp giá trị (d[u], u). 
    # Cặp nào có d[u] nhỏ nhất tự động được đẩy lên top của hàng đợi.
    qu_min = PriorityQueue()
    

if __name__ == '__main__':
    # Nhập dữ liệu đồ thị, sử dụng danh sách kề để cải tiến thuật toán.
    # Cách làm phù hợp với đồ thị có số đỉnh khoảng 10^6.
    n, m = map(int, input().split())

    adj = [[] for _ in range(n + 1)]
    for i in range(m):
        u, v, c = map(int, input().split())
        adj[u].append((v, c))
        adj[v].append((u, c))

    prim_heap(n, m, adj)

IV. Bài toán minh họa

1. Ô tô điện

Đề bài

Hiện nay, nhiều hãng xe đang phát triển xe ô tô chạy năng lượng điện thay vì chạy bằng xăng, dầu. Tuy nhiên, ắc quy cấp điện dùng cho những mẫu xe điện này còn rất nặng nề và tốn kém, vì vậy các nhà thiết kế luôn phải xác định trước được dung lượng ắc quy và phạm vi di chuyển tối đa của chiếc xe này.

Mạng lưới giao thông đường bộ gồm $n$ thành phố (các thành phố đánh số từ $0$ tới $n-1$ ) được nối với nhau bằng $m$ con đường hai chiều. Mỗi thành phố có một trạm nạp điện cho ắc quy xe. Dọc theo tuyến đường giữa hai thành phố, chiếc xe có thể đi qua một số các thành phố tùy ý khác, nhưng khoảng cách giữa các cặp thành phố liên tiếp dọc theo tuyến đường không được dài hơn phạm vi di chuyển quy định của chiếc xe.

Hãy xác định phạm vi di chuyển tối thiểu mà chiếc xe cần đáp ứng (quãng đường tối thiểu mà xe di chuyển được từ lúc nạp điện tới lúc hết điện) để chiếc xe có thể đi lại giữa hai thành phố bất kỳ mà không bị hết điện trước khi tới được một trạm nạp điện?

Input:

Gồm nhiều bộ dữ liệu, mỗi bộ dữ liệu gồm:
- Dòng đầu tiên chứa hai số nguyên dương $n$ và $m$ – số lượng thành phố và số tuyến đường giao thông.
- $m$ dòng tiếp theo, mỗi dòng chứa ba số nguyên không âm $u,v,w$ – cho biết có con đường hai chiều nối giữa thành phố $u$ và thành phố $v$ với khoảng cách là $w$ .
Kết thúc của file dữ liệu là một dòng gồm hai chữ số $0,$ cho biết đã kết thúc dữ liệu vào (không cần xử lý).

Ràng buộc:

$1 \le n, m \le 10^6$ .
$0 \le u \ne v < n$ .
$0 \le w \le 10^6$ .

Output:

Ứng với mỗi bộ dữ liệu, in ra một số nguyên là phạm vi di chuyển tối thiểu chiếc xe cần đáp ứng để nó có thể di chuyển qua lại giữa hai thành phố bất kỳ. Nếu không thể tìm được đáp số thì đưa ra thông báo IMPOSSIBLE.

Sample Input:

Sample Output:

4
IMPOSSIBLE

Ý tưởng

Đề bài có thể phát biểu lại thành: Tìm một hành trình để xe điện đi qua mọi địa điểm, sao cho khoảng cách lớn nhất giữa hai địa điểm liên tiếp là bé nhất.

Vậy ý tưởng là tìm cây khung nhỏ nhất của đồ thị, cạnh cuối cùng được kết nạp vào cây khung sẽ là kết quả. Các bạn có thể sử dụng giải thuật Kruskal hoặc Prim đều được. Solution mẫu sẽ sử dụng giải thuật Kruskal.

Độ phức tạp: $O\big(n \times \log(n)\big)$ .

Cài đặt

Ngôn ngữ C++:

#include <bits/stdc++.h>

using namespace std;

struct Edge
{
    int u, v, w;
};

int find_root(int u, vector < int > &lab)
{
    return (lab[u] < 0) ? u : lab[u] = find_root(lab[u], lab);
}

void union_trees(int r1, int r2, vector < int > &lab)
{
    int child_r1 = -lab[r1], child_r2 = -lab[r2];

    if (child_r1 < child_r2)
        swap(r1, r2);

    lab[r1] += lab[r2];
    lab[r2] = r1;
}

bool cmp(Edge a, Edge b)
{
    return a.w < b.w;
}

void kruskal(int n, int m, vector < Edge > &edges)
{
    vector < int > &lab(n + 1, -1);
    sort(edges.begin(), edges.end(), cmp);

    int minimum_range = 0, mst_edges = 0;
    for (int i = 0; i < m; ++i)
    {
        int r1 = find_root(edges[i].u), r2 = find_root(edges[i].v);

        if (r1 != r2)
        {
            union_trees(r1, r2, lab);

            minimum_range = edges[i].w;
            ++mst_edges;
        }

        if (mst_edges == n - 1)
            break;
    }

    if (mst_edges != n - 1)
        cout << "IMPOSSIBLE" << endl;
    else 
        cout << minimum_range << endl;
}

main()
{
    while (true)
    {
        int n, m;
        cin >> n >> m;

        if (n == 0 && m == 0)
            break;
        
        vector < Edge > edges;
        
        edges.resize(m);
        for (int i = 0; i < m; ++i)
            cin >> edges[i].u >> edges[i].v >> edges[i].w;

        kruskal(n, m, edges);
    }
}

Ngôn ngữ Python:

def find_root(u, lab):
    if lab[u] < 0:
        return u
    else:
        lab[u] = find_root(lab[u], lab)
        return lab[u]


def union_trees(r1, r2, lab):
    child_r1, child_r2 = -lab[r1], -lab[r2]

    if child_r1 < child_r2:
        r1, r2 = r2, r1

    lab[r1] += lab[r2]
    lab[r2] = r1


def take_weight(element):
    return element[2]


def kruskal(n, m, edges):
    lab = [-1] * (n + 1)
    edges = sorted(edges, key=take_weight)

    minimum_range, mst_edges = 0, 0
    for i in range(m):
        r1, r2 = find_root(edges[i][0], lab), find_root(edges[i][1], lab)

        # Thêm cạnh (u, v) vào đồ thị nếu cạnh này không tạo ra chu trình đơn.
        # Hợp nhất hai cây chứa hai đỉnh u và v.
        if r1 != r2:
            union_trees(r1, r2, lab)
            
            minimum_range = edges[i][2]
            mst_edges += 1
        
        if mst_edges == n - 1:
            break

    if mst_edges != n - 1:
        print('IMPOSSIBLE')
    else:
        print(mst_edges)


if __name__ == '__main__':
    while True:
        n, m = map(int, input().split())

        if n == 0 and m == 0:
            break

        edges = []
        for _ in range(m):
            u, v, c = map(int, input().split())
            edges.append((u, v, c))

        kruskal(n, m, edges)

2. Động viên đàn bò

Đề bài

Một trang trại gồm $n$ cánh đồng và $m$ con đường nối hai chiều giữa một số cặp cánh đồng, mỗi cánh đồng là nơi ở của một chú bò. Do đã già nua nên chủ trang trại rất mệt mỏi với việc phải đi lại trên quá nhiều con đường, vì vậy bác ta quyết định loại bỏ một số con đường, sao cho các cánh đồng vẫn liên thông với nhau.

Biết được thông tin này, đàn bò rất buồn bã. Người con trai của chủ trang trại sẽ phải thay bố mình đi thăm mỗi chú bò ít nhất một lần trong ngày để động viên chúng. Mỗi lần đi qua cánh đồng $i,$ anh phải trò chuyện với chú bò ở đó trong thời gian $c_i$ để giúp chú bò phấn chấn trở lại (dù chỉ là đi ngang qua cánh đồng đó).

Để thuận tiện cho công việc vào sáng hôm sau, người con trai quyết định sẽ chọn một cánh đồng nào đó để xuất phát từ đó, đi thăm tất cả các chú bò và quay trở lại cánh đồng đó để nghỉ đêm. Dĩ nhiên, khi quay trở về vào buổi tối, anh ta sẽ lại trò chuyện với chú bò ở cánh đồng mình nghỉ đêm thêm một lần nữa.

Hãy xác định tổng thời gian nhỏ nhất mà người con trai cần để đi thăm tất cả đàn bò trong một ngày?

Input:

Dòng đầu tiên chứa hai số nguyên dương $n$ và $m$ – số lượng cánh đồng và số đường đi giữa chúng.
$n$ dòng tiếp theo, dòng thứ $i$ chứa số nguyên dương $c_i$ – thời gian cần trò chuyện với chú bò ở cánh đồng $i$ .
$m$ dòng cuối cùng, mỗi dòng ghi ba số nguyên dương $u,v,t$ – thể hiện con đường hai chiều nối giữa cánh đồng $u$ và cánh đồng $v$ cần thời gian $t$ để di chuyển. Không có hai cánh đồng nào được nối bởi nhiều hơn $1$ con đường.

Ràng buộc:

$1≤n≤10^4$ .
$1≤m≤10^5$ .
$1≤c_i≤10^3; \forall i: 1 \le i \le n$ .
$1 \le t \le 10^3$ .

Output:

Một số nguyên duy nhất là tổng thời gian tối thiểu để đi thăm tất cả đàn bò trong một ngày.

Sample Input:

Sample Output:

Ý tưởng

Nhận xét: Đề bài có thể tóm tắt lại thành: Tìm một hành trình gồm $(n - 1)$ cạnh, xuất phát từ $1$ đỉnh bất kỳ đi qua tất cả các đỉnh còn lại và quay trở về đỉnh xuất phát. Như vậy bài toán trở thành tìm cây khung nhỏ nhất, tuy nhiên trọng số cạnh sẽ được xử lý lại.

Xét cạnh $(u, v)$ : Nếu đi qua cạnh này, thì sẽ tốn tổng thời gian là $2 \times w(u, v) + c_u + c_v,$ bao gồm thời gian đi và về cộng với thời gian nói chuyện cùng chú bò ở cánh đồng $u$ và cánh đồng $v$ . Ta tạo lại trọng số cho các cạnh theo công thức trên, sau đó tìm cây khung nhỏ nhất trên đồ thị.

Cuối cùng, chọn đỉnh xuất phát $s$ có $c_s$ nhỏ nhất và cộng thêm $c_s$ vào kết quả, do cánh đồng xuất phát sẽ trở về thêm một lần nữa. Thực tế điều này có được từ việc tính tổng mọi đường đi trên cây tạo thành (mỗi đường đi bằng các cạnh + số ở các đỉnh) sau đó nhân với $2$ và cộng thêm đỉnh gốc có giá trị $c$ nhỏ nhất.

Độ phức tạp: $O\big(m \times \log(m)\big)$ .

Cài đặt

Ngôn ngữ C++:

#include <bits/stdc++.h>

using namespace std;

struct Edge
{
    int u, v, w;
};

void enter(int &n, int &m, vector < int > &c, vector < Edge > &edges)
{
    cin >> n >> m;

    c.resize(n + 1);
    for (int i = 1; i <= n; ++i)
        cin >> c[i];

    edges.resize(m);
    for (int i = 0; i < m; ++i)
    {
        cin >> edges[i].u >> edges[i].v >> edges[i].w;
        edges[i].w = 2 * edges[i].w + c[edges[i].u] + c[edges[i].v];
}

int find_root(int u, vector < int > &lab)
{
    return (lab[u] < 0) ? u : lab[u] = find_root(lab[u], lab);
}

void union_trees(int r1, int r2, vector < int > &lab)
{
    int child_r1 = -lab[r1], child_r2 = -lab[r2];

    if (child_r1 < child_r2)
        swap(r1, r2);

    lab[r1] += lab[r2];
    lab[r2] = r1;
}

bool cmp(Edge a, Edge b)
{
    return a.w < b.w;
}

void kruskal(int n, int m, vector < int > &c, vector < Edge > &edges)
{
    vector < int > lab(n + 1, -1);
    sort(edges.begin(), edges.end(), cmp);

    int res = *min_element(c.begin() + 1, c.end());
    int mst_edges = 0;
    for (int i = 0; i < m; ++i)
    {
        int r1 = find_root(edges[i].u), r2 = find_root(edges[i].v);

        if (r1 != r2)
        {
            union_trees(r1, r2, lab);

            res += edges[i].w;
            ++mst_edges;
        }

        if (mst_edges == n - 1)
            break;
    }

    cout << mst_edges;
}

main()
{
    int n, m;
    vector < int > c;
    vector < Edge > edges;

    enter(n, m, edges);
    kruskal(n, m, edges);

    return 0;
}

Ngôn ngữ Python:

def find_root(u, lab):
    if lab[u] < 0:
        return u
    else:
        lab[u] = find_root(lab[u], lab)
        return lab[u]


def union_trees(r1, r2, lab):
    child_r1, child_r2 = -lab[r1], -lab[r2]

    if child_r1 < child_r2:
        r1, r2 = r2, r1

    lab[r1] += lab[r2]
    lab[r2] = r1


def take_weight(element):
    return element[2]


def kruskal(n, m, c, edges):
    lab = [-1] * (n + 1)
    edges = sorted(edges, key=take_weight)

    res = min(c)
    mst_edges = 0
    for i in range(m):
        r1, r2 = find_root(edges[i][0], lab), find_root(edges[i][1], lab)

        if r1 != r2:
            union_trees(r1, r2, lab)
            
            res += edges[i][2]
            mst_edges += 1
        
        if mst_edges == n - 1:
            break

    print(res)


if __name__ == '__main__':
    n, m = map(int, input().split())

    c = [0] + [int(x) for x in input().split()]

    edges = []
    for _ in range(m):
        u, v, w = map(int, input().split())
        edges.append((u, v, w))

    kruskal(n, m, c, edges)

Các bạn có thể tham khảo thêm bài tập tự luyện tại <i>đây.</i>

V. Tài liệu tham khảo

Algorithm

I. Giới thiệu chung

1. Cây khung của đồ thị (Spanning Trees)

2. Cây khung nhỏ nhất (Minimum Spanning Tree)

3. Bài toán tìm cây khung nhỏ nhất

II. Giải thuật Kruskal (Joseph Kruskal - 1956)

1. Ý tưởng

2. Cài đặt

III. Giải thuật Prim (Robert Prim - 1957)

1. Ý tưởng

3. Cài đặt

Cài đặt cơ bản không sử dụng Heap

Cải tiến bằng hàng đợi ưu tiên

IV. Bài toán minh họa

1. Ô tô điện

Đề bài

Ý tưởng

Cài đặt

2. Động viên đàn bò

Đề bài

Ý tưởng

Cài đặt

V. Tài liệu tham khảo

Mục lục