日本aaaaa片特黄aaaa,日韩熟女精品一区二区三区

1.1 連通圖與生成樹

一個連通圖是指在無向圖中，任意兩個頂點之間都有路徑相通。生成樹則是該連通圖的一個極小連通子圖，包含所有頂點且無環(huán)路。最小生成樹是指生成樹中所有邊的權(quán)重之和最小的那一棵。

1.2 生成樹的性質(zhì)

一個連通圖可以有多個生成樹，每個生成樹包含相同的頂點個數(shù)和邊數(shù)。生成樹中沒有環(huán)，但移除任何一條邊會導(dǎo)致圖不連通。對于包含 n 個頂點的連通圖，生成樹包含 n 個頂點和 n-1 條邊。

2. Kruskal算法詳解

Kruskal算法是最小生成樹的一種經(jīng)典算法，其基本思想是將所有邊按權(quán)重從小到大排序，然后依次選擇權(quán)重最小且不形成環(huán)的邊加入生成樹，直到生成樹包含 n-1 條邊。

Kruskal算法示意圖

2.1 Kruskal算法步驟

將圖中的所有邊按權(quán)重從小到大排序。
初始化 n 個頂點為 n 棵獨立的樹組成的森林。
依次選擇權(quán)重最小的邊，如果邊的兩個頂點屬于不同的樹，則將這兩個樹合并。
重復(fù)第3步，直到所有頂點都在同一顆樹內(nèi)，或者有 n-1 條邊。

2.2 Kruskal算法的實現(xiàn)

#include 
#include 
#include 
using namespace std;

struct Edge {
    int u, v, weight;
    bool operator<(const Edge& e) const {
        return weight < e.weight;
    }
};

int findParent(int v, vector& parent) {
    if (parent[v] != v)
        parent[v] = findParent(parent[v], parent);
    return parent[v];
}

void kruskal(int vertexCount, vector& edges) {
    sort(edges.begin(), edges.end());
    vector parent(vertexCount);
    vector mst;
    for (int i = 0; i < vertexCount; ++i)
        parent[i] = i;

    for (const Edge& edge : edges) {
        int uParent = findParent(edge.u, parent);
        int vParent = findParent(edge.v, parent);
        if (uParent != vParent) {
            mst.push_back(edge);
            parent[uParent] = vParent;
        }
    }

    for (const Edge& edge : mst)
        cout << edge.u << " - " << edge.v << " : " << edge.weight << endl;
}

3. Prim算法詳解

Prim算法是另一種求最小生成樹的方法，與Kruskal算法不同，Prim算法是從一個頂點開始，逐漸擴展生成樹，直到覆蓋所有頂點。

Prim算法示意圖

3.1 Prim算法步驟

從任意一個頂點開始，加入生成樹。
在生成樹和集合中，選擇一條代價最小的邊，將相關(guān)頂點加入生成樹。
重復(fù)第2步，直到生成樹包含 n 個頂點。

3.2 Prim算法的實現(xiàn)

#include 
#include 
#include 
using namespace std;

#define V 5

int minKey(int key[], bool mstSet[])
{
    int min = INT_MAX, min_index;

    for (int v = 0; v < V; v++)
        if (mstSet[v] == false && key[v] < min)
            min = key[v], min_index = v;

    return min_index;
}

void primMST(int graph[V][V])
{
    int parent[V];
    int key[V];
    bool mstSet[V];

    for (int i = 0; i < V; i++)
        key[i] = INT_MAX, mstSet[i] = false;

    key[0] = 0;
    parent[0] = -1;

    for (int count = 0; count < V - 1; count++) {
        int u = minKey(key, mstSet);

        mstSet[u] = true;

        for (int v = 0; v < V; v++)
            if (graph[u][v] && mstSet[v] == false && graph[u][v] < key[v])
                parent[v] = u, key[v] = graph[u][v];
    }

    for (int i = 1; i < V; i++)
        cout << parent[i] << " - " << i << " n";
}