Python高级数据结构——图论算法（Graph Algorithms）

class GraphAdjacencyMatrix:
    def __init__(self, num_vertices):
        self.num_vertices = num_vertices
        self.matrix = [[0] * num_vertices for _ in range(num_vertices)]

    def add_edge(self, start, end):
        self.matrix[start][end] = 1
        self.matrix[end][start] = 1

# 示例
graph_matrix = GraphAdjacencyMatrix(5)
graph_matrix.add_edge(0, 1)
graph_matrix.add_edge(1, 2)
graph_matrix.add_edge(2, 3)
graph_matrix.add_edge(3, 4)

from collections import defaultdict

class GraphAdjacencyList:
    def __init__(self):
        self.graph = defaultdict(list)

    def add_edge(self, start, end):
        self.graph[start].append(end)
        self.graph[end].append(start)

# 示例
graph_list = GraphAdjacencyList()
graph_list.add_edge(0, 1)
graph_list.add_edge(1, 2)
graph_list.add_edge(2, 3)
graph_list.add_edge(3, 4)

def dfs(graph, start, visited=None):
    if visited is None:
        visited = set()
    visited.add(start)
    print(start, end=" ")
    for neighbor in graph[start]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)

# 示例
dfs(graph_list.graph, 0)

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
    visited.add(start)
    while queue:
        current = queue.popleft()
        print(current, end=" ")
        for neighbor in graph[current]:
            if neighbor not in visited:
                queue.append(neighbor)
                visited.add(neighbor)

# 示例
bfs(graph_list.graph, 0)

import heapq

def dijkstra(graph, start):
    distances = {vertex: float('infinity') for vertex in graph}
    distances[start] = 0
    priority_queue = [(0, start)]
    while priority_queue:
        current_distance, current_vertex = heapq.heappop(priority_queue)
        if current_distance > distances[current_vertex]:
            continue
        for neighbor, weight in graph[current_vertex].items():
            distance = current_distance + weight
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(priority_queue, (distance, neighbor))
    return distances

# 示例
graph_weighted = {
    0: {1: 1, 2: 4},
    1: {0: 1, 2: 2, 3: 5},
    2: {0: 4, 1: 2, 3: 1},
    3: {1: 5, 2: 1}
}
shortest_distances = dijkstra(graph_weighted, 0)
print("Shortest Distances:", shortest_distances)

import heapq

def prim(graph):
    start_vertex = list(graph.keys())[0]
    visited = {start_vertex}
    edges = [
        (cost, start_vertex, to_vertex)
        for to_vertex, cost in graph[start_vertex].items()
    ]
    heapq.heapify(edges)
    minimum_spanning_tree = []
    while edges:
        cost, from_vertex, to_vertex = heapq.heappop(edges)
        if to_vertex not in visited:
            visited.add(to_vertex)
            minimum_spanning_tree.append((from_vertex, to_vertex, cost))
            for neighbor, neighbor_cost in graph[to_vertex].items():
                if neighbor not in visited:
                    heapq.heappush(edges, (neighbor_cost, to_vertex, neighbor))
    return minimum_spanning_tree

# 示例
graph_weighted = {
    'A': {'B': 1, 'C': 4},
    'B': {'A': 1, 'C': 2, 'D': 5},
    'C': {'A': 4, 'B': 2, 'D': 1},
    'D': {'B': 5, 'C': 1}
}
minimum_spanning_tree = prim(graph_weighted)
print("Minimum Spanning Tree:", minimum_spanning_tree)