1 概述

图是数据结构中最复杂的形式，也是最烧脑的结构。无数的牛人乐此不疲地钻研，然而，时至今日，依然有很多问题等着童鞋们去解决。为什么图重要，下面以两个简单的例子进行说明：

• 银行转账超过10000，要24小时后到账，为什么？本人猜测：因为后台服务器要计算这笔转账是否涉嫌诈骗、洗钱，交易是在一张超级巨大的图上（每个账号是图中一个节点），服务器计算的重点是图中是否存在某个强连通图或者某个节点在某个时间点入度特别大等等。因为计算需要时间较长，无法在几分钟内算完，所以要求24小时延迟也是正常的；
• 间友圈价值再发现。没错，就是我们现在写作的平台，通过间友之间的关注、收藏、阅读等，能迅速组成一张图，通过这张图，可以很快计算出谁是最受欢迎的作者，谁的粉丝最多，谁的文章最受欢迎，谁是通过不正常手段获取的粉丝等等...

图计算的地位在最近的机器学习领域日益体现，tensorflow等深度学习框架无一不是基于图计算的，图计算中最基础的当属图的表示和图的遍历。本文剩余部分介绍图的表示和两个最基本的遍历算法（广度遍历、深度遍历）并对算法本身进行分析说明。（算法实现地址：https://github.com/bjutJohnson/Algorithms/tree/master/src/graph ,请查阅）

2 图的表示

与其它基本的数据结构不同，图的表示较为复杂。在图中，存在两类元素，一类是节点元素，一类是边元素。在具体工程实践中，每个节点可能包括一系列属性，如过用一个节点表示人，则其属性可能包括身份证号、年龄、性别等；每条边也可能包括一系列属性，针对人，边的属性可能包括亲戚、朋友、同事等关系。在具体的工程项目中，通常都会给每个节点和边赋予唯一的ID，在此基础上进行一系列的计算。

具体而言，图的表示可以有两种方法，一种是矩阵表示法，一种是邻接表法，其对应的例子如下图所示：

图1:图的表示方法

图1中的b是邻接表法，c是矩阵表示法。从两种表示方法的形式上看，当图中的边比较稀疏时，用邻接表法表示更节省空间，但是判断特定的顶点对是否存在边，需要搜索邻接表对应的线性表，比较费事；当图中的边比较密集时，用矩阵表示法比较合适，判断特定的顶点对是否存在边，直接取值判定即可，效率较高。当前，随着存储空间越来越便宜，机器学习深度学习等算法中通常采用矩阵表示方法，用空间换取时间。在本文中，我们一般用邻接表方法来表示图。图的表示的具体代码分为，图节点表示、边表示、图表示，分别如下所示：

// 定义图节点文件
type GraphNode struct {
    id    int   // 节点唯一标识
    edges []int // 标识邻接边的编号
    color int8  // 标识是否访问

    feature map[string]interface{} // 定义图节点本身的属性，以key-value的形式提供，用户负责转换，另一种方案是使用reflect
}

// 定义图上的边
type GraphEdge struct {
    id       int                    // 唯一标识符
    from     int                    // 出节点
    to       int                    // 入节点
    features map[string]interface{} // 边上的各种属性，暂时可能用不着
}

// 管理图的所有节点
type GraphManager struct {
    id2Node map[int]*GraphNode // 以map的形式记录所有的节点
    id2Edge map[int]*GraphEdge // 以map的形式记录所有的边

    nodeCounter int // 计数器，申请的图节点数量
    edgeCounter int // 边计数器

    isDirection bool // 有向图还是无向图，必须初始时给定

    lockChan chan bool // 控制对管理对象的操作，一个时刻只能有一个goroutine对其进行修改

    logicTime int // 用于控制深度遍历时的逻辑时钟，只表示先后关系，如t0=0, t1=1表示t1是紧邻t0的下一个时刻
}

3 图的遍历

与树结构中存在先序遍历、中序遍历、和后序遍历一样，在图中存在广度遍历和深度遍历两种方式，这两种方式几乎是所有图计算的最基础部分，其重要性不言而喻。

3.1 广度遍历

广度遍历的概念比较容易理解，其语义为：针对当前节点v，先遍历所有t的所有未访问的邻接节点{v₁,v,v₂, ... v_m}，然后再以此以{v₁,v,v₂, ... v_m}中的元素为当前节点，递归进行，直至所有的节点都遍历完毕。下面的图可能更容易表示广度遍历的过程：

图2:广度遍历图示，摘自算法导论

图2中是以s点为源节点开始进行广度遍历，初始时，所有的节点涂成白色，遍历过程中，当第一次发现节点时，将节点涂灰，当节点的所有邻接节点都发现后，将节点涂黑，图中节点类的数据表示节点与源节点之间的最短距离（这个需要分析说明）。

试证明：广度遍历的结果是各节点与源节点的最短距离

证明（数学归纳法），假设求节点v与源节点s的最短距离
1）当v与s相邻时，其最短距离必然为1，广度遍历得到的值显然为1，结论成立；
2）当v与s相距k时，假设广度遍历得到的值最短距离为k；
3）当v与s相距k+1时，必然存在一个节点v'与v距离为k，v'与s相邻，根据广度遍历算法过程，在访问到v'之后，必然再下一轮会访问到v，因此得到的必然是k+1；

如果觉得上述分析比较啰嗦，可以观察图2，广度遍历就是逐层往外扩散遍历的过程，得到的是一颗广度优先树，如下图所示：

图3: 广度优先树

根据上面的进程，广度遍历的算法实现思路如下：

摘自算法导论

（具体的实现请详见 https://github.com/bjutJohnson/Algorithms/blob/master/src/graph/graph_manager.go 中的BFS函数，可能实现与上面的算法有些不一致。）算法借助一个队列，首先，将源节点s入队列，然后，进入循环，在队列不为空的前提下，从队列中取出一个元素v（11行），然后访问其所有未访问的邻接节点(12-17行)将其涂灰，并将未访问的节点入队列，当v的所有邻接节点访问完成之后，将自身涂黑。

节点为白色，表示节点未被发现，节点为灰色时，表示节点已被防线，且已被加入到队列中，当节点为黑色时，表示节点已出列，并且其所有邻接点已被发现。从算法中，可以看出一个节点均只有一次涂白，一次涂灰和一次涂黑的机会。

其时间复杂度直接分析遍历的过程，有N个节点、M条边，访问节点必然是O(M),通过连接表发现相邻节点必然是O(N)，因此，其时间复杂度必然为O(M+N)

3.2 深度遍历

与广度遍历对应最短路径不同，深度遍历更多地用于拓扑排序、强连通分量发现等。深度遍历的语义是：总是对最近发现的节点v出发的边进行探索，如果v的所有边都已探索完毕，则回溯至其上层节点p（v是p的邻接节点，由p发现v），进一步探索p的其它未遍历的邻接节点，若p的所有邻接节点已探索完毕，则回溯至p的上层节点继续探索，直至所有的节点都探索完毕。

说起来也是很啰嗦，看如下图示：

图4: 深度遍历图示，摘自算法导论

图中节点标识的m/n，其中m表示节点发现的逻辑时间，n表示其所有的邻接节点都被访问的时间，简单描述如下：

• （a）首先u被发现，u涂成灰色；
• （b）探索u的邻接节点，发现了v，v涂成灰色；
• （c）进一步探索v的邻接节点，发现了y，y涂成灰色；
• （d）探索y的邻接节点，发现了x，x涂成灰色；
• （e）尝试探索x的邻接节点y，发现y已发现；
• （f）x的所有的邻接节点都已访问，回溯至y；
• （g）y的所有邻接点都已访问，回溯至v；
• ...

其对应的算法为：

深度优先算法，摘自算法导论

下面对节点的发现时间和邻接节点都被发现的时间进行分析（对于后面的拓扑排序、强连通分量非常重要）。假设深度遍历过程中得到的节点相关时间为：x(m1/n1), y(m2/n2),不妨取m2 > m1，则以下二者必然有一个成立：

• m1 < m2, n1 > n2
• n1 < m2

证明：
1）若x是y的上层节点（或距离更远的上层节点），根据深度优先遍历算法，m1 < m2肯定成立，当y的所有邻接点都访问结束时（此时才对n2赋当前逻辑时间值），然后，一直向上层回溯至x，x遍历完所有的邻接节点才会结束（此时才对n1赋当前逻辑时间值），根据时间先后的描述，显然有：m1 < m2, n1 > n2；如图4中的节点u, v, y, x
2）若x不是y的上层节点，则必然是通过x无法访问到y，要访问y，必然是通过算法中的第5行，从其中选择的y，在此之前，x的上层节点和下层节点，必然都已经访问完毕，而y还未被访问，因此，必然有n1 < m2，如图4中的u和w

通常情况下，深度优先算法中的第5行中选择一个节点开始遍历时，对应此节点的一棵深度优先树（这更多的是从后续使用的角度来说明，对于有向树来说，容易理解，对于无向树而言，必然是一颗树），因此，通常将有向图深度优先遍历的结果表示成一个森林（因为是多棵树）。如下图所示：

图5: 有向树的深度遍历

对于图中的边，根据与优先遍历生成树的边之间的关系，图中的边可以分为：

• 树边：深度优先图过程中，生成的树中的边，如图5（c）中的涂阴影的边均为树边；
• 后向边：如图5（c）中标识为B的边，其产生的原因是，在深度遍历中，x是y的上层节点，而在访问y时，发现其有指向x的边，这一类边称为后向边；
• 前向边：如图5（c）中标识为F的边，其产生的原因是：在深度遍历中，x是y和z的上层节点，y是z的上层节点，在发现x后，优先访问y，通过y又访问到z，则(x, y)和（y, z）是树边，但是(x, z)则不是树边，这种边称为前向边；
• 横向边：不是上述3类的边称为横向边。

在理解了上述定义，可以得出如下结论：

试证明：在对无向图G进行深度优先搜索时，每条边要么是树边，要么是后向边。

证明：前面已经分析过，如果无向图中没有孤立节点或孤立节点集合（那样是多个图，而非一个图），即从一个节点出发，必然可以深度遍历访问所有的节点（也就是说算法中的第5行中的循环只进入一次），在访问过程中，如果访问节点x时，通过x的邻接表发现y，则y必然是树边；如果访问节点x时，如果x邻接表为空，则开始回溯，从x的上层节点到x的边必为树边，如果x的邻接表非空，但其邻接节点y已访问，则y必然是x的上层节点（有可能有几层），因此，从x到y的边必然为后向边。不可能存在其它情况，因此，结论成立。

4 小结

本文讲解了图的基本表示和两个基本的遍历算法，其中也伴有一些简单的分析。图是最考验思考能力的一种形式，其对应的算法也最难，后续课程将会针对图进一步分析讲解。