prim算法 贪心算法

Prim算法是一种求解加权无向连通图的最小生成树的算法。其基本思想是从一个点开始，每次选择一个与当前生成树相邻且权值最小的边，直到生成一棵包含所有节点的树为止。具体步骤如下：

1. 任选一个起始点，将其加入生成树中。
2. 找到与生成树相邻的所有边中权值最小的那条边，将其加入生成树中。
3. 重复第二步，直到生成一棵包含所有节点的树为止。

下面是一个使用Prim算法求解最小生成树的Python代码示例：

def prim(graph):
    # 初始化
    nodes = list(graph.keys())
    visited = [nodes[0]]
    edges = []
    # 循环直到所有节点都被访问
    while len(visited) < len(nodes):
        min_edge = None
        # 找到与已访问节点相邻的所有边中权值最小的那条边
        for node in visited:
            for neighbor, weight in graph[node].items():
                if neighbor not in visited:
                    if min_edge is None or weight < min_edge[2]:
                        min_edge = (node, neighbor, weight)
        # 将该边加入生成树中
        edges.append(min_edge)
        visited.append(min_edge[1])
    return edges

贪心算法是一种在求解最优解问题时采用贪心策略的算法。其基本思想是每次选择当前看来最优的解决方案，直到达到全局最优解。贪心算法通常适用于满足最优子结构性质的问题，即问题的最优解可以通过子问题的最优解推导得到。具体步骤如下：

1. 将问题分解为若干个子问题。
2. 对每个子问题求解，得到子问题的最优解。
3. 将所有子问题的最优解合并成原问题的解。

下面是一个使用贪心算法求解背包问题的Python代码示例：

def knapsack(items, capacity):
    # 按照单位价值排序
    items = sorted(items, key=lambda x: x[1]/x[0], reverse=True)
    # 初始化
    total_value = 0
    knapsack = []
    # 循环直到背包装满
    for item in items:
        if capacity >= item[0]:
            knapsack.append(item)
            capacity -= item[0]
            total_value += item[1]
        else:
            knapsack.append((capacity, item[1]/item[0]*capacity))
            total_value += item[1]/item[0]*capacity
            break
    return knapsack, total_value