graph

图论

图论（Graph theory）是数学的一个分支，它以图为研究对象，研究顶点和边组成的图形的数学理论和方法。

定义

图（graph）G=(V, E)由顶点（vertex）集V和边（edge）集E组成。每一条边是一个点对(v, w)，其中v, w ∈ V。有时也把边称作弧（arc）。

如果点对是有序的，那么叫做有向图（digraph）。

顶点v和w邻接（adjacent）当且仅当(v, w) ∈ E。在一个具有边(v, w)从而具有边(w, v)的无向图中，w和v邻接且v也和w邻接。边可能有权（weight）或值（cost）。

一些基本概念

1. 有向图和无向图：

   (v, w) 表示无向边，即 v 和 w 是互通的。

   <v, w> 表示有向边，该边始于 v，终于 w。

2. 有权图和无权图：

   有权图：每条边具有一定的权重(weight)，通常是一个数字。

   无权图：每条边均没有权重，也可以理解为权为1。

3. 连通图和非连通图：

   连通图：所有的点都有路径相连。

   非连通图：存在某两个点没有路径相连。

4. 顶点的度：

   度(Degree)：所有与这个顶点连接的点的个数之和，也就是这个顶点边的总数。

   入度(Indegree)：有向图中，指向这个顶点的边数。

   出度(Outdegree)：有向图中，从这个顶点发出的边数。

图的表示

图的表示主要有两种方法。假设图为：

邻接矩阵（Adjacency-Matri）

• 有 n 个顶点的图需要有一个 n × n 大小的矩阵；
• 在一个无权图中，矩阵坐标中每个位置值为 1 代表两个点是相连的，0 表示两点是不相连的；
• 在一个有权图中，矩阵坐标中每个位置值代表该两点之间的权重，0 表示该两点不相连；
• 在无向图中，邻接矩阵关于对角线对称。

则上图可表示为：

  1 2 3 4 5
1 0 1 0 1 0
2 0 0 1 0 1
3 1 0 0 0 0
4 0 0 0 0 0
5 0 0 1 1 0

显然，可以很容易得到一个顶点的入度和出度。邻接矩阵中第i行元素个数的和即为第i个顶点的出度，第i列元素的和即为第i个顶点的入度。

缺点

1. 没有存储图中顶点的数据条目，只记录了编号，这个可以通过外加一个1维数组记录解决；
2. 表示的稀疏性。会有很多多余的0元素，浪费大量的空间。

邻接链表（Adjacency-List）

• 对于每个点，存储着一个链表，用来指向所有与该点直接相连的点；
• 对于有权图来说，链表中元素值对应着权重。

则上图可表示为：

1 --> 2 --> 4
2 --> 3
3 --> 1
4
5 --> 3 --> 4

邻接矩阵由于没有相连的边也占有空间，因此存在浪费空间的问题，而邻接链表则比较合理地利用空间；

缺点

邻接链表比较耗时，需要更多的时间来查找，而邻接矩阵法相比邻接链表法来说，时间复杂度低。

搜索和遍历

图的遍历就是要找出图中所有的点，一般有以下两种方法。

深度优先搜索（Depth First Search, DFS）

从图中某顶点 v 出发:

1. 访问起始顶点 v；

2. 对于每个 v 的邻接点w做以下工作：

   如果 w 未被访问，将 w 作为起始顶点，应用深度优先搜索算法。

广度优先搜索（Breadth First Search, BFS）

1. 访问起始顶点；
2. 初始化一个队列为仅包含起始顶点；
3. 当这个队列为非空时，做以下工作：

   1. 从队列删除一个顶点v；

   2. 对于所有邻接于v的顶点w，做以下工作：

      如果w未被访问，则：

      • 访问w；
      • 将w添加到队列中。

最短路径算法（Shortest Path Algorithm）

寻找一个有向图中从一个起始顶点start到一个目的顶点destination之间一条最短路径。显示从start到destination的一条最短路径上的所有顶点。如果从start无法到达destination，则给出一条提示信息。

1. 访问start，并将其标签置为0；

2. 初始化distance为0；

3. 初始化一个队列为仅包含start；

4. 当destination还未被访问并且队列非空时，做以下工作：

   1. 从队列删除一个顶点v；

   2. 如果v的标签大于distance，将distance增1；

   3. 对于邻接于v的每一个顶点w：

      如果w还未被访问，则：

      • 访问w，并将其标签置为distance＋1；
      • 将w添加到队列中。

5. 如果destination还未被访问，则：

   显示 “从起始顶点无法到达目的顶点”

   否则，如下查找最短路径中的顶点p[0], ..., p[distance]:

   1. 初始化p[distance]为destination；

   2. 对于从distance-1～0的每一个值k：

      找到邻接于p[k+1]并且标签为k的一个顶点p[k]。