Python案例中的图算法如何实现？

wen python案例 2026-06-15 233

本文目录导读：

Python案例中的图算法如何实现？

图的表示方法
图的遍历算法
最短路径算法
最小生成树算法
拓扑排序
完整案例：社交网络分析
性能优化建议

我来详细介绍Python中图算法的实现方法,包括图的表示和核心算法。

图的表示方法

邻接矩阵

class AdjMatrix:
    def __init__(self, vertices):
        self.V = vertices
        self.graph = [[0] * vertices for _ in range(vertices)]
    def add_edge(self, u, v, weight=1):
        self.graph[u][v] = weight
        self.graph[v][u] = weight  # 无向图
# 使用示例
g = AdjMatrix(5)
g.add_edge(0, 1)
g.add_edge(1, 2)

邻接表（推荐）

from collections import defaultdict
class Graph:
    def __init__(self):
        self.graph = defaultdict(list)
    def add_edge(self, u, v, weight=1):
        self.graph[u].append((v, weight))
        # 无向图加上：self.graph[v].append((u, weight))
    def display(self):
        for vertex in self.graph:
            print(f"{vertex}: {self.graph[vertex]}")
# 使用示例
g = Graph()
g.add_edge(0, 1, 4)
g.add_edge(0, 2, 3)
g.add_edge(1, 2, 1)

图的遍历算法

广度优先搜索 (BFS)

from collections import deque
def bfs(graph, start):
    visited = set()
    queue = deque([start])
    visited.add(start)
    while queue:
        vertex = queue.popleft()
        print(vertex, end=" ")
        for neighbor in graph[vertex]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
    print()
# 使用示例
graph = {
    0: [1, 2],
    1: [3],
    2: [3],
    3: []
}
bfs(graph, 0)  # 输出: 0 1 2 3

深度优先搜索 (DFS)

def dfs_recursive(graph, vertex, visited=None):
    if visited is None:
        visited = set()
    visited.add(vertex)
    print(vertex, end=" ")
    for neighbor in graph[vertex]:
        if neighbor not in visited:
            dfs_recursive(graph, neighbor, visited)
# 迭代版本
def dfs_iterative(graph, start):
    visited = set()
    stack = [start]
    while stack:
        vertex = stack.pop()
        if vertex not in visited:
            visited.add(vertex)
            print(vertex, end=" ")
            stack.extend(reversed(graph[vertex]))
# 使用示例
graph = {
    0: [1, 2],
    1: [3],
    2: [3],
    3: []
}
dfs_recursive(graph, 0)  # 输出: 0 1 3 2

最短路径算法

Dijkstra算法（单源最短路径）

import heapq
def dijkstra(graph, start):
    # 初始化距离字典
    distances = {vertex: float('infinity') for vertex in graph}
    distances[start] = 0
    pq = [(0, start)]  # (距离, 顶点)
    while pq:
        current_distance, current_vertex = heapq.heappop(pq)
        # 如果当前距离大于已知距离，跳过
        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(pq, (distance, neighbor))
    return distances
# 使用示例
graph = {
    'A': {'B': 4, 'C': 2},
    'B': {'A': 4, 'C': 1, 'D': 5},
    'C': {'A': 2, 'B': 1, 'D': 8, 'E': 10},
    'D': {'B': 5, 'C': 8, 'E': 2},
    'E': {'C': 10, 'D': 2}
}
distances = dijkstra(graph, 'A')
print(f"最短路径: {distances}")  # {'A': 0, 'B': 3, 'C': 2, 'D': 8, 'E': 10}

Floyd-Warshall算法（所有顶点对最短路径）

def floyd_warshall(graph):
    n = len(graph)
    dist = [[float('inf')] * n for _ in range(n)]
    # 初始化
    for i in range(n):
        for j in range(n):
            if i == j:
                dist[i][j] = 0
            elif j in graph[i]:
                dist[i][j] = graph[i][j]
    # 动态规划
    for k in range(n):
        for i in range(n):
            for j in range(n):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
    return dist

最小生成树算法

Kruskal算法

class UnionFind:
    def __init__(self, vertices):
        self.parent = {v: v for v in vertices}
        self.rank = {v: 0 for v in vertices}
    def find(self, vertex):
        if self.parent[vertex] != vertex:
            self.parent[vertex] = self.find(self.parent[vertex])
        return self.parent[vertex]
    def union(self, v1, v2):
        root1, root2 = self.find(v1), self.find(v2)
        if root1 != root2:
            if self.rank[root1] < self.rank[root2]:
                self.parent[root1] = root2
            elif self.rank[root1] > self.rank[root2]:
                self.parent[root2] = root1
            else:
                self.parent[root2] = root1
                self.rank[root1] += 1
def kruskal_mst(graph):
    edges = []
    for u in graph:
        for v, w in graph[u].items():
            edges.append((w, u, v))
    edges.sort()
    vertices = list(graph.keys())
    uf = UnionFind(vertices)
    mst = []
    for weight, u, v in edges:
        if uf.find(u) != uf.find(v):
            uf.union(u, v)
            mst.append((u, v, weight))
    return mst
# 使用示例
graph = {
    'A': {'B': 4, 'C': 2},
    'B': {'A': 4, 'C': 1, 'D': 5},
    'C': {'A': 2, 'B': 1, 'D': 8, 'E': 10},
    'D': {'B': 5, 'C': 8, 'E': 2},
    'E': {'C': 10, 'D': 2}
}
mst = kruskal_mst(graph)
print(f"最小生成树: {mst}")
# [('B', 'C', 1), ('A', 'C', 2), ('D', 'E', 2), ('B', 'D', 5)]

拓扑排序

from collections import defaultdict, deque
def topological_sort(vertices, edges):
    # 构建图的入度
    in_degree = {v: 0 for v in vertices}
    graph = defaultdict(list)
    for u, v in edges:
        graph[u].append(v)
        in_degree[v] += 1
    # 将所有入度为0的顶点加入队列
    queue = deque([v for v in vertices if in_degree[v] == 0])
    result = []
    while queue:
        u = queue.popleft()
        result.append(u)
        for v in graph[u]:
            in_degree[v] -= 1
            if in_degree[v] == 0:
                queue.append(v)
    if len(result) != len(vertices):
        print("图中存在环！")
        return None
    return result
# 使用示例
vertices = ['A', 'B', 'C', 'D', 'E']
edges = [('A', 'B'), ('A', 'C'), ('B', 'D'), ('C', 'D'), ('D', 'E')]
order = topological_sort(vertices, edges)
print(f"拓扑排序: {order}")  # ['A', 'C', 'B', 'D', 'E']

完整案例：社交网络分析

class SocialNetwork:
    def __init__(self):
        self.graph = defaultdict(set)
    def add_friendship(self, person1, person2):
        self.graph[person1].add(person2)
        self.graph[person2].add(person1)
    def friends_count(self, person):
        return len(self.graph[person])
    def shortest_path(self, start, end):
        """使用BFS找最短路径"""
        visited = {start}
        queue = deque([(start, [start])])
        while queue:
            person, path = queue.popleft()
            for friend in self.graph[person]:
                if friend == end:
                    return path + [friend]
                if friend not in visited:
                    visited.add(friend)
                    queue.append((friend, path + [friend]))
        return None
    def find_communities(self):
        """查找连通分量"""
        visited = set()
        communities = []
        for person in self.graph:
            if person not in visited:
                community = []
                queue = deque([person])
                visited.add(person)
                while queue:
                    current = queue.popleft()
                    community.append(current)
                    for friend in self.graph[current]:
                        if friend not in visited:
                            visited.add(friend)
                            queue.append(friend)
                communities.append(community)
        return communities
    def suggest_friends(self, person, max_suggestions=5):
        """基于共同好友推荐"""
        if person not in self.graph:
            return []
        suggestions = defaultdict(int)
        # 遍历朋友的朋友
        for friend in self.graph[person]:
            for friend_of_friend in self.graph[friend]:
                if (friend_of_friend != person and 
                    friend_of_friend not in self.graph[person]):
                    suggestions[friend_of_friend] += 1
        # 按共同好友数量排序
        sorted_suggestions = sorted(suggestions.items(), 
                                   key=lambda x: x[1], 
                                   reverse=True)
        return sorted_suggestions[:max_suggestions]
# 使用示例
network = SocialNetwork()
network.add_friendship("Alice", "Bob")
network.add_friendship("Alice", "Charlie")
network.add_friendship("Bob", "David")
network.add_friendship("Charlie", "David")
network.add_friendship("David", "Eve")
# 查找最短路径
path = network.shortest_path("Alice", "Eve")
print(f"Alice到Eve的最短路径: {path}")
# 朋友推荐
suggestions = network.suggest_friends("Alice")
print(f"为Alice推荐的朋友: {suggestions}")

性能优化建议

# 使用NumPy加速矩阵操作
import numpy as np
def floyd_warshall_fast(adj_matrix):
    n = len(adj_matrix)
    dist = np.array(adj_matrix, dtype=float)
    for k in range(n):
        dist = np.minimum(dist, 
                         dist[:, np.newaxis, k] + dist[k, :])
    return dist
# 使用缓存的DFS
from functools import lru_cache
@lru_cache(maxsize=None)
def adjacency_list(vertex):
    # 缓存邻接列表计算
    pass

这些Python图算法实现涵盖了常见的图处理需求,可以根据具体场景选择合适的算法和数据结构。

本文地址： https://www.bmjup.com/post/6263.html