无向图最小生成树 普里姆算法和克鲁斯卡尔算法

无向图最小生成树（Minimum Spanning Tree, MST）是指在一个无向图中，选取一些边，使得这些边连接的所有顶点构成一棵树，并且这棵树覆盖所有顶点，同时边的总权重尽可能小。在图论中有两种主要的算法用于求解最小生成树：普里姆算法（Prim's Algorithm）和克鲁斯卡尔算法（Kruskal's Algorithm）。

1. **普里姆算法**：
- 这是一种贪心算法，从任意一个顶点开始，每次添加一条与当前生成树中所有顶点相连且权重最小的新边，直到所有顶点都被包含。
- 操作过程是逐步构建树，始终保持边的选择是当前未加入树的顶点中距离最近的。
- 直接操作是邻接矩阵或邻接表，方便查找最短边。

2. **克鲁斯卡尔算法**：
- 这也是一种贪心策略，但它不是从一个顶点出发，而是从所有的边开始，每次选择一条能形成一棵树且权重最小的新边，直到树包含了所有顶点。
- 克鲁斯卡尔算法通常用并查集数据结构来辅助，因为需要频繁地合并集合。
- 这种算法适合边的数量远大于顶点的数量的情况，因为它不需要维护一个已访问过的集合。

相关问题

最小生成树—普里姆与克鲁斯卡尔

最小生成树是指在一张有权无向图中，生成一棵树，并使得这棵树上所有边的权值之和最小。普里姆和克鲁斯卡尔是两种常用的最小生成树算法。

普里姆算法的思想是从一个点开始，每次选择一个距离该点最近的未选择的点，将这个点与已选择的点形成一条边加入到最小生成树中。具体实现可以用堆来维护未选择的点集合。

克鲁斯卡尔算法的思想是先将所有边按照权值从小到大排序，然后依次将每条边加入到生成树中，但要保证加入后不会形成环，可以用并查集来维护已选择的点集合。

C语言，输入边数、结点数和权重，构建带权无向图的邻接矩阵存储结构，分别用普里姆算法和克鲁斯卡尔算法生成该图的最小生成树

好的，我来回答你的问题。

首先，我们可以使用二维数组来表示邻接矩阵。假设边数为E，结点数为V，则邻接矩阵的大小为V*V。我们可以定义一个如下的结构体来表示一条边：

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

接下来，我们先来看普里姆算法。该算法的基本思想是从一个任意结点开始，逐步加入与当前最小生成树相邻的边，直到生成一棵包含所有结点的最小生成树。具体实现步骤如下：

1. 初始化一个空的最小生成树集合MST和一个空的结点集合visited。
2. 随机选择一个结点v，将其加入visited集合中。
3. 从visited集合中的所有结点出发，找到一条权重最小的边，该边的另一端结点不在visited集合中，将该边加入MST集合中，并将该边的另一端结点加入visited集合中。
4. 重复步骤3，直到visited集合包含所有结点。

下面是普里姆算法的C代码实现：

void primMST(int graph[V][V]) {
    int parent[V]; // 存储最小生成树中每个结点的父结点
    int key[V]; // 存储每个结点到最小生成树的距离
    bool visited[V]; // 标记每个结点是否已加入最小生成树

    // 初始化key数组和visited数组
    for (int i = 0; i < V; i++) {
        key[i] = INT_MAX;
        visited[i] = false;
    }

    // 选择第一个结点作为起点
    key[0] = 0;
    parent[0] = -1;

    for (int i = 0; i < V - 1; i++) {
        // 找到距离最近的结点
        int u = minKey(key, visited);
        visited[u] = true;

        // 更新与u相邻的结点的key值和parent
        for (int v = 0; v < V; v++) {
            if (graph[u][v] && !visited[v] && graph[u][v] < key[v]) {
                parent[v] = u;
                key[v] = graph[u][v];
            }
        }
    }

    // 输出最小生成树
    printMST(parent, graph);
}

其中，minKey函数用于找到距离最近的结点，代码如下：

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

    for (int i = 0; i < V; i++) {
        if (!visited[i] && key[i] < min) {
            min = key[i];
            min_index = i;
        }
    }

    return min_index;
}

最后，我们需要实现一个函数来输出最小生成树。代码如下：

void printMST(int parent[], int graph[V][V]) {
    printf("最小生成树:\n");
    for (int i = 1; i < V; i++) {
        printf("%d - %d: %d\n", parent[i], i, graph[i][parent[i]]);
    }
}

接下来，我们来看克鲁斯卡尔算法。该算法的基本思想是先将所有边按照权重从小到大排序，然后依次加入到最小生成树中，直到生成一棵包含所有结点的最小生成树。具体实现步骤如下：

1. 将所有边按照权重从小到大排序。
2. 初始化一个空的最小生成树集合MST，以及一个空的并查集。
3. 依次从排好序的边中取出一条边，如果该边的两个端点不在同一个连通块中，就将该边加入MST集合中，并将该边的两个端点合并到同一个连通块中。
4. 重复步骤3，直到MST集合包含所有结点。

下面是克鲁斯卡尔算法的C代码实现：

void kruskalMST(struct Edge edges[]) {
    int parent[V]; // 存储最小生成树中每个结点的父结点
    for (int i = 0; i < V; i++) {
        parent[i] = i;
    }

    int e = 0, i = 0;
    struct Edge result[V];

    // 按照边的权重从小到大排序
    qsort(edges, E, sizeof(edges[0]), compare);

    while (e < V - 1 && i < E) {
        // 取出一条边
        struct Edge next_edge = edges[i++];

        // 找到该边的两个端点所在的连通块
        int x = find(parent, next_edge.src);
        int y = find(parent, next_edge.dest);

        // 如果两个端点不在同一个连通块中，将该边加入MST集合中
        if (x != y) {
            result[e++] = next_edge;
            union_(parent, x, y);
        }
    }

    // 输出最小生成树
    printMST(result);
}

其中，find函数用于查找一个结点所在的连通块，代码如下：

int find(int parent[], int i) {
    while (parent[i] != i) {
        i = parent[i];
    }
    return i;
}

union_函数用于合并两个连通块，代码如下：

void union_(int parent[], int x, int y) {
    int xset = find(parent, x);
    int yset = find(parent, y);
    parent[xset] = yset;
}

最后，我们需要实现一个函数来输出最小生成树。代码如下：

void printMST(struct Edge result[]) {
    printf("最小生成树:\n");
    for (int i = 0; i < V - 1; i++) {
        printf("%d - %d: %d\n", result[i].src, result[i].dest, result[i].weight);
    }
}

这样，我们就完成了使用普里姆算法和克鲁斯卡尔算法生成带权无向图的最小生成树的任务。