前言图算法对计算机学科很重要。 数百个计算问题最终可以归结为图论问题。 本章主要说明图的显示和图的检索。
对于图g=(v，e )，图的显示可以用两种标准的显示方法来表示。
在表示稀疏图(边数|E|远远小于3v32|v|^23v32的图)时，相邻链表非常紧凑，因此成为通常的选择。 邻接矩阵在密度图((e|接近) v )2|v|) v ) 2的图)时，倾向于该表示法。 相邻链表由包含|V|链表的数组Adj组成，每个节点都有一个链表。 对于每个节点，相邻链表Adj[u]包含与节点u之间有边的所有节点v。 也就是说，Adj[u]包含与图表g中所有u相邻的节点。
相邻链表的表示法也有潜在的缺点，就是不能快速判断一条边(u，v )是否是图中的一条边。 唯一的方法是在Adj[u]中搜索v节点。 相邻矩阵解决了客户服务的这个缺陷，但成本是更大的存储空间。 对有向图来说，邻接矩陈还有另一个优点。 最初的条目对于图表g只需要1位空间宽度优先搜索。 宽度优先搜索算法必须发现源节点s到k的所有节点，然后发现源节点s到k 1的其他节点。
# u.d记录通过宽度优先搜索算法计算出的从源点s到节点u的距离。 # u.记录u的前驱节点。 BFS(g， s ) foreachvertexug.v-{ s } u.color=whiteu.d=d .=nils.color=gray u.d=0d .=nilq=enil=u=ded ifv.color==whitev.color=grayv.d=u.d1v .=u enqueue ) q，v ) u同时，该算法为广度优先树以下代码将
print-path(g，s，v ) ifv==sprintselseifv .==nil print“nopathfrom”s“to”v“exists”else print-path ) g，
# u.d表示u节点开始搜索的时间，# u.f表示u节点结束搜索的时间DFS(G )，foreachvertexug.vu.color=whiteu .=nil time=0foreache u ) Disit ) ) d u ) time=time1//whitevertexuhasjustbeendiscoveredu.d=timeu.color=grayforeachvg.adj [ u ]/(Exploreedge () Exploreedge () ) ) 65 v ) ifv.color==whitev .=UDFs-visit (g，v ) u.color=black///
深度优先搜索的性质深度优先搜索生成的前体图可能由多个树组成，因为搜索可能从多个源节点重复。 也就是说
trong>深度优先森林。深度优先搜索的一个重要特性是发现和完成时间具有括号结构。
图b是图a根据发现时间和结束时间的时序
对于图G,根据发现结速时间，总结三大性质：
性质1：在对有向图或无向图G = (V, E)进行的任意DFS过程中，对于任意两个节点u和v来说，下面三种情况只有一种成立： a：区间[u.d, u.f]和区间[v.d, v.f]完全分离，在深度优先森林中，节点u不是节点v的后代，节点v也不是节点u的后代。b：区间[u.d, u.f]包含在区间[v.d, v.f]中，在深度优先树中，节点u是节点v的后代。c：区间[v.d, v.f]包含在区间[u.d, u.f]中，在深度优先树中，节点v是节点u的后代。 性质二：在有向或无向图G的深度优先森林中，节点v是节点u的真后代当且仅当u.d < v.d <v.f < u.f成立。性质三：在有向或无向图G = (V, E)的深度优先森林中，节点v是节点u的后代，当且仅当在时间u.d，存在一条从节点u到节点v的全部由白色节点所构成的路径。 边的分类深度优先搜索的另一个有趣的性质是，可以通过搜索来对输入图G=（V, E）的边进行分类：
树边：为深度优先森林Gπ中的边。如果结点v是因算法对边(u, v)的探索而首先被发现，则(u, v)是一条树边。前向边（上图灰色虚线）：从某个点到它的某个子孙节点的边。这种边相当于提供某种“捷径”，在这个问题里不太重要，即使把它们全部删去，对于连通性也没什么影响。后向边（上图绿色虚线）：从某个点到它的某个祖先节点的边。这种边就是产生环的原因，如果删去所有反向边，那么原图会成为有向无环图。横叉边（上图蓝色虚线）：从某个点到一个既非它子孙节点、也非它祖先节点的边。这种边本身不产生环，但是它可能把两个强连通子图“连接”起来，形成一个更大的强连通子图。反向边和横叉边都有一个特点：起点的dfs序必然大于终点的dfs序。
性质四：在对无向图G进行DFS时，每条边要么是树边，要么是后向边
拓扑排序对于一个有向无环图G = （V，E）来说，其拓扑排序是G中所有结点的一种线性次序，该次序满足如下条件：如果图G包含边（u, v），则结点u在拓扑排序中处于结点v的前面。
拓扑排序就是将节点按完成时间进行降序排序
如果一个有向图中任意两个顶点互相可达，则称该有向图是强连通的。
有向图G=(V, E)的强连通分量是一个最大节点集合 C ∈ V Cin V C∈V，对于该集合中的任意一对节点u和v来说，路径u->v和路径v->u同时存在，即节点u和v可以相互抵达.
Kosaraju算法其实比较容易理解，它使用了两次DFS，算法的主要过程也就是这两次DFS:
主要利用“强连通分量”在转置图中，依旧是“强连通分量”。利用DFS分别计算图G与图Gt的连通性，然后取交集。
主要过程：《Kosaraju强连通子图算法》
主要参考《Elementary Graph Algorithms》
《算法学习笔记(69): 强连通分量》
《Kosaraju强连通子图算法》
《强连通分量》