kruscal算法最小生成树

Kruskal算法是一种用于求解最小生成树的贪心算法。它的基本思想是将所有边按照权值从小到大排序，然后依次选择权值最小的边，并将其加入到最小生成树中。在选择过程中，如果该边的两个端点已经在同一棵生成树中，那么就舍弃该边，直到找到 n-1 条边为止。以下是 Kruskal算法的具体步骤：

1. 将所有边按照权值从小到大排序。

2. 依次选择权值最小的边，并判断其两个端点是否在同一棵生成树中。

3. 如果不在同一棵生成树中，则将该边加入到最小生成树中，并将两个端点合并。

4. 重复步骤2和步骤3，直到找到n-1条边为止。

Kruskal算法的时间复杂度为 O(mlogm)，其中m为边的数量。它的空间复杂度为 O(n)，其中n为顶点的数量。

相关问题

编程实现Prim算法和Kruscal求解最小生成树。 输入可以选择给定边集，或者成本邻接矩阵。 输出最小成本，及最小生成树的边集

Prim算法和Kruskal算法都是用于寻找无向图的最小生成树的常用方法：

1. **Prim算法**:
- **输入**：成本邻接矩阵或边集，起始顶点（通常默认为0）
- **步骤**：
- 初始化一个包含起始顶点的集合S，其余顶点在集合V中。
- 初始化一个空的最小生成树MST，初始成本为0。
- 当V非空时，找到V中与S相连且权重最小的边(e, v)，将v加入S并添加这条边到MST，同时更新MST的成本。
- 重复此过程，直到V为空。
- **输出**：MST的成本（总权重）以及包含在MST中的边集合。

2. **Kruskal算法**:
- **输入**：边集，每条边包括两个端点及其成本
- **步骤**：
- 将所有边按成本排序。
- 初始化一个空的最小生成树MST，设置当前总成本为0。
- 遍历排序后的边，检查这条边连接的顶点是否形成了环，如果不形成，则将其加入MST，并增加总成本。
- 重复此过程，直到加进来的边数等于图的顶点数减一。
- **输出**：MST的成本（总权重）以及包含在MST中的边集合。

为了编写实际的代码，你可以使用你喜欢的语言，比如Python。这里给出一个简单的伪代码概述：

# Prim示例
def prim(matrix, start=0):
    # 初始化等价于S的集合
    S = [start]
    MST = []
    cost = 0

    while V := set(range(len(matrix))) - S:
        min_edge = min([(matrix[u][v], u, v) for u in S, v in V])
        cost += min_edge[0]
        MST.append(min_edge)
        S.add(min_edge[1])  # 添加新的顶点到S

    return cost, MST

# Kruskal示例
def kruskal(edges):
    edges.sort(key=lambda x: x[2])  # 排序边按权重
    MST = []
    cost = 0
    graph = {}  # 使用集合存储已经加入MST的边

    for edge in edges:
        if not (edge[1] in graph or edge[0] in graph):  # 防止形成环
            cost += edge[2]
            MST.append(edge)
            graph.update({edge[1]: True, edge[0]: True})

    return cost, MST

这里的`edges`应是一个二维列表，每一项包含三个元素：源节点、目标节点和边的权重。

用c语言建立一个以邻接矩阵形式存储的图； 2、以Prim算法获得最小生成树； 3、以Kruscal算法获得最小生成树； 4、退出系统。

以下是以邻接矩阵形式存储图，以Prim算法和Kruskal算法获取最小生成树的C语言代码：

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

#define MAX_VERTICES 100
#define INF INT_MAX

typedef struct {
    int weight;
    int visited;
} Edge;

typedef struct {
    Edge edges[MAX_VERTICES][MAX_VERTICES];
    int num_vertices;
    int num_edges;
} Graph;

typedef struct {
    int from;
    int to;
    int weight;
} EdgeInfo;

Graph graph;

void init_graph(int num_vertices) {
    graph.num_vertices = num_vertices;
    graph.num_edges = 0;
    for (int i = 0; i < num_vertices; i++) {
        for (int j = 0; j < num_vertices; j++) {
            graph.edges[i][j].weight = INF;
            graph.edges[i][j].visited = 0;
        }
    }
}

void add_edge(int u, int v, int weight) {
    graph.edges[u][v].weight = weight;
    graph.edges[v][u].weight = weight;
    graph.num_edges++;
}

void remove_edge(int u, int v) {
    graph.edges[u][v].weight = INF;
    graph.edges[v][u].weight = INF;
    graph.num_edges--;
}

int get_next_vertex(int visited[]) {
    for (int i = 0; i < graph.num_vertices; i++) {
        if (!visited[i]) {
            return i;
        }
    }
    return -1;
}

void prim() {
    int visited[MAX_VERTICES] = {0};
    visited[0] = 1;
    int edges_selected = 0;
    while (edges_selected < graph.num_vertices - 1) {
        int min_weight = INF;
        int from, to;
        for (int i = 0; i < graph.num_vertices; i++) {
            if (visited[i]) {
                for (int j = 0; j < graph.num_vertices; j++) {
                    if (!visited[j] && graph.edges[i][j].weight < min_weight) {
                        min_weight = graph.edges[i][j].weight;
                        from = i;
                        to = j;
                    }
                }
            }
        }
        printf("(%d, %d) %d\n", from, to, min_weight);
        visited[to] = 1;
        edges_selected++;
    }
}

int find(int parent[], int i) {
    if (parent[i] == -1) {
        return i;
    }
    return find(parent, parent[i]);
}

void union_vertices(int parent[], int x, int y) {
    int xroot = find(parent, x);
    int yroot = find(parent, y);
    parent[xroot] = yroot;
}

int compare_edge(const void* a, const void* b) {
    EdgeInfo* e1 = (EdgeInfo*)a;
    EdgeInfo* e2 = (EdgeInfo*)b;
    return e1->weight - e2->weight;
}

void kruskal() {
    EdgeInfo edges[graph.num_edges];
    int index = 0;
    for (int i = 0; i < graph.num_vertices; i++) {
        for (int j = i + 1; j < graph.num_vertices; j++) {
            if (graph.edges[i][j].weight != INF) {
                edges[index].from = i;
                edges[index].to = j;
                edges[index].weight = graph.edges[i][j].weight;
                index++;
            }
        }
    }
    qsort(edges, graph.num_edges, sizeof(EdgeInfo), compare_edge);
    int parent[MAX_VERTICES];
    for (int i = 0; i < graph.num_vertices; i++) {
        parent[i] = -1;
    }
    int edges_selected = 0;
    int i = 0;
    while (edges_selected < graph.num_vertices - 1) {
        EdgeInfo next_edge = edges[i++];
        int x = find(parent, next_edge.from);
        int y = find(parent, next_edge.to);
        if (x != y) {
            printf("(%d, %d) %d\n", next_edge.from, next_edge.to, next_edge.weight);
            union_vertices(parent, x, y);
            edges_selected++;
        }
    }
}

int main() {
    init_graph(7);
    add_edge(0, 1, 5);
    add_edge(0, 2, 7);
    add_edge(0, 3, 12);
    add_edge(1, 2, 9);
    add_edge(1, 4, 7);
    add_edge(2, 3, 4);
    add_edge(2, 4, 4);
    add_edge(2, 5, 3);
    add_edge(3, 5, 7);
    add_edge(4, 5, 2);
    add_edge(4, 6, 5);
    add_edge(5, 6, 2);
    printf("Prim's algorithm:\n");
    prim();
    printf("Kruskal's algorithm:\n");
    kruskal();
    return 0;
}

在这个例子中，我们创建了一个具有7个节点的图。然后我们使用`add_edge`函数添加边。最后，我们分别使用Prim算法和Kruskal算法来获取最小生成树，并将结果打印到控制台上。