数据结构之图

图是一种（包含若干个节点），每个节点可以连接 0 个或多个元素

两个节点相连的部分称为边（edge）。节点也被称作顶点（vertice）

一个顶点的度（degree）是指与该顶点相连的边的条数

如果所有的边都是双向的，那我们就有了一个无向图（undirected graph）。反之如果边是有向的，我们得到的就是有向图（directed graph）。可以将有向图和无向图想象为单行道或双行道组成的交通网

顶点的边可以是从自己出发再连接回自己（如蓝色的顶点），拥有这样的边的图被称为自环

图可以有环（cycle），即如果遍历图的顶点，某个顶点可以被访问超过一次。而没有环的图被称为无环图（acyclic graph）

无环无向图也被称为树（tree）

在图中，从一个顶点出发，并非所有顶点都是可到达的。可能会存在孤立的顶点或者是相分离的子图。如果一个图所有顶点都至少有一条边，这样的图被称为连通图（connected graph）。而当一个图中两两不同的顶点之间都恰有一条边相连，这样的图就是完全图（complete graph）

对于完全图而言，每个定点都有图的定点数 - 1 条边

图的应用

当图的每条边都被分配了权重时，我们就有了一个加权图（weighted graph）。如果边的权重被忽略，那么可以将（每条边的）权重都视为 1（权重都是一样，也就是无权重）

加权图应用的场景很多，根据待解决问题主体的不同，有不同的展现。一起来看一些具体的场景吧：

• 航空线路图 (如上图所示)
  • 顶点 = 机场
  • 边 = 两个机场间的飞行线路
  • 权重 = 两个机场间的距离

• GPS 导航

  • 顶点 = 交叉路口
  • 边 = 道路
  • 权重 = 从一个路口到另一个路口所花的时间

• 网络

  • 顶点 = 服务器
  • 边 = 数据链路
  • 权重 = 连接速度

图在现实世界中的应用有：

• 电子电路
• 航空控制
• 行车导航
• 电信设施： 基站建设规划
• 社交网络： Facebook 利用图来推荐（你可能认识的）朋友
• 推荐系统： Amazon/Netflix 利用图来推荐产品与电影
• 利用图来规划物流线路

图的表示有两种主要方式：

1. 邻接表
2. 邻接矩阵

按照图的存储结构分为 完全图，连通图、稀疏图和稠密图