本文共 1993 字，大约阅读时间需要 6 分钟。

图的概念与应用

图是信息时代的重要数据结构，广泛应用于网络路由、计算机科学课程安排、生物学蛋白质结构预测等多个领域。图的实现方法有多种，其中邻接矩阵和邻接表是最常用的两种 обра形式。

图的定义

图由顶点和边组成，其中顶点是数字或符号表示的实体，边描述了顶点之间的关系。一个图可以用数学公式表示为 G=(V, E)，其中：

• V 表示顶点的集合。
• E 表示边的集合，每条边连接两个顶点。

顶点和边可以带权重，权重用于表示边的权值或代价。

图的实现方法

在Python中，常用的图实现方法包括邻接矩阵和邻接表。邻接矩阵适合稠密图，但不适合稀疏图；而邻接表则更适合稀疏图，效率更高。

邻接矩阵

邻接矩阵以二维数组形式存储，将顶点的位置用于行和列索引。矩阵中的每个元素表示两个顶点之间是否有一条边，及其权重。

邻接表

邻接表采用字典形式存储，将每个顶点映射到其相邻顶点列表。这种形式占用内存更少，适合稀疏图。

图的应用场景

图在各种实际问题中扮演重要角色，其应用包括：

• 词梯问题：寻找从一个单词到另一个单词的最短变化路径。
• 拓扑排序：确定任务执行顺序，解决 precede 和 depend 的关系。
• 最短路径问题：寻找权重最小的路径。
• 广播问题：设计高效信息传递机制，利用最小生成树进行信息传递。

算法概述

图算法分为几种常用类型：

难忘的顶点类

每个顶点维护其相邻顶点和边权重，支持添加邻居、获取所有邻居和查询边权重等操作。代码如下：

class Vertex:
    def __init__(self, key):
        self.id = key
        self.connected_to = {}
        
    def add_neighbor(self, neighbor, weight=0):
        self.connected_to[neighbor] = weight
    
    def get_connections(self):
        return self.connected_to.keys()
    
    def get_weight(self, neighbor):
        return self.connected_to.get(neighbor, 0)
    
    def __str__(self):
        return f"Vertex({self.id}, {self.connected_to})"

代码示例

class Graph:
    def __init__(self):
        self.vertices = {}
        self.num_vertices = 0
        
    def add_vertex(self, key):
        vertex = Vertex(key)
        self.num_vertices += 1
        self.vertices[key] = vertex
        return vertex
        
    def get_vertex(self, name):
        return self.vertices.get(name, None)
    
    def add_edge(self, from_vertex, to_vertex, cost=0):
        if from_vertex not in self.vertices:
            from_vertex = self.add_vertex(from_vertex)
        if to_vertex not in self.vertices:
            to_vertex = self.add_vertex(to_vertex)
        from_vertex.add_neighbor(to_vertex, cost)
    
    def get_vertices(self):
        return self.vertices.keys()
    
    def __iter__(self):
        return iter(self.vertices.values())

如果有任何问题或建议，请随时告诉我！