Python 经典贪心算法之Prim算法案例详解

Sure, I'd be happy to help! Here is a detailed guide on the Prim algorithm in Python, including two examples:

Introduction to Prim Algorithm

Prim's algorithm is a greedy algorithm that finds a minimum spanning tree for a weighted undirected graph. The algorithm starts with a single vertex and gradually expands the tree by adding the cheapest edge that connects the tree to a new vertex. The algorithm continues until all vertices are included in the tree.

Prim Algorithm Implementation

Here is a Python implementation of the Prim algorithm:

import heapq

def prim(graph, start):
    visited = set()
    edges = [(0, start)]
    while edges:
        weight, vertex = heapq.heappop(edges)
        if vertex not in visited:
            visited.add(vertex)
            yield weight, vertex
            for neighbor, w in graph[vertex]:
                if neighbor not in visited:
                    heapq.heappush(edges, (w, neighbor))

The prim function takes a graph represented as a dictionary of lists, where each key is a vertex and the corresponding value is a list of tuples representing the edges and their weights. The start parameter specifies the starting vertex for the algorithm.

The function uses a heap to keep track of the cheapest edges that connect the tree to new vertices. The visited set keeps track of the vertices that have already been added to the tree.

The function yields the weight and vertex of each edge that is added to the tree.

Example 1: Finding the Minimum Spanning Tree

Let's use the prim function to find the minimum spanning tree of the following graph:

     2
  A-----B
  |\   /|
  | \ / |
3 |  X  | 1
  | / \ |
  |/   \|
  C-----D
     4

We can represent this graph as a dictionary of lists:

graph = {
    'A': [('B', 2), ('C', 3)],
    'B': [('A', 2), ('C', 1), ('D', 4)],
    'C': [('A', 3), ('B', 1), ('D', 5)],
    'D': [('B', 4), ('C', 5)]
}

To find the minimum spanning tree, we can call the prim function with the starting vertex 'A':

for weight, vertex in prim(graph, 'A'):
    print(f'{vertex} - {weight}')

This will output:

A - 0
B - 2
C - 3
D - 4

This means that the minimum spanning tree consists of the edges (A, B), (B, C), and (B, D), with a total weight of 2 + 1 + 4 = 7.

Example 2: Finding the Shortest Path

We can also use the prim function to find the shortest path between two vertices in a graph. For example, let's find the shortest path between vertices 'A' and 'D' in the same graph:

for weight, vertex in prim(graph, 'A'):
    if vertex == 'D':
        print(f'Shortest path weight: {weight}')
        break

This will output:

Shortest path weight: 4

This means that the shortest path between 'A' and 'D' is the edge (B, D), with a weight of 4.

I hope this guide helps you understand the Prim algorithm in Python!