邻接矩阵（adjacency matrix）

有向图

假设有5个城市，名字依次叫做ABCDE。

vertex = ['A', 'B', 'C', 'D', 'E']  
  
adjacency_matrix = [  
    [0, 1, 0, 0, 0],  
    [1, 0, 0, 0, 1],  
    [0, 1, 0, 1, 0],  
    [0, 1, 1, 0, 0],  
    [0, 0, 0, 1, 0],  
]

adjacency_matrix[i][j] 表示从i到j是否具有有向边。

有向边的含义：

adjacency_matrix[2][1] 等于 1，表明从C可以到达B。
adjacency_matrix[1][2] 等于 0，表明从B不能到达C。
adjacency_matrix[4][3] 等于 1，表明从E可以到达D。
adjacency_matrix[3][0] 等于 0，表明从D不能到达A。

在这个例子中，每一个城市到达自己这里，好像说不过去，没有什么意义，索性让正对角线为0。

无向图

注意，如果这个图是无向的，那么邻接矩阵是对称矩阵，类似这样：

adjacency_matrix = [
    [0, 1, 0, 0, 1],
    [1, 0, 1, 1, 0],
    [0, 1, 0, 1, 1], 
    [0, 1, 1, 0, 0],
    [1, 0, 1, 0, 0]
]

带权（网）

如果ABCDE这5个城市之间修起了公路，想通过边的权重来代表两个城市之间的公路距离是多少千米。

带权的形式是这样的：

vertex = ['A', 'B', 'C', 'D', 'E']  

adjacency_matrix = [
    [0, 72, 0, 0, 23],
    [72, 0, 94, 61, 0],
    [0, 94, 0, 19, 59],
    [0, 61, 19, 0, 0],
    [23, 0, 59, 0, 0]  
]

在这里,A到B的公路距离是72km, B到C的公路距离是94km, B到D的公路距离是61km, A到E的公路距离是23km。

带多维权重信息（容器）

假设后来在公路的基础上，又修建了铁路，开辟了飞机航线。乘坐不同的交通工具会花不同的时间，假设单位为分钟数。

况且每个地方地势不一样，去的时候和回来的时候所花的时间也不一样。

可以通过一个类来表示多种形式的权。或者，元组或命名元组，dataclass类也可以。

这里使用dataclass可能更方便。

from dataclasses import dataclass

vertex = ['A', 'B', 'C', 'D', 'E']


@dataclass
class E:
    driving_time: int
    train_time: int
    flying_time: int


adjacency_matrix = [
    [E(0, 0, 0), E(4320, 1200, 60), E(0, 0, 0), E(0, 0, 0), E(1800, 600, 48)],
    [E(3600, 900, 54), E(0, 0, 0), E(4800, 1500, 60), E(3000, 1080, 36), E(0, 0, 0)],
    [E(0, 0, 0), E(5400, 1800, 66), E(0, 0, 0), E(2400, 720, 30), E(4200, 1320, 54)],
    [E(0, 0, 0), E(4200, 1500, 48), E(2100, 600, 24), E(0, 0, 0), E(0, 0, 0)],
    [E(1200, 480, 36), E(0, 0, 0), E(3900, 960, 42), E(0, 0, 0), E(0, 0, 0)]
]

E 数据类是Edge边的缩写，表示图中的一条边，存储了多种交通方式的时间权重，其中：

driving_time 表示开车时间
train_time 表示乘坐火车时间
flying_time 表示乘坐飞机时间

adjacency_matrix 中每个元素是一个 E 的实例，比如：

E(4320, 1200, 60) 表示从城市 A 到城市 B 的开车时间是4320分钟,乘火车1200分钟,乘飞机60分钟
E(0, 0, 0) 表示城市之间这一方向没有连接

邻接表（adjacency list）

有向图

前面有向图的例子，转换成邻接表是这样：

vertex = {  
  'A': ['B'],  
  'B': ['A', 'E'],  
  'C': ['B', 'D'],  
  'D': ['B', 'C'],  
  'E': ['D'],  
}

这里的ABCDE是字符串，实际上，可以是任意Python类型，但是用作字典键时，必须是可哈希的（hash）。

这里，'C': ['B', 'D'] 的意思是C可以到达B和D，也即存在这样一条有向边。

无向图

与邻接矩阵类似，如果图是无向图，A和B之间有边，那么需要保证A中有B，B中有A。就像这样：

vertex = {  
  'A': ['B'],  
  'B': ['A'],  
}

带权图（网）

带权的形式只需用一个元组来包裹即可。这里也可以使用命名元组等方式，都可以。

# 加权邻接表
vertex = {
  'A': [(B, 10)],
  'B': [(A, 10), (C, 20)],
  'C': [(B, 20), (D, 15)],
  'D': [(B, 15), (C, 15)],
  'E': [(D, 9)], 
}

至于带多维权重等，可以通过新建一个类、命名元组等方式来实现。它的实现原理是相似的，不多赘述。

这里补充一下，如果可以保证ABCDE对象是可哈希的（hash），那么可以用作字典键，像这样：

vertex = {
  A: [(B, 10)],
  B: [(A, 10), (C, 20)],
  C: [(B, 20), (D, 15)],
  D: [(B, 15), (C, 15)],
  E: [(D, 9)], 
}

也就是直接使用对象的“引用”，不需要转换为字符串。

邻接表是重点

邻接矩阵的优点是简单、容易表示权重、检查两个顶点之间是否有边更快、更容易实现某些图算法等。

但实际生活当中，我们用得更多的是邻接表。因为：

对于存储稀疏数据来说，邻接矩阵并不高效。而现实生活中大多数情况都是比较稀疏的，邻接表就比较适合。
邻接表的很多操作的时间复杂度会更低
邻接表在程序中的操作更加灵活一些

013 图的实现