有向图、无向图
 
有向图和无向图是我们常用到的术语，本文属于简单的科普帖。
 
全部由无向边构成图称为无向图（Undirected Graph）,全部由有向边构成图称为有向图（Directed Graph）。有向，顾名思义，有方向。本文中顶点Vertex（V），边Edge（E）
 
（1）出度和入度：如图D，以点A为例子，在所有与A关联的边中，以A为起点的边的条数称为出度。而入度则刚好相反，以A为终点的边的条数则称为入读。其中，入度+出度，我们称为A的度。注意特殊情况：如图：A有一个自环，起点和终点都是自己，此时出度算一度，入度也算一度。如图：A的出度为3，入度也为2，A的度的5。
 

 （2）描述图的邻接矩阵和关联矩阵
 【邻接矩阵】
 
定义：
 设无向图G=(V,E),其中顶点集V=v1,v2,…,vn，边集 E=e1,e2,…,eε。用aij表示顶点vi与顶点vj之间的边数，可能取值为0,1,2,…，称所得矩阵A=A(G)=(aij)n×n为图G的邻接矩阵。邻接矩阵可以描述有向图和无向图。
 
示例，求图所示简单图的邻接矩阵？
 
 解：根据定义，可求得该无向图的邻接矩阵为
 
 
邻接矩阵的存储特点：
 （a）无向图的邻接矩阵一定是一个对称矩阵，有向图不一定是。
 *（b）邻接矩阵所需的存储空间值域只与顶点数有关系。
 （c）用邻接矩阵存储图，容易判断两个点之间是否有边。
 （d）如果一个有向图的邻接矩阵为三角矩阵（主对角线为0），则它的拓扑排序一定存在。
 *（e）小技巧：
 无向图：邻接矩阵的第i行或者第i列的非零元素的个数正好是第i个顶点Vi的度；
 有向图：邻接矩阵的第i行的非零元素个数正好是第i个顶点Vi的出度，第i列非零元素的个数正好是第i个顶点Vi的入度。
 
【关联矩阵】
 
定义：
 设任意图G=(V,E)，其中顶点集V=v1,v2,…,vn，边集E=e1,e2,…,eε。用mij表示顶点vi与边ej关联的关系，可能取值为0,1，-1，称所得矩阵M(G)=(mij)n×ε为图G的关联矩阵。
 
 mij 表示i行j列，探究顶点Vi和边Ej之间的关系，形成下列的关联矩阵
 示例：
 
 关联矩阵
 
 
连通图、连通分量
 
连通图：无向图中，若从顶点u到顶点v有路径，称为u，v是连通的。若图中任意两个顶点均是连通的，则称为连通图。
 连通分量：无向图中极大连通子图称为连通分量。
 
强连通图、强连通分量
 
强连通图：有向图中，若从顶点u到顶点v有路径，称为u，v是连通的。若图中任意两个顶点均是连通的，则称为强连通图。
 连通分量：无向图中极大连通子图称为强连通分量。特：强连通图只有强连通分量（本身），非强连通图有多个强连通分量。
 
另外，本文参考路了下面两位作者的优秀博客
 https://blog.csdn.net/Hanging_Gardens/article/details/55670356
 https://blog.csdn.net/legendaryhaha/article/details/83049101

图的定义:
 
　　图在数据结构中是中一对多的关系，一般分为无向图与无向图
 
　　常用 邻接矩阵 或者 邻接链表 来表示图中结点的关系
 
　　⑴图是由顶点集V和顶点间的关系集合E（边的集合）组成的一种数据结构
 　　⑵用二元组定义为：G=（V,E）。
 
例如：
 
 
对于图7-1所示的无向图G1和有向图G2，它们的数据结构可以描述为：
 
　　　　　　G1=(V1,E1)， 其中 V1={a,b,c,d},E1={(a,b),(a,c),(a,d),(b,d),(c,d)},
        　　        G2=(V2,E2)，其中 V2={1,2,3}, E2={<1,2>,<1,3>,<2,3>,<3,1>}。
 
有向图与无向图
 
　　　　⑴在图中，若用箭头标明了边是有方向性的，则称这样的图为有向图，否则称为无向图。
 
　　　　如图7-1中:
    　　　　　　①G1为无向图，   ②G2 为有向图。
 　　　　⑵在无向图中:一条边（x,y）与（y,x）表示的结果相同，用圆括号表示，
 　　　　⑶在有向图中:一条边<x,y>与<y,x>表示的结果不相同，故用尖括号表示。<x,y>表示从顶点x发向顶点y的边，x为始点，y为终点。
 　　　　⑷有向边也称为弧，x为弧尾，y为弧头,则<x,y>表示为一条弧, 而<y,x>表示y为弧尾，x为弧头的另一条弧 。
 
 
 
完全图/稠密图/稀疏图：
 
　　⑴具有n个顶点，n(n-1)/2条边的图，称为完全无向图，
 　　⑵具有n个顶点，n(n-1) 条弧的有向图,称为完全有向图。
 　　⑶完全无向图和完全有向图都称为完全图。
 　　⑷对于一般无向图，顶点数为n，边数为e，则 0≤e  ≤n(n-1)/2。
 　　⑸对于一般有向图，顶点数为n，弧数为e， 则 0≤e≤n(n-1)  。
 　　⑹当一个图接近完全图时，则称它为稠密图，
 　　⑺当一个图中含有较少的边或弧时，则称它为稀疏图。
 
度/出度/入度：
 
　　⑴在图中，一个顶点依附的边或弧的数目，称为该顶点的度。
 
　　⑵在有向图中，一个顶点依附的弧头数目，称为该顶点的入度。
 
　　⑶一个顶点依附的弧尾数目，称为该顶点的出度，某个顶点的入度和出度之和称为该顶点的度。
 
　　⑷若图中有n个顶点，e条边或弧，第i个顶点的度为di，则有  e=1/2 * Σ(1<= i <= n,   di)
 
子图
 
⑴若有两个图G1和G2， G1=(V1,E1)， G2=(V2,E2)， 满足如下条件：
     V2⊆V1  ，E2⊆ E1，即V2为V1的子集，E2为E1的子集，则 称图G2为图G1的子图。

 
权：
 ⑴在图的边或弧中给出相关的数，称为权。
 ⑵权可以代表一个顶点到另一个顶点的距离，耗费
    等，带权图一般称为网。
 
一个图由多个结点以及边组成。
 
无向图例子：
 
　　
 
　　有向图例子：
 
　　
 
从上述例子中可以看出，一个图表是由数个顶点和边组成的。
 
　　其中，无向图的边是没方向的，即两个相连的顶点可以互相抵达。
 
　　而有向图的边是有方向的，即两个相连的顶点，根据边的方向，只能由一个顶点通向另一个顶点。（当然，如有向图例子中的2和3，由于有两个指向对方的方向，所以2和3是互通的。）
 
完全图
 
连通图：如果一个无向图从每一个顶点到其他顶点都存在一条路径，则称该无向图为连通图
 
强连通图：具有这样的性质的有向图称为是强连通的，如果不是强连通的，
 
弱连通图：它的基础图，即去掉弧上的方向所形成的的图，是连通的，那么该有向图称为弱连通的
 
完全无向图：具有n个顶点，并具有n(n - 1)/2 条边的图，称为完全无向图（每个顶点到其他顶点都有边），连通图
 
完全有向图：具有n个顶点，并且具有n(n - 1) 条边的有向图，称为完全有向图（每个顶点到其他顶点都有相互两条边），强连通图
 
完全图：完全无向图和完全有向图都称为完全图
 
邻接矩阵
 
定义：
 设无向图G=(V,E)G=(V,E),其中顶点集V=v0,v1,v2,...,vnV=v1,v2,...，边集E=e0,e1,e2,...,eεE=e1,e2,...,eε。用aijaij表示顶点vivi与顶点vjvj之间的边数，可能取值为0,1,2,…，称所得矩阵A=A(G)=(aij)n×nA=A(G)=(aij)n×n为图G的邻接矩阵
 
性质：
 
 
类似地，有向图D的邻接矩阵A(D)=(aij)n×nA(D)=(aij)n×n, aijaij表示从始点vivi到终点vjvj的有向边的条数，其中vivi和vjvj为D的顶点
 
示例，求图所示简单图的邻接矩阵？
 
 
解：根据定义，可求得该无向图的邻接矩阵为
 
 
注：邻接矩阵是描述图的一种常用的矩阵表示。
 
 
 
关联矩阵
 
定义：
 设任意图G=(V,E)G=(V,E)，其中顶点集V=v1,v2,...,vnV=v1,v2,...,vn，边集E=e1,e2,...,eεE=e1,e2,...,eε。用mijmij表示顶点vivi与边ejej关联的次数，可能取值为0,1,2,…，称所得矩阵M(G)=(mij)n×εM(G)=(mij)n×ε为图G的关联矩阵
 
类似地，有向图DD的关联矩阵M(D)=(mij)n×εM(D)=(mij)n×ε的元素mi×jmi×j定义为：
 
 
示例，求图中有向图的邻接矩阵和关联矩阵
 
 
解：根据定义，可求得该有向图的邻接矩阵:
 
 
关联矩阵:
 
 
注：关联矩阵是描述图的另一种矩阵表示。
 
参考地址：
 
https://blog.csdn.net/Hanging_Gardens/article/details/55670356
 
https://blog.csdn.net/legendaryhaha/article/details/83049101
 
https://www.cnblogs.com/schips/p/10632250.html

备注：大一学了图后，一段时间没用就还给老师了，如今重新复习一下，理解有误的地方请指教。
 
 
有向图和无向图的定义
 
1）关于有向图，百科中是这样描述的：一个有向图D是指一个有序三元组(V(D)，A(D)，ψD)，其中ψD为关联函数，它使A(D)中的每一个元素(称为有向边或弧)对应于V(D)中的一个有序元素(称为顶点或点)对。
 理解：如图D，如果e是D的一条边，而这时候存在这样的一个关系，ψD，有A，B两点，使得，ψD（A，B）=e（到底是怎样的关系？我觉得在应用中，需要我们自己制定，就像在预算100元的条件下，你选择怎样的交通工具快速到达目的地），通俗理解：边有方向的图。即AB ！= BA。
 [外链图片转存失败(img-OHZsll7R-1567908307459)(https://uploadfiles.nowcoder.com/images/20181014/443077457_1539483515239_C07BA5588B40E754EB534225BA630A0D “图片标题”)]
 
 
（2）平行边：在图中，如果起点和终点相同则称为平行边，平行边的条数则称为重数。如图：e2和e3为平行边，B和C之间的重数为2。
 [外链图片转存失败(img-EMKaEUe6-1567908307460)(https://uploadfiles.nowcoder.com/images/20181014/443077457_1539483671400_6DA66AE52EFE0CF2370DF02226877263 “图片标题”)]
 
 
（3）关于无向图：了解了有向图，那它就好理解了，就是有向图中去掉所有的方向，AB=BA，如图，就是去掉D中的所有箭头（此时，又称为基础图，反之给无向图添上箭头的有向图又称为定向图）。
 [外链图片转存失败(img-DJM75Udh-1567908307461)(https://uploadfiles.nowcoder.com/images/20181014/443077457_1539483731056_5FB56EBF13116F56F22CCFD0F068F03B “图片标题”)]
 
 
（4）出度和入度：如图D，以点A为例子，在所有与A关联的边中，以A为起点的边的条数称为出度。而入度则刚好相反，以A为终点的边的条数则称为入读。其中，入度+出度，我们称为A的度。注意特殊情况：如图：A有一个自环，起点和终点都是自己，此时出度算一度，入度也算一度。如图：A的出度为3，入度也为2，A的度的5。
 
 
 
（5）邻接矩阵和关联矩阵定义：设D（V,E）是有向图，其中V={v1,v2,v2…vn},E={e1,e2,e3,…em}称A(D)=(aij)nxn是D的领接矩阵，其中aij是以vi为起始点，以vj为终点的边的条数。若图D中无环，则称M(D)=（mij）nxm为关联矩阵。[i，j是下标，n是点的个数，m是边的数量注意：1.关联矩阵是针对边来说的，所以矩阵大小为n*m，它的取值如下：
 

 例子：
 
 （6）补充：对于无向图而言：邻接矩阵则是对称的，且只有0和1，因为没有方向的区别后，要么有边，要么没边：
 
 从图我们可以看到，它是关于对角线对称的一个矩阵，我们在编程中，遍历和存储是只需要关注上半部分或者下半部分即可。
 
 
 
（7）跟邻接矩阵一样，用来存储图中信息的，还有邻接表：如果学过链表了，就很好理解了，首先在一个数组中存储各个点（对象或者成为链），而每个对象又保存着一个next引用指向连接的点在数组中的坐标，如图：A到E在数组中存储后，坐标依次排列，A连B，B的坐标为1，所以指向的地方标记为1，代表A连着B，接着，B连着E，E的坐标为4，这1的引用指向4。
 
从图我们就可以得出邻接表的存储方式了：即链表加数组，这存储结构比起纯粹用数组（邻接矩阵）要节约很多空间。邻接矩阵，我们需要一个n*n维的数组，复杂度为O（n^2），而邻接表是根据点和边来保存数据的，当一个起点决定后，就采用深度搜索的方法沿着边，保存连接点的信息，复杂度为O(n+m）
 
另外，若果是有向图，我们在保存下一个顶点时，还需要保存边的权值，看图中每个格子都分成两小格了吗，第二个小格子就是用来存储权值的。
 
图来自百度词条，好难画
 
 
 
拓扑排序
 
百度词条这样描述：对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若边(u,v)∈E(G)，则u在线性序列中出现在v之前。通常，这样的线性序列称为满足拓扑次序(Topological Order)的序列，简称拓扑序列。
 理解:（1）根据定义，我们可以知道它是针对有向图而言的.（2）它是一个包含有向图的所有点的线性序列，且满足两个条件：a.有向图的每个顶点只出现一次。b.若存在一条从顶点 A 到顶点 B 的路径，那么在序列中顶点 A 应该出现在顶点 B 的前面。
 
备注：图来源于百度，之前都没发现，它的786，应该是678，C0是连着C2和C6的
 [外链图片转存失败(img-q5yfBWrf-1567908307464)(https://uploadfiles.nowcoder.com/images/20181014/443077457_1539485618410_F203E6F40B767104E9635E84C103CA7C “图片来源于百科”)]
 
（2）注意，拓扑排序并不是唯一的，它的排序方式：以上图为例子：a.首先我们从有向图图中选择一个没有前驱（即入度为0）的顶点并输出，这里我们可以选择c0或者c1。b.从图中删除输出的顶点和所有以它为起点的有向边。c.循环 a步骤 和 b步骤，终止条件为当前的有向图为空或当前图中不存在无前驱的顶点为止。备注：若当前图中不存在无前驱的顶点，说明有向图中必然存在环。
 

 
有向图
 
一. 有向图的相关术语
二. 有向图的存储数据结构
1. 有向图的表示
2. 有向图取反
3. 有向图的实现
4. 符号有向图的实现
  
三. 有向图中的可达性
1. 使用DFS实现有向图的可达性分析
2. 标记-清除的垃圾收集
3. 有向图的寻路
  
四. 环和有向无环图(DFS和拓扑排序)
1. 调度问题(拓扑排序)
2. 有向环的检测方法一：DFS
3. 顶点的深度优先次序与拓扑结构
  
五. 有向图中的强连通性
1. 强连通分量
2.强连通分量应用
3. 计算强连通分量的Kosaraju算法(无)
4. 再谈可达性(无)
  
六. 总结(无)

 
一. 有向图的相关术语
 
在有向图中，边是单向的：每条边连接的两个顶点都是一个有序对，它们的邻接性是单向的。我们开发过程中碰到的很多场景都是有向图：比如任务調度的依赖关系，社交网络的任务关系等等都是天然的有向图。
 
以下概念都是针对有向图的：
 
（1）有向图：一幅有向图是由一组顶点和一组有方向的边组成的，每条有方向的边都连接着有序的一对顶点。
 
（2）顶点的出度：该顶点指出的边的总数。
 
（3）顶点的入度：指向该顶点的边的总数。
 
（4）比如对于有序对(w,v) 一般代表w->v 的一条有向边。
 
（5）有向路径：由一系列顶点组成，其中每个顶点都存在一条有向边从它指向序列中的下一个顶点。
 
（6）有向环：为一条至少含有一条边且起点和终点相同的有向路径。
 
（7）简单有向环：是一条除了起点和终点外，不含有重复的顶点和边的环。
 
二. 有向图的存储数据结构
 
首先定义有向图的API接口，DiGraph 本质上和Graph是一样的。
 
public class Digraph
Digraph(int v)
创建一幅含有v个顶点，但是没有边的有向图
Digraph(In in)
从输入流中读取一幅有向图
int E()
边的总数
int V()
边的总数
void addEdge(int v, int w)
添加一条有向边v ->w
Iterble<Integer>adj(int v)
由顶点v出发的有向边所连接的所有顶点
Digraph reverse()
该图的反向图
String toString()
对象的字符串表示形式
1. 有向图的表示
 
和无向图的表示类似，我们还是使用 邻接表 来存储有向图，其中边 v—>w 表示为顶点v所对应的邻接链表中包含一个w顶点。
 
2. 有向图取反
 
上面的API中给出了reverse() 方法，将有向图中的所有有向边反转，并生成副本。
 
3. 有向图的实现
 
使用邻接表来存储有向图，用数组来表示图中的每个节点的集合，并且数组的下标就表示节点的标识符。
 
下面就是有向图的实现方式：
 
package com.example.algorithm4.graphs;

import edu.princeton.cs.algs4.Bag;

/**
 * 有向图的实现
 * 
 * @author 惜暮
 * @email chris.lyt@alibaba-inc.com
 * @date 2017/12/7
 */
public class DiGraph {
    /**
     * 节点的总个数
     */
    private final int V;
    /**
     * 边的总个数
     */
    private int E;
    /**
     * 有向图的邻接表表示法
     */
    private Bag<Integer>[] adj;

    /**
     * 创建一个含有V个节点，但是0条边的有向图
     * @param V
     */
    public DiGraph(int V) {
        this.V = V;
        this.E = 0;
        adj = (Bag<Integer>[])new Bag[V];
        for (int i=0; i<this.V; i++){
            adj[V] = new Bag<>();
        }
    }


    public int E(){
        return this.E;
    }


    public int V(){
        return this.V;
    }

    /**
     * 添加一条 v-->w 的边
     * @param v 有向边的源在数组中的标识符
     * @param w 有向边的终在数组中的标识符
     */
    public void addEgge(int v, int w){
        adj[v].add(w);
        this.E++;
    }

    /**
     * 节点v 的所有出度的终顶点
     * @param v 节点v 的标识符
     * @return
     */
    public Iterable<Integer> adj(int v){
        return adj[v];
    }

    /**
     * 此有向图反转之后的副本
     * @return
     */
    public DiGraph reverse(){
        DiGraph reverse = new DiGraph(this.V);
        for(int i=0 ;i<this.V; i++){
            for (int w : adj[i]){
                //边反转
                reverse.addEgge(w, i);
            }
        }
        return reverse;
    }
}
 
4. 符号有向图的实现
 
有向图的邻接表表示和无向图的邻接表表示区别不大，仅仅在于边的处理上有一点区别。如果对于有向图的结点的标识我们也想用字符串来表示呢？其实现方法几乎和无向图一样，增加一个Map用来保存顶点的符号到数组下表的映射关系，然后用字符数组保存所有的符号，数组下标天然表示每个顶点的index。 代码实现上只需要把SymbolGraph中的Graph替换成DiGraph就可，下面也给出实现代码：
 
package com.example.algorithm4.graphs;

import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.ST;

/**
 * 符号有向图的实现
 * @author 惜暮
 * @email chris.lyt@alibaba-inc.com
 * @date 2017/12/7
 */
public class SymbolDiGraph {
    private ST<String, Integer> st; // map,顶点符号名 -> 数组索引
    private String[] keys; // 数组索引 -> 顶点符号名
    private DiGraph G; // 图

    /**
     * 构造一颗符号有向图
     * @param stream 顶点边的数据源
     * @param sp 顶点分隔符
     */
    public SymbolDiGraph(String stream, String sp) {
        st = new ST<>();
        In in = new In(stream); // First pass
        while (in.hasNextLine()) {// builds the index
            String[] a = in.readLine().split(sp); // by reading strings
            for (int i = 0; i < a.length; i++) {// to associate each
                if (!st.contains(a[i])) {// distinct string
                	st.put(a[i], st.size()); // with an index.
                }
            }
        }
        keys = new String[st.size()]; //建立索引 --> 结点符号
        for (String name : st.keys()) {// to get string keys
          	keys[st.get(name)] = name; // is an array.
        }
      
        // 创建符号图
        G = new DiGraph(st.size());
        in = new In(stream); // Second pass
        while (in.hasNextLine()) {// builds the graph
            String[] a = in.readLine().split(sp); // by connecting the
            int v = st.get(a[0]); // source vertex
            for (int i = 1; i < a.length; i++) {// on each line
            	G.addEdge(v, st.get(a[i])); // to all the others.
            }
        }
    }

  	public boolean contains(String s) {
      	return st.contains(s);
    }

  	public int index(String s) {
      	return st.get(s);
    }

	public String name(int v) {
      	return keys[v];
    }

	public DiGraph G() {
      	return G;
    }
}
 
三. 有向图中的可达性
 
我们在无向图中介绍的第一个算法就是DFS，其实无向图是很多算法的基础，解决了单点连通性的问题，可以判断无向图中指定的两个顶点是否连通。其思想对于有向图同样适用~
 
 
 
定义：有向图的单点可达性：给定一个有向图和一个起点s，判断是否存在一条从起点s到指定节点v的有向路径。
 
 
针对以上问题，设计DirectedDFS 算法的API：
 
public class DirectedDFS
DirectedDFS(DiGraph G, int s)
在G中找到从s可达的所有顶点
DirectedDFS(DiGraph G, Iterable<Integer> sources)
在G中找到从sources的所有顶点中可达的所有顶点
boolean reachable(int v)
d顶点v是可达的嘛
1. 使用DFS实现有向图的可达性分析
 
 
 
在有向图中，深度优先搜索标记由一个集合的顶点可达的所有顶点所需的时间与被标记的所有顶点的出度之和成正比。
 
 
下面是有向图的可达性算法的实现：
 
package com.example.algorithm4.graphs;

/**
 * 有向图的深度优先遍历
 *
 * @author 惜暮
 * @email chris.lyt@alibaba-inc.com
 * @date 2017/12/7
 */
public class DirectedDFS {
    /**
     * 从起点s开始DFS访问过的路径标记
     */
    private boolean[] marked;

    public DirectedDFS(Digraph digraph, int s) {
        this.marked = new boolean[digraph.V()];
        dfs(digraph, s);
    }

    public DirectedDFS(Digraph digraph, Iterable<Integer> sources) {
        this.marked = new boolean[digraph.V()];
        for(int s : sources){
            if (!marked[s]){
                dfs(digraph, s);
            }
        }
    }

    /**
     * 从节点v 开始有向图的DFS
     *
     * @param digraph 有向图
     * @param v 结点
     */
    private void dfs(Digraph digraph, int v){
        this.marked[v] = true;
        for (int w : digraph.adj(v)){
            if(!this.marked[w]){
                dfs(digraph, w);
            }
        }
    }

    public boolean marked(int v){
        return marked[v];
    }
}
 
这份深度优先搜索能够实现判断一个或则一组(多点可达性)顶点能到达哪些其他顶点。
 
2. 标记-清除的垃圾收集
 
多点可达性的一个重要的实际应用是在典型的内存管理上，比如JVM内存管理，在一幅有向图中，一个顶点代表一个对象，一条边代表一个对象对另外一个对象的引用。 有向图的模型很好的可以应用在JVM内存管理上面。当从根节点遍历时候，那么不可达的顶点就代表不会再被使用，就可以被回收以释放内存。
 
标记-清除的垃圾回收算法会为每个对象保存一个位作为垃圾回收之用，然后周期性的运行一个类似于DirectedDFS的有向图可达性算法来标记所有可以被访问到的对象，然后清理所有对象，回收没有被标记的对象，以达到释放内存的目的。
 
3. 有向图的寻路
 
DepthFirstPaths 和 BreadthFirstPaths 也都是有向图处理中的重要算法。可以用处理下面问题：
 
单点有向路径：给定一个起点s，从s到给定目的顶点v是否存在一条有向路径。如果有就找出这条路径。
单点最短有向路径：给定一个起点s，从s到给定目的顶点v是否存在一条有向路径。如果有就找出最短的路径。
 
下图给出了一个使用深度优先遍历在一幅有向图中寻找能够从顶点0到达的所有顶点的轨迹的示意图：
 
 
四. 环和有向无环图(DFS和拓扑排序)
 
在有向图的应用场景中对于有向环的检测十分重要，因为有向环就代表着死循环，然后实际的项目中由于依赖关系的复杂，几乎不可能肉眼检测有向环，所以检测有向环是否存在就至关重要。
 
对于有向环的检测主要有两种方法：DSF和拓扑排序。下面以实际例子来分析
 
1. 调度问题(拓扑排序)
 
一个广泛使用的模型就是给定一组任务并安排它们的执行顺序，限制条件是这些任务的执行方法和起始时间。限制条件可能还包括任务的耗时以及消耗的其他资源。最重要的一种限制条件叫做优先级限制，它指明了哪些任务必须在哪些任务之前完成。 不同类型的限制条件会产生不同类型不同难度的调度问题
 
下面以一个正在安排课程的大学生为例，有些课程是其余课程的先导课程：如图：
 
 
再假设该学生一次只能修一门课，问题就可以抽象成以下模型：
 
优先级限制下的調度问题：给定一组需要完成的任务，以及一组关于任务完成的先后次序的优先级顺序。在满足条件下以最优方案完成任务。为了简化模型，以数字标识顶点，顶点代表任务。可以等价成下图:
 
 
 
 
拓扑排序：给定一幅有向图，将所有顶点排序，使得所有的有向边均从排在前面元素指向排在后面的元素。
 
 
上面的实例的拓扑排序图如下：所有边都朝下，清晰描绘了这幅有向图模型代表的优先级限制下調度问题的解决方法：
 
 
拓扑排序有很多典型的应用，比如任务調度，继承等等。
 
2. 有向环的检测方法一：DFS
 
 
 
定义。有向无环图就是一幅不包含环的有向图。
 
 
有向环的检测，我们可以借助于DFS算法，也可以借助拓扑排序。算法DirectedCycle 实现了环的检测，API如下:
 
public class DirectedCycle
DirectedCycle(Digraph digraph)
寻找有向环的构造函数
boolean hasCycle()
digraph是否有环
Iterable<Integer> cycle()
有向环中的所有顶点
下图是一个在有向环中寻找环的过程示意图：
 
 
算法实现如下：
 
package com.example.algorithm4.graphs;

import java.util.Stack;

/**
 * 有向图环的检测：DFS算法
 *
 * @author 惜暮
 * @email chris.lyt@alibaba-inc.com
 * @date 2017/12/7
 */
public class DirectedCycle {
    /**
     * 从起点开始DFS访问过的路径标记
     */
    private boolean[] marked;
    /**
     * 从起点到一个顶点v的已知路径上的最后一个顶点
     */
    private int[] edgeTo;
    /**
     * 如果存在有向环，就保存有向环中的所有顶点。
     */
    private Stack<Integer> cycle;
    /**
     * 递归调用栈上的所有顶点
     * 这里类似于Java里面的一个set，里面保存了所有已经访问过的顶点
     */
    private boolean[] onStack;

    /**
     * 构造器
     *
     * @param digraph 有向图
     */
    public DirectedCycle(Digraph digraph) {
        this.marked = new boolean[digraph.V()];
        this.edgeTo = new int[digraph.V()];
        this.onStack = new boolean[digraph.V()];
        for (int v=0; v<digraph.V(); v++) {
            if( !marked[v] ) {
                dfs(digraph, v);
            }
        }
    }

    /**
     * 从节点v 开始有向图的DFS
     *
     * @param digraph 有向图
     * @param v 结点
     */
    private void dfs(Digraph digraph, int v){
        // 标记当前结点在堆栈路径上
        this.onStack[v] = true;
        this.marked[v] = true;
        for (int w : digraph.adj(v)){
            // 如果当前图已经有环就直接返回
            if (this.hasCycle(w)){
                return;
            } else if(!this.marked[w]){
                // 如果当前结点没有被标记过，递归dfs
                edgeTo[w] = v;
                dfs(digraph, w);
            } else if (onStack[w]){
                // (1)当前结点被标记过来了，(2)而且在已经访问过得堆栈上，则存在环
                cycle = new Stack<>();
                for(int x = v; x!=w; x = this.edgeTo[x]) {
                    cycle.push(x);
                }
                cycle.push(w);
                cycle.push(v);
            }
        }
        // 递归回溯时，当前结点重置为不在环的堆栈上。
        this.onStack[v] = false;
    }

    public boolean hasCycle(int v){
        return cycle!=null;
    }

    public Iterable<Integer> cycle(){
        return cycle;
    }
}
 
上面检测有向图是否有环的算法采用标准的递归dfs算法，添加了一个布尔型数组onStack[] 来保存递归调用期间栈上面的所有顶点。当找到一条边 v->w 且w在栈中时，就代表找到了有向环。环上所有顶点都可以通过edgeTo[]数组得到。
 
3. 顶点的深度优先次序与拓扑结构
 
在优先级限制下的調度问题等价于计算有向无环图中的所有顶点的拓扑排序，因此给出如下API：
 
public class Topological
Topological(Digraph digraph)
拓扑排序的构造函数
boolean isDAG()
图digraph是有向无环图嘛？
Iterable<Integer> order()
拓扑排序的所有顶点
 
 
定理：当且仅当一幅图是有向无环图时才能进行拓扑排序。也就是有向无环图才有拓扑排序。
 
 
首先我们先来看看 有向图中基于深度优先搜索的顶点排序 的DepthFirstOrder算法。
 
其基本思想是：深度优先搜索正好只会访问每个顶点一次，如果将dfs()的参数顶点保存在一个数据结构中，遍历这个数据结构实际上就能访问图中的所有顶点，遍历的顺序取决于这个数据结构的性质以及是在递归调用之前还是调用之后进行保存。在应用中我们关注的是以下3种排列顺序：
 
前序：在递归调用之前将顶点加入队列
后序：在递归调用之后将顶点加入队列
逆后续：在递归调用之后将顶点压入栈。
 
下图是用DepthFirstOrder 算法处理有序无环图产生的轨迹。实现简单，支持处理图的高级算法中十分有用的pre()、post()和reversePost()方法。 例如Topological类中order()方法就调用了reversePost()方法。
 
 
算法实现如下：
 
package com.example.algorithm4.graphs;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * 有向图中基于深度优先搜索的顶点排序
 *
 * @author 惜暮
 * @email chris.lyt@alibaba-inc.com
 * @date 2017/12/7
 */
public class DepthFirstOrder {
    /**
     * 从起点开始DFS访问过的路径标记
     */
    private boolean[] marked;
    /**
     * 所有顶点的前序排列
     */
    private Queue<Integer> pre;
    /**
     * 所有顶点的后序排列
     */
    private Queue<Integer> post;
    /**
     * 所有顶点的逆后序排列
     */
    private Stack<Integer> reversePost;

    public DepthFirstOrder(Digraph digraph) {
        marked = new boolean[digraph.V()];
        pre = new LinkedList<>();
        post = new LinkedList<>();
        reversePost = new Stack<>();

        for (int v=0; v<digraph.V(); v++){
            if ( !marked[v] ) {
                dfs(digraph, v);
            }
        }
    }

    /**
     * 从节点v 开始有向图的DFS
     *
     * @param digraph 有向图
     * @param v 结点
     */
    private void dfs(Digraph digraph, int v){
        pre.add(v);
        this.marked[v] = true;
        for (int w : digraph.adj(v)){
            if(!this.marked[w]){
                dfs(digraph, w);
            }
        }
        post.add(v);
        reversePost.push(v);
    }

    public Iterable<Integer> pre(){
        return pre;
    }

    public Iterable<Integer> post(){
        return post;
    }

    public Iterable<Integer> reversePost(){
        return reversePost;
    }
}
 
该类允许使用各种顺序遍历DFS经过的顶点。这在高级的有向图处理算法中非常有用，因为搜索的递归性是的我们能够证明这段计算的许多性质。
 
下面给出拓扑排序==Topological==的实现算法：
 
package com.example.algorithm4.graphs;

/**
 * 有向无环图的 拓扑排序
 *
 * @author 惜暮
 * @email chris.lyt@alibaba-inc.com
 * @date 2017/12/7
 */
public class Topological {
    /**
     * 顶点的拓扑排序
     */
    private Iterable<Integer> order;

    public Topological(Digraph digraph){
        DirectedCycle cycleFinder = new DirectedCycle(digraph);
        if( !cycleFinder.hasCycle() ) {
            DepthFirstOrder dfs = new DepthFirstOrder(digraph);
            order = dfs.reversePost();
        }
    }

    public Iterable<Integer> order() {
        return order;
    }

    public boolean isDAG(){
        return order!=null;
    }
}
 
Topological的实现借助了DirectedCycle 检测环是否存在，借助DepthFirstOrder的逆后续来获取拓扑排序。
 
 
 
定理：一幅有向无环图的拓扑排序就是所有顶点的逆后续排列。
 
 
证明：
 
 
在任意一条边v->w， 在调用dfs(v) 时，下面三种情况，必有一种成立：
 
 
（1）dfs(w) 已经被调用过了，且已经返回了。 (w节点已经被标记true了)
 
 
（2）dfs(w)还没有被调用(w还没被标记)， 因此v->w 会直接或则间接调用并返回dfs(w)，且dfs(w)会在dfs(v)之前返回。
 
 
（3）dfs(w)已经被调用但还没返回。证明的关键在于，在DAG中，这种情况是不可能出现的。由于递归调用链的特性意味着存在从w到v的路径，但又存在v->w的边，所以存在一个环。
 
 
在上面(1)(2)两种情况中dfs(w) 会在dfs(v)之前完成，也就是后续排列中w排在v之前。 所以在逆后序中w排在v之后，因此任意一条边v->w 都如我们所愿地从排名比较靠前的顶点指向排名靠后的顶点。
 
 
 
 
定理：使用深度优先算法对有向无环图进行拓扑排序所需要时间和 (V+E) 成正比。
 
 
证明：从DirectedCycle和DepthFirstOrder的实现可知，两次搜索都访问了所有顶点和边，所以时间和（V+E）成正比。
 
 
下面给出了一个示例 DAG 的逆后续是拓扑排序的轨迹图：
 
 
五. 有向图中的强连通性
 
 
 
定义：有向图中，如果两个顶点v和w是互相可达的，则称它们为强连通的。也就是说存在一条从v到w的有向路径，也存在一条从w到v的有向路径。 如果一幅有向图中任意两个顶点都是强连通的，则称这幅有向图也是强连通的。
 
 
1. 强连通分量
 
有向图的强连通性也是一种顶点之间的平等关系，因为其有着如下性质：
 
自反性：任意顶点v和自己都是强连通的。
对称性：如果v和w是强连通的， 那么w和v也是强连通的。
传递性：如果v和w是强连通的且w和x也是强连通的 ，那么v和x也是强连通的。
 
强连通分量就是：有向图的极大强连通子图
 
2.强连通分量应用
 
最典型应用就是网络，以顶点代表网页，超链接代表边。 下面给强连通分量的API：
 
public class SCC
SCC(Digraph digraph)
预处理构造函数
boolean stronglyConnected(int v, int w)
v和w是强连通的吗？
int count()
图中强连通分量的总数
int id(int v)
v所在强连通分量的标识符(0至count()-1 之间)
3. 计算强连通分量的Kosaraju算法(无)
 
4. 再谈可达性(无)
 
六. 总结(无)