简单介绍下图及拓扑排序。

图

图（Graph）是由顶点的有穷非空集合和顶点之间的边的集合组合。

一般可以用G(V,E)来标识一个图，其中，V表示图G的顶点集合，E表示图G的边集合。

无向图：图中任意两个顶点之间的边都是无向边（顶点之间的边没有方向，则称该条边为无向边）。

连通图：所有顶点之间都是连通的无向图（顶点之间的连通允许跨多条边的路径）。

有向图：图中任意两个顶点之间的边都是有向边（顶点之间的边有方向，则称该条边为有向边）。

入度：有向图中以顶点为终点的边的个数。

出度：有向图中以顶点为起点的边的个数。

邻接矩阵

邻接矩阵（Adjaceny Matrix）是图的存储方式，由一维数组存储图的顶点集合和二维数据存储图的边集合组成。

假设图G存在n个顶点，则邻接矩阵可以表示为一个n * n的矩阵matrix，matix[i][j]代表顶点i和顶点j之间的边。

拓扑排序

在图论中，由一个有向无环图的顶点组成的序列，当且仅当满足下列条件时，称为该图的一个拓扑排序（Topological Sort）

• 每个顶点出现且只出现一次；
• 若A在序列中排在B的前面，则在图中不存在从B到A的路径。

在拓扑排序中实现方式有两种：Kahn算法和DFS深度遍历算法，算法的时间复杂度均为O(N+E)。

由于遍历存在随机性，所以拓扑排序的结果不一定唯一。

Kahn算法

以入度（或出度）为零的顶点作为遍历的开始，不断排除入度为零的顶点的所有边，不断重复此过程。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

L ← 包含已排序的元素的空列表
S ← 没有入边的顶点（入度为零的顶点）的集合
G ← 统计所有顶点的出边顶点集合（记录顶点的下级顶点）

while S 非空时：
    从S取出顶点n
    将点n从S移走
    将n加到L尾
    从G中获取顶点N的所有出边顶点集合T
    for 顶点t in 遍历顶点集合T：
        顶点t的入度减一
        if 顶点t的入度为零：
            把顶点t加入S集合
            顶点t的入度减一（此时入度=-1，不会再处理）

return L

Kahn算法可以分为无前趋的的顶点优先拓扑排序和无后继的的顶点优先拓扑排序，区别在于使用入度为零还是出度为零的边作为起点。

DFS深度遍历算法

DFS同样使用以入度为零的顶点作为遍历的开始，通过记录节点的访问状态不断遍历前置顶点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

L ← 包含已排序的元素的空列表
G ← 统计所有顶点的入边顶点集合（记录顶点的前置条件）
S ← 没有进入边的节点（入度为零的节点）的集合
V ← 所有顶点的访问记录（初始化为False）

for n in S:
    dfs(n)
    
function dfs(n)
    if 已经访问过 n in V:
        return
    记录n的访问状态 V[n] = True
    从G中找到顶点所有的出边集合T
    for t in 出边集合T：
        dfs(t)
    将n加到L尾
   
return L

在算法中，集合V是用来记录节点的访问记录，从而实现环的判断（如果已经访问的节点再次访问则一定存在环）。

常见问题

在碰到该类问题，一般需要注意几点：

• 是否存在环（循环依赖）；
• 顶点的入度和出度，不存在环的情况下，至少存在一个入度为0和一个出度为0的顶点；
• 遍历的起点一定是入度或出度为零的顶点；
• 入度和出度计算出的排序不同；
• 对于kahn算法，如果同时出现多个入度或出度为零的顶点则拓扑排序结果不唯一。

在某校的选课系统中，存在这样的规则：

• 每门课可能有若干门先修课，如果要修读某一门课，则必须要先修读此课程所要求的先修课后才能修读 （图的有向边）。
• 假设一个学生同时只能修读一门课程，那么，被选课系统允许的他修完他需要所有课程的顺序是一个拓扑序。

course-schedule
course-schedule-ii