Python 数据结构入门 - 图（Graph）

图是什么

图是由一组结点和边组成的数据结构。

图的特点

一个结点通常代表一个单一的物体，在数学的图形里用一个点来代表；边用来连接两个结点，它代表着两个结点间包含某种关系，在数学图形里用可视化的线段来代表。

图的应用

• 计算机网络
  
• 路径问题，寻找最优路径
• 地图
• 约束性满足问题

图的类型

图有两种，有向图和无向图。在有向图中，所有的边都有一个箭头用来标识结点间关系的方向；在做图的遍历时，沿着箭头的方向遍历，并且不可逆。在无向图中，边没有箭头，一条边总是代表着双向的关系。

举一个生活中的例子，facebook 中的好友是无向图，twitter 中的关注者是有向图。

图的表示方法

图有两种主要表示方法。

第一种是邻接表法（adjacency list）。在邻接表中，对于图中的每个结点，我们用一个列表（list）来存储它的邻接结点。（在接下来的实现代码中，我们只考虑有向图）

在上述代码中，我们用字典生成一个推特关注者图。总共列出5个用户，对于每个用户，用一个列表跟踪存储关注者。举例来说，Jack 关注 Amy 和 Nox , Nox 没有关注任何人。

第二种表示图的方法是邻接矩阵（adjacency matrix）。邻接矩阵的行数和列数都等于结点数。对于矩阵中的每个单元，true 代表结点间存在关系，false 代表不存在关系。在 Python 中，我们可以用两级列表模拟一个这样的矩阵。