写出prim算法的代码

以下是Prim算法的伪代码：

1. 初始化一个空的集合T，存储最小生成树的边。
2. 随意选择一个顶点v0，将其加入集合S中。
3. 依次寻找从S中的顶点到不在S中的顶点的所有边中权值最小的边，将该边加入T中。
4. 将该边的另一个顶点加入S中。
5. 重复第3、4步，直到S中包含所有顶点。

以下是Prim算法的Python代码实现：

def prim(graph):
n = len(graph)
T = set()
S = {0}
while len(S) < n:
min_weight = float('inf')
min_edge = None
for u in S:
for v in range(n):
if v not in S and graph[u][v] < min_weight:
min_weight = graph[u][v]
min_edge = (u, v)
T.add(min_edge)
S.add(min_edge[1])
return T

#其中graph是一个二维数组，表示图的邻接矩阵

相关问题

用python使用prim算法写出最小生成树的代码

Prim算法是一种常用的最小生成树算法，其基本思想是从一个顶点开始，逐步加入距离该顶点最近的未加入树中的顶点，直到所有顶点都被加入为止。下面是用Python实现Prim算法的代码：

import sys

class Graph:
    def __init__(self, vertices):
        self.V = vertices
        self.graph = [[0 for column in range(vertices)]
                      for row in range(vertices)]

    def printMST(self, parent):
        print("Edge \tWeight")
        for i in range(1, self.V):
            print(parent[i], "-", i, "\t", self.graph[i][parent[i]])

    def minKey(self, key, mstSet):
        min = sys.maxsize
        for v in range(self.V):
            if key[v] < min and mstSet[v] == False:
                min = key[v]
                min_index = v
        return min_index

    def primMST(self):
        key = [sys.maxsize] * self.V
        parent = [None] * self.V
        key[0] = 0 
        mstSet = [False] * self.V

        parent[0] = -1 

        for cout in range(self.V):

            u = self.minKey(key, mstSet)

            mstSet[u] = True

            for v in range(self.V):

                if self.graph[u][v] > 0 and mstSet[v] == False and key[v] > self.graph[u][v]:
                    key[v] = self.graph[u][v]
                    parent[v] = u

        self.printMST(parent)

g = Graph(5)
g.graph = [[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]]

g.primMST()

上述代码实现了Prim算法的主要功能，包括了最小生成树的生成和输出。其中，Graph类代表了一个图，其中包含V个顶点，graph是一个V×V的邻接矩阵，表示了图中各个顶点之间的边。primMST()函数是Prim算法的主要实现函数，通过调用minKey()函数找到距离该顶点最近的未加入树中的顶点，并将其加入树中。最终，通过调用printMST()函数输出最小生成树的边和权重。

用C++写prim算法

Prim算法是一种求无向加权连通图的最小生成树的贪心算法，可以用C语言来实现。下面是一份示例代码：

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

#define MAX_VERTICES 1000 // 最大顶点数

typedef struct {
    int v1, v2, weight;
} Edge;

typedef struct {
    int count;
    int parent[MAX_VERTICES];
    int key[MAX_VERTICES];
    int mst[MAX_VERTICES][MAX_VERTICES];
} Graph;

Graph create_graph(int vertices) {
    Graph G;
    G.count = vertices;
    for (int i = 0; i < vertices; i++) {
        for (int j = 0; j < vertices; j++) {
            G.mst[i][j] = 0;
        }
        G.key[i] = INT_MAX;
        G.parent[i] = -1;
    }
    return G;
}

void add_edge(Graph *G, int v1, int v2, int weight) {
    G->mst[v1][v2] = weight;
    G->mst[v2][v1] = weight;
}

int extract_min(Graph *G, int *visited) {
    int min = INT_MAX, min_index = -1;
    for (int i = 0; i < G->count; i++) {
        if (visited[i] == 0 && G->key[i] < min) {
            min = G->key[i];
            min_index = i;
        }
    }
    return min_index;
}

void prim(Graph *G) {
    int visited[MAX_VERTICES] = {0};
    G->key[0] = 0;
    for (int i = 0; i < G->count-1; i++) {
        int u = extract_min(G, visited);
        visited[u] = 1;
        for (int v = 0; v < G->count; v++) {
            if (G->mst[u][v] != 0 && visited[v] == 0 && G->mst[u][v] < G->key[v]) {
                G->parent[v] = u;
                G->key[v] = G->mst[u][v];
            }
        }
    }
    for (int i = 1; i < G->count; i++) {
        add_edge(G, G->parent[i], i, G->mst[G->parent[i]][i]);
    }
}

void print_mst(Graph G) {
    for (int i = 1; i < G.count; i++) {
        printf("(%d, %d) -> %d\n", G.parent[i], i, G.mst[G.parent[i]][i]);
    }
}

int main() {
    Graph G = create_graph(6);
    add_edge(&G, 0, 1, 4);
    add_edge(&G, 0, 2, 3);
    add_edge(&G, 1, 2, 1);
    add_edge(&G, 1, 3, 2);
    add_edge(&G, 2, 3, 4);
    add_edge(&G, 3, 4, 2);
    add_edge(&G, 4, 5, 6);
    prim(&G);
    print_mst(G);
    return 0;
}

这份代码实现了Prim算法，使用邻接矩阵来表示图，其中`create_graph`函数用来创建一个空的图，`add_edge`函数用来添加一条边，`extract_min`函数用来从尚未访问的顶点中选取key值最小的顶点，`prim`函数用来求出最小生成树，`print_mst`函数用来输出最小生成树的边。