玩转python：掌握Python数据结构之图-EW帮帮网

图（Graph）是一种用于表示复杂关系的数据结构，由**顶点（Vertex）和边（Edge）**组成。图可以是有向的或无向的，边可以有权重，适用于描述现实世界中的网络关系，如社交网络、交通路网、任务依赖等。本文将深入探讨图的基本概念，并通过丰富的实际案例展示其应用。

图的基本概念与操作

图的表示方式

邻接矩阵：用二维数组表示顶点之间的连接关系。
邻接表：用字典或列表存储每个顶点的邻居节点。

常见操作

添加顶点/边
遍历（DFS/BFS）
最短路径（Dijkstra算法）
最小生成树（Prim/Kruskal算法）
拓扑排序
检测环

图的Python实现（邻接表）

from collections import defaultdict, deque

class Graph:
    def __init__(self):
        self.graph = defaultdict(list)  # 邻接表

    def add_edge(self, u, v, weight=None):
        self.graph[u].append((v, weight) if weight else self.graph[u].append(v)

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

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

图的8大实际应用案例

1. 社交网络分析

场景：分析用户好友关系，推荐共同好友。
实现：使用BFS遍历好友网络。

# 创建社交网络图
social_graph = Graph()
social_graph.add_edge("Alice", "Bob")
social_graph.add_edge("Alice", "Charlie")
social_graph.add_edge("Bob", "Diana")
social_graph.add_edge("Charlie", "Diana")

print("Alice的好友网络（BFS遍历）:")
social_graph.bfs("Alice")  # 输出: Alice Bob Charlie Diana

2. 最短路径导航

场景：地图导航应用，寻找两点间最短路径。
实现：Dijkstra算法计算最短路径。

import heapq

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

# 带权图的邻接表表示
weighted_graph = {
    'A': [('B', 4), ('C', 2)],
    'B': [('C', 5), ('D', 10)],
    'C': [('D', 3)],
    'D': []
}
print("\n从A到各顶点的最短距离:", dijkstra(weighted_graph, 'A'))  # 输出: {'A':0, 'B':4, 'C':2, 'D':5}

3. 任务依赖管理

场景：构建系统中的任务依赖，检测循环依赖。
实现：拓扑排序检测有向无环图（DAG）。

def topological_sort(graph):
    in_degree = {u:0 for u in graph}
    for u in graph:
        for v in graph[u]:
            in_degree[v] += 1
    queue = deque([u for u in in_degree if in_degree[u] == 0])
    sorted_list = []
    while queue:
        u = queue.popleft()
        sorted_list.append(u)
        for v in graph[u]:
            in_degree[v] -= 1
            if in_degree[v] == 0:
                queue.append(v)
    return sorted_list if len(sorted_list) == len(graph) else "存在循环依赖！"

# 任务依赖图
task_graph = {
    '编译': ['链接'],
    '链接': ['测试'],
    '测试': [],
    '设计': ['编译']
}
print("\n任务执行顺序:", topological_sort(task_graph))  # 输出: ['设计', '编译', '链接', '测试']

4. 推荐系统

场景：基于用户行为推荐商品。
实现：构建用户-商品二部图，应用PageRank算法。

import networkx as nx

# 创建用户-商品关系图
G = nx.Graph()
G.add_edges_from([('用户A', '商品1'), ('用户A', '商品2'), ('用户B', '商品2'), ('用户B', '商品3')])
pagerank = nx.pagerank(G)
print("\nPageRank评分:", pagerank)  # 输出: 商品2的评分较高

5. 网络爬虫

场景：管理已爬取和待爬取的URL。
实现：使用图跟踪链接关系，避免重复爬取。

crawler_graph = Graph()
crawled = set()

def crawl(url):
    if url not in crawled:
        print(f"爬取: {url}")
        crawled.add(url)
        # 假设提取到链接: link1, link2
        for link in ['link1', 'link2']:
            crawler_graph.add_edge(url, link)
            crawl(link)

crawl('start_url')  # 递归爬取所有链接

6. 知识图谱查询

场景：问答系统中的实体关系查询。
实现：构建知识图谱，搜索关联实体。

knowledge_graph = {
    'Python': ['编程语言', 'Guido van Rossum'],
    'Guido van Rossum': ['荷兰', '开发者']
}

def search_entity(entity):
    return knowledge_graph.get(entity, [])

print("\nPython的关联实体:", search_entity('Python'))  # 输出: ['编程语言', 'Guido van Rossum']

7. 电路设计验证

场景：检查电路连接是否存在短路。
实现：检测图中是否存在环。

def has_cycle(graph):
    visited = set()
    stack = set()
    def dfs(node):
        if node in stack:
            return True
        if node in visited:
            return False
        visited.add(node)
        stack.add(node)
        for neighbor in graph[node]:
            if dfs(neighbor):
                return True
        stack.remove(node)
        return False
    for node in graph:
        if dfs(node):
            return True
    return False

circuit_graph = {
    'A': ['B', 'C'],
    'B': ['D'],
    'C': ['D'],
    'D': []
}
print("\n电路是否存在环:", has_cycle(circuit_graph))  # 输出: False

8. 交通流量优化

场景：分析城市交通拥堵点。
实现：使用最大流算法优化流量分配。

from networkx.algorithms.flow import shortest_augmenting_path

G = nx.DiGraph()
G.add_edge('A', 'B', capacity=4)
G.add_edge('A', 'C', capacity=2)
G.add_edge('B', 'D', capacity=3)
G.add_edge('C', 'D', capacity=5)
flow_value, flow_dict = nx.maximum_flow(G, 'A', 'D', flow_func=shortest_augmenting_path)
print("\n最大流量分配:", flow_dict)  # 输出: B到D流量3，C到D流量2

总结

图数据结构在解决复杂关系问题时表现出色，无论是社交网络分析、路径规划，还是系统依赖管理，图都能提供高效的解决方案。通过本文的案例，我们展示了图在以下场景的应用：

社交网络分析：BFS遍历好友关系。
路径规划：Dijkstra算法计算最短路径。
任务调度：拓扑排序管理依赖。
推荐系统：PageRank算法评估重要性。
网络爬虫：递归爬取链接。
知识图谱：实体关系查询。
电路设计：环检测避免短路。
交通优化：最大流算法分配流量。

掌握图的操作和算法，能够帮助你在实际项目中高效处理网络关系问题。希望本文的案例能为你提供启发，欢迎在评论区交流你的想法！

玩转python：掌握Python数据结构之图