跳到主要内容

最小生成树、Prim算法、Kruskal算法

概述​

最小生成树（Minimum Spanning Tree, MST）是图论中的一个重要概念，主要用于加权无向图。最小生成树是包含所有顶点的连通子图，边的权重之和最小。最小生成树在网络设计、聚类分析等领域有广泛应用。

视频讲解​

【最小生成树(Kruskal(克鲁斯卡尔)和Prim(普里姆))算法动画演示】

基本概念​

  • 无向图（Undirected Graph）：图中的边没有方向。
  • 加权图（Weighted Graph）：图中的每条边都有一个权重（成本）。
  • 生成树（Spanning Tree）：包含图中所有顶点的连通子图，但没有环。
  • 最小生成树（Minimum Spanning Tree）：生成树中所有边的权重之和最小。

最小生成树示例​

首先，这是原始图：

graph TD;
    A((A)) ---|2| B((B));
    A ---|3| C((C));
    A ---|1| D((D));
    B ---|4| C;
    B ---|2| E((E));
    C ---|5| E;
    D ---|3| E;

在这个图中，节点A、B、C、D、E是顶点，连线上的数字代表边的权重。

然后，这是原始图的最小生成树：

graph TD;
    A((A)) ---|1| D((D));
    A ---|2| B((B));
    B ---|2| E((E));
    A ---|3| C((C));

在这个最小生成树中，已经包含了所有的顶点，并且总权重最小。

解释：​

  • 原始图：图中的每个顶点通过不同权重的边相互连接。
  • 最小生成树：从原始图中选出一些边，使得所有顶点都相连，且这些边的权重之和最小。

通过这个图，可以更加形象地理解最小生成树的概念，即如何在保证所有顶点连通的前提下，选择权重最小的边进行连接。

常用算法​

Prim算法、Kruskal算法都属于贪心算法哦

Prim算法​

Prim算法是一种逐步扩展的贪心算法，初始时从一个顶点开始，然后逐步添加最小权重的边，直到所有顶点都包含在树中。

步骤：

  1. 选择一个起始顶点，将其加入最小生成树。
  2. 重复以下步骤，直到最小生成树包含所有顶点：
    • 在所有连接已包含顶点和未包含顶点的边中，选择权重最小的边。（这里是未链接的顶点链接到已链接的顶点的集合的权重最小的边，这里不是连接到起始顶点的边权重（这里与dijiesitela算法区分））
    • 将该边和相应的顶点加入最小生成树。
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

#define V 5

// 在所有连接已包含顶点和未包含顶点的边中，选择权重最小的边
//这里通过更新与加入已包含顶点的集合顶点所相连的边来寻找在所有连接已包含顶点和未包含顶点的边
int minKey(int key[], int mstSet[]) {
    int min = INT_MAX, min_index;
    for (int v = 0; v < V; v++)
        if (mstSet[v] == 0 && key[v] < min)
            min = key[v], min_index = v;
    return min_index;
}


//打印
void printMST(int parent[], int graph[V][V]) {
    printf("Edge \tWeight\n");
    for (int i = 1; i < V; i++)
        printf("%d - %d \t%d \n", parent[i], i, graph[i][parent[i]]);
}

void primMST(int graph[V][V]) {

    //graph[V][V]保存边的权重值
    
    int parent[V]; //前驱节点
    int key[V]; //当前连接到最小生成树集合的权重
    int mstSet[V]; //是否已经加入最小生成树集合

    //初始化
    for (int i = 0; i < V; i++)
        key[i] = INT_MAX, mstSet[i] = 0;

    key[0] = 0;
    parent[0] = -1;
    
    //Prim
    for (int count = 0; count < V - 1; count++) {
        //寻找连接权重最小的边的点
        int u = minKey(key, mstSet);
        
        //加入到最小生成树集合
        mstSet[u] = 1;
        
        //更新与刚加入的点相连的点
        for (int v = 0; v < V; v++)
            if (graph[u][v] && mstSet[v] == 0 && graph[u][v] < key[v])
                parent[v] = u, key[v] = graph[u][v];
    }

    printMST(parent, graph);
}

int main() {
    int graph[V][V] = {{0, 2, 0, 6, 0},
                       {2, 0, 3, 8, 5},
                       {0, 3, 0, 0, 7},
                       {6, 8, 0, 0, 9},
                       {0, 5, 7, 9, 0}};
    primMST(graph);
    return 0;
}

Kruskal算法​

Kruskal算法是一种基于边的贪心算法，初始时所有顶点都是独立的集合，然后按照边的权重从小到大排序，逐步选择权重最小且不形成环的边，直到树包含所有顶点。

步骤：

  1. 将所有边按权重升序排序。
  2. 依次选择权重最小的边，若该边连接的两个顶点不在同一集合，则将该边加入最小生成树，并合并两个顶点的集合。
  3. 重复以上步骤，直到最小生成树包含所有顶点。
#include <stdio.h>
#include <stdlib.h>

#define V 5
#define E 7

struct Edge {
    int src, dest, weight;
};

struct Graph {
    int V, E;
    struct Edge* edge;
};

struct Graph* createGraph(int V, int E) {
    struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph));
    graph->V = V;
    graph->E = E;
    graph->edge = (struct Edge*)malloc(graph->E * sizeof(struct Edge));
    return graph;
}

struct subset {
    int parent;
    int rank;
};

int find(struct subset subsets[], int i) {
    if (subsets[i].parent != i)
        subsets[i].parent = find(subsets, subsets[i].parent);
    return subsets[i].parent;
}

void Union(struct subset subsets[], int x, int y) {
    int xroot = find(subsets, x);
    int yroot = find(subsets, y);

    if (subsets[xroot].rank < subsets[yroot].rank)
        subsets[xroot].parent = yroot;
    else if (subsets[xroot].rank > subsets[yroot].rank)
        subsets[yroot].parent = xroot;
    else {
        subsets[yroot].parent = xroot;
        subsets[xroot].rank++;
    }
}

int compareEdges(const void* a, const void* b) {
    struct Edge* a1 = (struct Edge*)a;
    struct Edge* b1 = (struct Edge*)b;
    return a1->weight > b1->weight;
}

void KruskalMST(struct Graph* graph) {
    int V = graph->V;
    struct Edge result[V];
    int e = 0;
    int i = 0;

    qsort(graph->edge, graph->E, sizeof(graph->edge[0]), compareEdges);

    struct subset* subsets = (struct subset*)malloc(V * sizeof(struct subset));

    for (int v = 0; v < V; ++v) {
        subsets[v].parent = v;
        subsets[v].rank = 0;
    }

    while (e < V - 1 && i < graph->E) {
        struct Edge next_edge = graph->edge[i++];

        int x = find(subsets, next_edge.src);
        int y = find(subsets, next_edge.dest);

        if (x != y) {
            result[e++] = next_edge;
            Union(subsets, x, y);
        }
    }

    printf("Following are the edges in the constructed MST\n");
    for (i = 0; i < e; ++i)
        printf("%d -- %d == %d\n", result[i].src, result[i].dest, result[i].weight);
}

int main() {
    int V = 4;
    int E = 5;
    struct Graph* graph = createGraph(V, E);

    graph->edge[0].src = 0;
    graph->edge[0].dest = 1;
    graph->edge[0].weight = 10;

    graph->edge[1].src = 0;
    graph->edge[1].dest = 2;
    graph->edge[1].weight = 6;

    graph->edge[2].src = 0;
    graph->edge[2].dest = 3;
    graph->edge[2].weight = 5;

    graph->edge[3].src = 1;
    graph->edge[3].dest = 3;
    graph->edge[3].weight = 15;

    graph->edge[4].src = 2;
    graph->edge[4].dest = 3;
    graph->edge[4].weight = 4;

    KruskalMST(graph);

    return 0;
}

应用场景​

  1. 网络设计：如电缆、电话线等连接设计，最小生成树可以帮助找到最低成本的连接方式。
  2. 聚类分析：在数据挖掘中，最小生成树可用于聚类分析，发现数据的自然簇。
  3. 交通网络：规划公路、铁路等，使总的建设成本最小。

总结​

最小生成树是图论中的重要问题，通过Prim和Kruskal算法可以高效地解决。上文详细介绍了其概念、算法步骤及C语言实现代码，便于理解和应用。

贪心算法​

简介​

贪心算法是一种通过每一步选择最优解来求解全局最优解的算法。该算法通常用于解决优化问题，例如最短路径、最小生成树、活动选择问题等。

应用场景​

贪心算法适用于以下几类问题：

  • 最短路径问题：例如Dijkstra算法。
  • 最小生成树问题：例如Prim算法和Kruskal算法。
  • 活动选择问题：选择最大数量的互不重叠活动。
  • 找零问题：用最少数量的硬币找零。

贪心算法的步骤​

贪心算法的一般步骤如下：

  1. 选择初始状态：根据问题的描述选择一个初始状态。
  2. 求解局部最优解：在当前状态下选择一个最优解。
  3. 更新状态：根据选择的最优解更新当前状态。
  4. 重复：重复步骤2和3，直到达到终止条件。

贪心算法的示例代码​

示例：找零问题​

给定不同面值的硬币和一个总金额，找出最少数量的硬币组合。

#include <stdio.h>

void findMinCoins(int coins[], int n, int amount) {
    int result[n];
    for (int i = 0; i < n; i++) {
        result[i] = 0;
    }

    for (int i = 0; i < n; i++) {
        while (amount >= coins[i]) {
            amount -= coins[i];
            result[i]++;
        }
    }

    printf("找零的硬币组合为：\n");
    for (int i = 0; i < n; i++) {
        if (result[i] != 0) {
            printf("%d 个 %d 面值的硬币\n", result[i], coins[i]);
        }
    }
}

int main() {
    int coins[] = {25, 10, 5, 1};
    int n = sizeof(coins) / sizeof(coins[0]);
    int amount = 63;

    findMinCoins(coins, n, amount);
    return 0;
}

贪心算法的优缺点​

优点​

  • 简单易懂：贪心算法通常比较直观，容易理解和实现。
  • 效率高：在适合的场景下，贪心算法的时间复杂度较低，能够快速找到问题的解。

缺点​

  • 局限性：贪心算法并不适用于所有问题，只有在满足贪心选择性质和最优子结构性质的问题上才能保证得到全局最优解。
  • 局部最优并非全局最优：在某些情况下，贪心算法找到的解可能只是局部最优解，而不是全局最优解。