基本图算法介绍

---

前言

由于图论问题渗透整个计算机科学，图算法对于计算机学科至关重要。成百上千的计算问题最后都可以归约为图论问题。本系列文章对《算法导论》一书中谈及的一些重要图论问题的相关知识进行汇总整理。本篇讲述图的搜索问题，图的搜索指的是系统化地跟随图中的边来访问图中的每个结点。图搜索算法可以用来发现图的结构。许多的图算法在一开始都会先通过搜索来获得图的结构，其他的一些图算法则是对基本的搜索加以优化。可以说，图的搜索技巧是整个图算法领域的核心。

---

一、图的表示

对于图G=（V，E），可以用两种标准表示方法表示。一种表示法将图作为邻接链表的组合，另一种表示法则将图作为邻接矩阵来看待。两种表示方法都既可以表示无向图，也可以表示有向图。

对于矩阵表示来说，它所需要的存储空间为 |V²|，可见在顶点数较多时，其所需的空间会急剧增长，并且当图为稀疏图（边很少）时，会存在较大的空间浪费。但是它的优势在于访问边的速度极快，可以在O（1）的时间内快速判断两个顶点之间是否存在边。因此在顶点数量较少，需要快速访问边的，以及图为稠密图时适合使用矩阵表示法。对于无向图的很多问题，由于边的对称性，我们可以通过矩阵转置的方法，仅使用矩阵的上三角，这样可以节省下一半的存储空间。

对于邻接表表示来说，在存储无向图时其所需的空间为|V|+2|E|，在存储有向图时为|V|+|E|，可见它所需的空间比矩阵表示小很多，但由于采用链表结构存储邻接点，访问性能较差，可以通过一些变种数据结构（如十字链表）来优化。

下面是使用两种表示法存储有向图与无向图的例子：

以下以邻接表表示法为例给出其代码示例：

 //图算法public class Graph{public Node[] nodes = null;/// <summary>/// 是否为有向图/// </summary>public bool IsDirect { get; }public Graph(int vcount, bool isDirect=false){nodes = new Node[vcount];for (int i = 0; i < nodes.Length; i++){nodes[i] = new Node();nodes[i].ID = i;}IsDirect = isDirect;}/// <summary>/// 根据传入顶点的命名数组构造图/// </summary>/// <param name="v"></param>/// <param name="isDirect"></param>public Graph(string[] v, bool isDirect=false){nodes = new Node[v.Length];for (int i = 0; i < nodes.Length; i++){nodes[i] = new Node();nodes[i].ID = i;nodes[i].Name = v[i];}IsDirect = isDirect;}public Graph(Node[] v,bool isDirect=false){nodes = v;IsDirect = isDirect;}/// <summary>/// 添加边/// </summary>/// <param name="from"></param>/// <param name="to"></param>public void AddEdge(int from,int to){nodes[from-1].AddAdjNode(nodes[to-1]);if (!IsDirect){nodes[to - 1].AddAdjNode(nodes[from - 1]);}}/// <summary>/// 节点颜色表示某种状态/// </summary>public enum NodeColor{//白色表示尚未被发现White,//灰色表示已发现但尚未处理完成的节点Gray,//黑色表示已经处理完成Black}/// <summary>/// 图节点/// </summary>public class Node{/// <summary>/// 顶点名字/// </summary>public string Name { get; set; }public int ID { get; set; }public NodeColor color=NodeColor.White;//邻接表public List<Node> AdjList = new List<Node>();//距离(默认为无穷大)public int Distance { get; set; } = int.MaxValue;//父节点public Node Parent { get; set; }/// <summary>/// 发现时间/// </summary>public int d { get; set; }/// <summary>/// 结束时间/// </summary>public int f { get; set; }public void AddAdjNode(Node node){if (!AdjList.Contains(node)){AdjList.Add(node);}}}
}

二、广度优先搜索

广度优先搜索（BFS）是最简单的图搜索算法之一，也是许多重要的图算法的原型。Prim的最小生成树算法和Dijkstra的单源最短路径算法都使用了类似广度优先搜索思想。

BFS的思路大致是这样，从原点s开始，首先将s标记为已发现并压入队列，搜索s的所有邻接点，当发现这个节点尚未发现（未被标记），则将其压入到队列中，并将其标记，当s的所有邻接点都被探索过之后，将s从队列中移除，从队列中取出一个继续上述操作，直到队列为空。

执行过程中，BFS会首先搜索所有与s相距为1的点，然后再搜索与s相距为2的点，以次类推，这也是广度优先的由来。

为了描述算法执行过程，我们给节点赋予不同颜色来表示节点的不同状态，当节点为白色时，表示节点尚未被搜索到，为灰色时表示节点已被发现，但是其邻接点尚未被探索完，为黑色时表示节点已被发现且其所有邻接点也以探索。这里灰色其实表示已被发现的节点与未被发现节点的边界节点，队列中自始至终存放的是这些灰色节点。需要注意灰色这种状态在实际算法实现中并没有什么用处，实际算法中只需要区分两种状态，要么已发现，要么未发现，我们这里只是为了描述清楚过程。

可以证明算法的时间复杂度为O（V+E）。

算法执行过程中，会生成一颗广度优先树，它会记录s到所有节点的距离以及路径（通过记录父节点），可以证明这些点到s的路径都是其到s的最短路径。通过这颗树，我们可以打印出s到任意节点的路径

BFS通常用于寻找从特定原点出发的最短路径距离及相关的前驱子图。

下面给出BFS的代码实现：

/// <summary>
/// 广度优先搜索
/// </summary>
/// <param name="g">图</param>
/// <param name="s">起始点</param>
public static void BFS(Graph g,Node s)
{//用于存储边界节点Queue<Node> q = new Queue<Node>();//初始化所有节点foreach (var v in g.nodes){v.color = NodeColor.White;v.Distance = int.MaxValue;v.Parent = null;}//初始化起始点s.color = NodeColor.Gray;s.Distance = 0;s.Parent = null;q.Enqueue(s);while (q.Count>0){var node = q.Dequeue();foreach (var adjNode in node.AdjList){//如果节点尚未发现标记为灰色if (adjNode.color==NodeColor.White){adjNode.color = NodeColor.Gray;adjNode.Parent = node;adjNode.Distance = node.Distance + 1;//加入到待处理队列中q.Enqueue(adjNode);}}//探索完所有邻接点标记为黑色node.color = NodeColor.Black;}
}

进行过BFS之后，便会得到一颗广度优先树，可以用其打印路径，代码示例如下：

/// <summary>
/// 打印起始点到顶点v的路径
/// </summary>
/// <param name="s">起始点</param>
/// <param name="d">目标点</param>
/// <param name="c">当前点</param>
public static void PrintPath(Node s,Node d,Node c)
{if (s==c){Console.Write($"{s.Name}-->");return;}if (c.Parent==null){Console.WriteLine($"顶点{s.Name}与{d.Name}不可达");return;}PrintPath(s,d,c.Parent);if (c==d){Console.Write($"{c.Name}");}else{Console.Write($"{c.Name}-->");}
}

以下是算法执行的一个示例演示：

三、深度优先搜索

注意这里与BFS的区别，在BFS中只存在一个s原点，而在DFS中，当搜索完成后若发现还有白色节点，会接着对这些节点应用DFS。为什么会存在这样的区别，是因为两者的用途不同，DFS算法通常作为其他图算法的子算法存在，这些算法利用DFS算法得出图的全部的构成信息。

同BFS一样，DFS也使用三种节点颜色表示不同状态，但除此之外，它还会给每个节点盖上时间戳，一个是在刚发现节点时（涂上灰色时）的时间d，一个是探索完成时（涂上黑色时）的时间f。这些时间戳提供了图结构的重要信息，通常能够帮助推断深度优先搜索算法的行为。

DFS执行的结果依赖于算法对节点检查的次序，以及对邻接点检查的次序。但这通常不会产生问题，我们会对这些结果有效利用产生等价结果。关于这一点在后面会再次说明。

下图是一个DFS执行过程的一个示例：

可以证明DFS的时间复杂度为O（V+E）。

上述是括号化定理定义，及示例。图b显示了其括号化结构，有点类似于函数调用栈。

这条定理可用于判断节点v是否是节点u的后代。也可以反过来用，在发现u时，u的后代此时都是白色。

有了边的分类概念，就可以回过来看图c，它是图a的重画，这种画法中，每颗深度优先树并列，前驱节点都在上面，后继节点都在下面，这种画法使得前向边始终朝下，后向边始终朝上。

那么，如何判断一条边究竟是什么边？

注意这里树边与横向边概念上可能混淆，同样的一条边有时可能是树边，有时可能是横向边，取决于节点检查顺序。举个例子，对于图A–》B–》C–》D，如果一开始选择A作为BFS的起点，那么B–》C这条边会作为树边，如果开始以C为起点，得到一颗深度优先树C–》D，然后算法继续，这次选择A作为起点，得到另一颗树A–》B，此时会产生两颗不同的树，而边C–》D跨越两颗树，此时它是横向边。如果是第二种情况，那么A的发现时间与结束时间就无法涵盖C，但是能够保证的是，A的结束时间一定是大于C的，及排在前的结束时间一定是大于排在后的。

如果是上述第三种情况，还需要进一步判断到底是前向边还是横向边，判断的依据为如果边(u，v)在u.dくv. d时为前向边，在u.d>v.d时为横向边。

这条定理应该也好理解，因为存在前向边或横向边，那么在进行深度搜索时必然会将这些边识别为后向边。因此前向边与横向边仅针对有向图而言。

下面给出DFS的代码示例：

/// <summary>
/// 深度优先搜索
/// </summary>
/// <param name="g"></param>
public static void DFS(Graph g)
{//全局时间计数器int time = 0;//初始化所有节点foreach (var v in g.nodes){v.color = NodeColor.White;v.Parent = null;v.d = int.MinValue;v.f = int.MinValue;}//遍历所有节点，得到多颗深度优先树foreach (var v in g.nodes){if (v.color==NodeColor.White){_DFS(v);}}void _DFS(Node u){u.d = ++time;u.color = NodeColor.Gray;foreach (var v in u.AdjList){//如果节点尚未探索if (v.color==NodeColor.White){v.Parent = u;_DFS(v);}}u.color = NodeColor.Black;u.f = ++time;}
}

测试代码对应上面的示例：

            var v = new string[] { "u", "v", "w", "x", "y", "z" };var g = new Graph(v, true);//添加边g.AddEdge(1, 2);g.AddEdge(1, 4);g.AddEdge(4, 2);g.AddEdge(2, 5);g.AddEdge(3, 5);g.AddEdge(3, 6);g.AddEdge(5, 4);g.AddEdge(6, 6);Graph.DFS(g);foreach (var node in g.nodes){Console.WriteLine($"顶点{node.Name}，  {node.d}/{node.f}");}

四、深度优先搜索应用

1.拓扑排序

更进一步抽象，拓扑排序就是在处理节点之间的依赖关系，使得被依赖的一方始终排在依赖的一方的前面，而图中的每条边就对应一条依赖，如A–》B表示B依赖于A，如GC的根可达算法，包管理器对依赖包的管理等就是拓扑排序的应用。

这是一个拓扑排序的示例，会发现其拓扑排序是按照节点的结束时间的逆序进行排序。前面我们说过，对于A–》B，DFS可以保证A.f>B.f始终成立，虽然A.d<B.d不一定始终成立，好在拓扑排序只依赖结束时间。所以要使的被依赖的一方始终排在前面，就需要根据f逆序排序。

这条定理应该很好理解，拓扑排序仅对DAG（有向无环图有意义），如果一个图有环，那无论如何也不可能排出一个合理的次序，通过这条定理，我们可以判断有向图中是否存在环路。

下面给出拓扑排序的代码实现：

/// <summary>
/// 拓扑排序
/// </summary>
/// <param name="g">待排序的图</param>
/// <param name="allowBack">是否允许存在后向边(有环)</param>
/// <returns>返回拓扑序的链表</returns>
public static LinkedList<Node> TopoLogicSort(Graph g,bool allowBack=false)
{if (!g.IsDirect){Console.WriteLine("只可对有向图进行拓扑排序");return null;}LinkedList<Node> list = new LinkedList<Node>();//全局时间计数器int time = 0;//初始化所有节点foreach (var v in g.nodes){v.color = NodeColor.White;v.Parent = null;v.d = int.MinValue;v.f = int.MinValue;}//遍历所有节点，得到多颗深度优先树foreach (var v in g.nodes){if (v.color == NodeColor.White){try{_DFS(v);}catch (Exception e){Console.WriteLine(e.Message);//return null;}}}return list;void _DFS(Node u){u.d = ++time;u.color = NodeColor.Gray;foreach (var v in u.AdjList){//如果节点尚未探索if (v.color == NodeColor.White){v.Parent = u;_DFS(v);}if (v.color==NodeColor.Gray&&!allowBack){throw new Exception($"检测出有向图存在环，后向边为{u.Name}-->{v.Name}");}}u.color = NodeColor.Black;u.f = ++time;list.AddFirst(u);}
}

代码与DFS代码差不多，只是在其基础上稍加改进。

测试代码，使用上述图中示例：

            var v = new string[] { "内裤", "袜子", "手表", "裤子", "鞋", "腰带", "衬衣", "领带", "夹克" };var g = new Graph(v, true);//添加边g.AddEdge(1, 4);g.AddEdge(1, 5);g.AddEdge(2, 5);g.AddEdge(4, 5);g.AddEdge(4, 6);g.AddEdge(7, 6);g.AddEdge(7, 8);g.AddEdge(8, 9);var list = Graph.TopoLogicSort(g);foreach (var node in list){Console.WriteLine($"顶点{node.Name}，  {node.d}/{node.f}");}

运行代码会发现结果与图中示例不太一样，并非算法错误，而是由于对节点检查顺序不同所导致，两种结果都是正确的，我们只需关注，被依赖的一方始终在前即可。这便是前面所讲的DFS的次序不影响最终结果的体现。

2.强连通分量

强连通分量指分量中任意两点之间都可互相到达（对有向图而言）。

对于图a中的每块阴影就是一个强连通分量。

要解释这一算法，我们需要先了解几个概念。

图的转置，指将图中所有的边进行反转。转置前后图中的强连通分量不会产生变化。如上述图b就是图a的转置。

分量图指将一个分量中的所有节点放在一个大的节点中，收缩其边，只保留分量之间相连的边，如图c就是图a的分量图。分量图有一个关键性质，即它一定是DAG。分量图之间一定是单向连通的。

这条引理说明，如果分量A能够到达B，那么f(A)>f(B)一定成立，因为分量a可以沿着边ab到达分量b的任意节点。

有了上述的一些概念后，我就可以对算法进行非正式的证明。我们首先需要对输入的图进行一次拓扑排序，得到一个按节点f逆序排序的图，再对此图进行一次转置操作，如图b，想象此时图c分量图中的边翻转的样子，原先分量图中连通走向全部翻转过来了，此时再对这个转置后的新图进行DFS，可以断言，所得到的每个深度优先树是一个强连通分量。

因为根据引理22.14可以通向其他分量的分量在经过第一次拓扑排序后必然排在其他分量之前。此时对图进行了转置，而分量图又是DAG的，那么原先可连通到其他分量的分量将不再能够连通，对此图做DFS，可以保证每颗树在进行DFS时，该树能够到达的其他分量必然已经DFS结束了，即其节点是黑色的。也就是说这颗树的所有后代（根据白色路径定理可知是这棵树中的所有白色节点）就是一个SCC（强连通分量），不可能包含其他未DFS的SCC的节点（分量图被转置了）。

讲清楚算法原理，下面给出代码实现：

/// <summary>
/// 计算有向图的强连通分量
/// </summary>
/// <returns>返回强连通分量列表</returns>
public static List<List<Node>> StrongConnectedComponents(Graph g)
{if (!g.IsDirect){Console.WriteLine($"只可计算有向图强连通分量");return null;}//首先对图拓扑排序var list = TopoLogicSort(g,true);var newg = new Graph(list.ToArray(),g.IsDirect);//对拓扑排序后的图进行转置var TranspoeG = Transpose(g);return GetSCC(TranspoeG);
}
static List<List<Node>> GetSCC(Graph g)
{//强连通分量列表List<List<Node>> SCCList = new List<List<Node>>();//全局时间计数器int time = 0;//初始化所有节点foreach (var v in g.nodes){v.color = NodeColor.White;v.Parent = null;v.d = int.MinValue;v.f = int.MinValue;}//遍历所有节点，得到多颗深度优先树foreach (var v in g.nodes){if (v.color == NodeColor.White){SCCList.Add(new List<Node>());_DFS(v);}}return SCCList;void _DFS(Node u){u.d = ++time;u.color = NodeColor.Gray;foreach (var v in u.AdjList){//如果节点尚未探索if (v.color == NodeColor.White){v.Parent = u;_DFS(v);}}u.color = NodeColor.Black;u.f = ++time;//将探索到的节点添加到当前分量中SCCList[SCCList.Count-1].Add(u);}
}
/// <summary>
/// 转置图
/// </summary>
/// <param name="g"></param>
/// <returns></returns>
public static Graph Transpose(Graph g)
{var newg = new Graph(g.nodes.Length,g.IsDirect);//初始化节点名称for (int i = 0; i < g.nodes.Length; i++){newg.nodes[i].Name = g.nodes[i].Name;}//初始化边for (int i = 0; i < g.nodes.Length; i++){foreach (var adjv in g.nodes[i].AdjList){//反转边newg.AddEdge(adjv.ID+1,i+1);}}return newg;
}

注意其中调用拓扑排序时，参数允许后向边应填true，因为强连通分量必然存在环。

测试代码如下：

var v = new string[] { "a","b","c","d","e","f","g","h" };
var g = new Graph(v, true);
//添加边
g.AddEdge(1, 2);
g.AddEdge(2, 3);
g.AddEdge(3, 4);
g.AddEdge(4, 3);
g.AddEdge(5, 1);
g.AddEdge(2, 5);
g.AddEdge(2, 6);
g.AddEdge(3, 7);
g.AddEdge(4, 8);
g.AddEdge(5, 6);
g.AddEdge(6, 7);
g.AddEdge(7, 6);
g.AddEdge(7, 8);
g.AddEdge(8, 8);var list = Graph.StrongConnectedComponents(g);foreach (var scc in list)
{Console.WriteLine($"强连通分量：{string.Join(",",scc.Select(x=>x.Name))}");
}

总结

本文对图的搜索算法及其应用相关知识进行了总结。