贪心法求无向图的最小生成树

贪心法求无向图的最小生成树的基本思想是：每次选择一条边权值最小且不会形成环的边加入生成树中，直到生成树中包含了所有的节点。具体实现可以使用Kruskal算法或Prim算法。

Kruskal算法的实现步骤如下：
1. 将所有边按照权值从小到大排序。
2. 依次选择每条边，如果这条边的两个端点不在同一个连通块中，则将这条边加入生成树中，并将这两个端点所在的连通块合并。
3. 重复步骤2，直到生成树中包含了所有的节点。

Prim算法的实现步骤如下：
1. 任选一个节点作为起点，将其加入生成树中。
2. 从与生成树相邻的节点中选择一条权值最小的边，将其加入生成树中。
3. 重复步骤2，直到生成树中包含了所有的节点。

相关问题

C语言写出，用贪心法求解无向图的最小生成树，要求有输入。

在C语言中，我们可以使用Kruskal算法（一种贪心算法），也称为最小生成树算法，来找到无向图的最小生成树。这个算法的基本思想是每次选择当前图中最短的边，直到所有顶点都连接在一起形成一棵树。以下是简单的C语言代码实现：

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <time.h>

#define V 9 // 图的顶点数

// 边的结构体表示
typedef struct {
    int u, v; // 邻接点
    int weight; // 权重
} Edge;

// 比较两个边的权重
bool compareEdges(Edge e1, Edge e2) {
    return e1.weight < e2.weight;
}

// 使用优先队列存放边
struct MinHeap {
    Edge* heap[V];
    int size;
};

// 插入元素到堆中
void insertMinHeap(struct MinHeap* minHeap, Edge new_edge) {
    minHeap->heap[minHeap->size++] = new_edge;
    // 保持堆的性质
    bubbleUp(minHeap, minHeap->size - 1);
}

// 将节点i下沉至其子节点满足堆的性质
void bubbleUp(struct MinHeap* minHeap, int i) {
    while (i > 0 && minHeap->heap[parent(i)].weight > minHeap->heap[i].weight) {
        swap(minHeap->heap[i], minHeap->heap[parent(i)]);
        i = parent(i);
    }
}

// 找出堆顶元素并删除它
Edge extractMin(struct MinHeap* minHeap) {
    if (minHeap->size == 0)
        return {-1, -1, 0}; // 空堆

    Edge smallest = minHeap->heap[0];
    minHeap->heap[0] = minHeap->heap[--minHeap->size]; // 移动最后一个元素到堆顶
    bubbleDown(minHeap, 0); // 保持堆的性质

    return smallest;
}

// 主函数实现Kruskal算法
int kruskalMST(int graph[V][V], int vertices) {
    struct MinHeap minHeap;
    for (int i = 0; i < vertices; ++i)
        minHeap.heap[i] = {i, -1, graph[i][i]}; // 初始化每个节点为孤立状态

    int edges_count = 0;
    bool edge_used[V * V] = {false}; // 标记已使用的边

    while (edges_count < vertices - 1) {
        Edge currentEdge = extractMin(&minHeap);

        // 如果这条边已经在最小生成树中，则跳过
        if (currentEdge.u != -1 && !edge_used[currentEdge.u * V + currentEdge.v]) {
            insertEdgeIntoUnion(currentEdge.u, currentEdge.v); // 合并边所连接的集合
            edge_used[currentEdge.u * V + currentEdge.v] = true;
            edges_count++;
        }
    }

    printf("Minimum spanning tree edges (Weight, Node1, Node2):\n");
    for (int i = 0; i < vertices; ++i) {
        if (graph[i][i] != 0) {
            printf("%d %d %d\n", graph[i][i], i, find(i));
        }
    }

    return edges_count;
}

// 查找给定节点属于哪棵树
int find(int node) {
    return node; // 无环的情况下，根节点就是自身
    // 如果需要考虑连通分量，可以使用更复杂的数据结构如邻接矩阵或数组
}

// 添加一条边到并查集
void insertEdgeIntoUnion(int u, int v) {
    u = root(u); // 转换为根节点
    v = root(v); // 转换为根节点

    if (u != v) {
        // 将较小的集合合并到较大的集合中
        if (unionSetSize[u] < unionSetSize[v])
            swap(u, v);

        graph[u][v] = graph[v][u] = unionSetSize[u]; // 更新邻接矩阵
        unionSetSize[u] += unionSetSize[v];
    }
}

// 获取节点所在的集合大小
int unionSetSize[V];

// 初始化并查集大小
void initSets() {
    for (int i = 0; i < V; ++i)
        unionSetSize[i] = 1;
}

int main() {
    int graph[V][V] = {{0, 4, 0, 0, 0, 0, 0, 8, 0},
                       {4, 0, 8, 0, 0, 0, 0, 11, 0},
                       {0, 8, 0, 7, 0, 4, 0, 0, 2},
                       {0, 0, 7, 0, 9, 14, 0, 0, 0},
                       {0, 0, 0, 9, 0, 10, 0, 0, 0},
                       {0, 0, 4, 14, 10, 0, 2, 0, 0},
                       {0, 0, 0, 0, 0, 2, 0, 1, 6},
                       {8, 11, 0, 0, 0, 0, 1, 0, 7},
                       {0, 0, 2, 0, 0, 0, 6, 7, 0}};
    initSets();
    int vertices = sizeof(graph) / sizeof(graph[0]);
    kruskalMST(graph, vertices);
    return 0;
}

邻接矩阵无向图prim算法求最小生成树

邻接矩阵无向图 Prim 算法求最小生成树的基本思想是贪心法。该算法以一个节点为起点，每次选择与当前已有节点集合距离最短的节点加入集合，直到所有节点都被加入集合为止。具体实现步骤如下：

1. 选择一个起点，将该起点加入已有节点集合中。

2. 初始化一个与节点数相同的一维数组，用来记录每个节点到已有节点集合的最短距离。将起点到自身的距离设为 0，起点到其他节点的距离设为该节点到起点的距离。

3. 从未加入已有节点集合的节点中，选择距离已有节点集合最近的节点加入集合。

4. 更新该节点到未加入已有节点集合的节点的距离。如果该节点到某个未加入已有节点集合的节点的距离比该节点到已有节点集合的某个节点的距离更短，就更新该未加入节点到已有节点集合的距离为该节点到已有节点集合的距离。

5. 重复 3 和 4 步骤，直到所有节点都被加入已有节点集合为止。

6. 最终已有节点集合中的节点和它们之间的边构成了最小生成树。

注意：邻接矩阵无向图 Prim 算法的时间复杂度为 O(n^2)，其中 n 为节点数。如果使用堆优化可以将时间复杂度优化到 O(mlogn)，其中 m 为边数。