贪心算法最小生成树生成的例题

以下是使用Prim算法求解最小生成树的例题：

假设有一个图，其中有N个点，点与点之间的连接的花费已经给出。我们需要设计一个算法来解决这个最小生成树的问题。

输入：
- 图的顶点数N
- 图的连接花费矩阵cost[][]，其中cost[i][j]表示顶点i和顶点j之间的连接花费。如果两个顶点之间没有连接，则cost[i][j]为无穷大。

输出：
- 最小生成树的总花费

算法步骤：
1. 创建一个空的集合visited，用于存储已经访问过的顶点。
2. 选择一个起始顶点start，并将其加入visited集合。
3. 创建一个空的优先队列pq，用于存储待访问的边。将起始顶点start的所有连接边加入pq。
4. 初始化最小生成树的总花费为0。
5. 当pq不为空时，执行以下步骤：
- 从pq中取出花费最小的边edge，并将其加入最小生成树。
- 如果边edge的另一个顶点不在visited集合中，则将该顶点加入visited集合，并将该顶点的所有连接边加入pq。
- 更新最小生成树的总花费。
6. 输出最小生成树的总花费。

示例代码如下所示：

import heapq

def prim(N, cost):
    visited = set()
    start = 0
    visited.add(start)
    pq = []
    total_cost = 0

    for i in range(1, N):
        heapq.heappush(pq, (cost[start][i], start, i))

    while pq:
        c, u, v = heapq.heappop(pq)
        if v not in visited:
            visited.add(v)
            total_cost += c
            for i in range(N):
                if i not in visited:
                    heapq.heappush(pq, (cost[v][i], v, i))

    return total_cost

# 示例输入
N = 4
cost = [[0, 1, 3, 4],
        [1, 0, 2, 5],
        [3, 2, 0, 6],
        [4, 5, 6, 0]]

# 调用prim算法求解最小生成树的总花费
min_cost = prim(N, cost)
print("最小生成树的总花费为:", min_cost)