数据结构与算法Python版 图

一、图

表示图的英文单词

• painting：用画刷画的油画
• drawing：用硬笔画的素描/线条画
• picture：真实形象所反映的画，如照片等，如take picture
• image：由印象而来的画，遥感影像做image，因是经过传感器印象而来
• figure：轮廓图的意思，某个侧面的轮廓，所以有figure out的说法
• diagram：抽象的概念关系图，如电路图、海洋环流图、类层次图
• chart：由数字统计来的柱状图、饼图、折线图
• map：地图；plot：地图上的一小块
• graph：重在由一些基本元素构造而来的图，如点、线段等

图Graph的例子

• 图是比树更为一般的结构，树是一种具有特殊性质的图
• 图可以用来表示现实世界中很多事物。例如道路交通系统、航班线路、互联网连接等
• 公共交通：一个城市的公交系统有数百条运营线路，公交站点数千个
• 互联网：一张百亿个信息点的巨型网络
• 社交网络：六度分隔理论，世界上任何两个人之间通过最多6个人即可建立联系

图的相关术语表

• 顶点Vertex（也称“节点Node”）：是图的基本组成部分，顶点具有名称标识Key，也可以携带数据项payload
• 边Edge（也称“弧Arc”）：作为2个顶点之间关系的表示，边连接两个顶点；边可以是无向或者有向的，相应的图称作“无向图”和“有向图”
• 权重Weight：为了表达从一个顶点到另一个顶点的**“代价”**，可以给边赋权；例如公交网络中两个站点之间的“距离”、“通行时间”和“票价”都可以作为权重。
• 图的定义：一个图G可以定义为G=(V, E)，其中V是顶点的集合，E是边的集合，E中的每条边e=(v, w)，v和w都是V中的顶点；
• 子图：V和E的子集
• 赋权图：在E中的每条边e=(v, w)中添加权重分量，如果边是有向的，叫有向赋权图。
• 路径Path：图中的路径，是由边依次连接起来的顶点序列；无权路径的长度为边的数量；带权路径的长度为所有边权重的和
• 圈Cycle：圈是首尾顶点相同的路径
• 有向无环图（directed acyclic graph: DAG）：如果一个有向图不存在任何圈，则称为有向无环图

二、抽象数据类型图

抽象数据类型图（ADT Graph）

抽象数据类型图的实现方法

• 方法一：邻接矩阵 Adjacency Matrix
• 方法二：邻接表 Adjacency List

邻接矩阵

• 矩阵的每行和每列都代表图中的顶点
• 如果两个顶点之间有边相连，设定行列值。无权边则将矩阵分量标注为1；带权边则将矩阵分量标注为权重
• 优点是简单，缺点效率低。大多数问题所对应的图都是稀疏sparse的，即边远远少于顶点数量平方这个量级

邻接列表

• 维护一个包含所有顶点的主列表（master list），主列表中的每个顶点，再关联一个与自身有边连接的所有顶点的列表
• 优点存储空间紧凑高效

三、图的实现-邻接列表法

顶点Vertex类：含了顶点信息，以及顶点连接边信息

class Vertex:
    """顶点类"""

    def __init__(self, key):
        self.key = key
        self.connected_to = {}

    def add_neighbor(self, nbr, weight=0):
        """键为nbr顶点对象，值为权重"""
        self.connected_to[nbr] = weight

    def __str__(self):
        return f"{self.key} connected to : {[x.key for x in self.connected_to]}"

    def get_connections(self):
        return self.connected_to.keys()

    def get_key(self):
        return self.key

    def get_weight(self, nbr):
        return self.connected_to.get(nbr, None)

图Graph类：Graph保存了包含所有顶点的主表

class Graph:
    def __init__(self):
        self.vertexes = {}
        self.num_vertexes = 0

    def add_vertex(self, key):
        """加入顶点：以key为键，以Vertex对象为值"""
        self.num_vertexes += 1
        new_vertex = Vertex(key)
        self.vertexes[key] = new_vertex
        return new_vertex

    def get_vertex(self, key):
        if key in self.vertexes:
            return self.vertexes[key]
        else:
            return None

    def __contains__(self, key):
        return key in self.vertexes

    def add_edge(self, begin, end, cost=0):
        """添加边，如果顶点不存在，先添加顶点再加边"""
        if begin not in self.vertexes:
            self.add_vertex(begin)
        if end not in self.vertexes:
            self.add_vertex(end)
        self.vertexes[begin].add_neighbor(self.vertexes[end], cost)

    def get_vertexes(self):
        """返回所有顶点"""
        return self.vertexes.keys()

    def __iter__(self):
        return iter(self.vertexes.values())


g = Graph()
for i in range(6):
    g.add_vertex(i)
print(g.get_vertexes())

g.add_edge(0, 1, 5)
g.add_edge(0, 5, 2)
g.add_edge(1, 2, 4)
g.add_edge(2, 3, 9)
g.add_edge(3, 4, 7)
g.add_edge(3, 5, 3)
g.add_edge(4, 0, 1)
g.add_edge(5, 4, 8)
g.add_edge(5, 2, 1)

for v in g:
    for w in v.get_connections():
        print(f"({v.get_key()},{w.get_key()})")
        
        
### 输出结果
dict_keys([0, 1, 2, 3, 4, 5])
(0,1)
(0,5)
(1,2)
(2,3)
(3,4)
(3,5)
(4,0)
(5,4)
(5,2)

您正在阅读的是《数据结构与算法Python版》专栏！关注不迷路~