有时，编程的过程中需要将值从一种数据类型转换为另一种数据类型。
在C语言中，强制类型转换的方式为(Type)Expression，另外还有一种现在已经不用的旧式写法Type(Expression)，这两种方式是等价的。
但是，C语言的强制类型转换方式存在一些问题：过于粗暴，可以在任意类型之间进行转换，编译器很难判断其正确性，难于定位，在源代码中无法快速定位所有使用强制类型转换的语句。
然而，强制类型转换在实际工程中几乎是不可避免的，为此C++将强制类型转换分为4种不同的类型，以提供更加安全可靠的转换。
static_cast
用法：static_cast (expression)
该运算符把expression转换为type-id类型，但没有运行时类型检查来保证转换的安全性。它主要有如下几种用法：
 (1)用于类层次结构中基类和派生类之间指针或引用的转换。
 进行上行转换(把派生类的指针或引用转换成基类表示)是安全的
 进行下行转换(把基类的指针或引用转换为派生类表示)，由于没有动态类型检查，所以是不安全的
 (2)用于基本数据类型之间的转换，如把int转换成char。这种转换的安全也要开发人员来保证
 (3)把空指针转换成目标类型的空指针
 (4)把任何类型的表达式转换为void类型
 注意：static_cast不能转换掉expression的const、volitale或者__unaligned属性。主要用于基本类型之间、有继承关系的类对象之间、类指针之间的转换,不能用于基本类型指针之间的转换。
比如：下面代码第五行会报错，“static_cast”: 无法从“float *”转换为“int *”
const_cast
用法：const_cast (expression)
该运算符用来修改类型的const或volatile属性。除了const 或volatile修饰之外， type_id和expression的类型是一样的。
 常量指针被转化成非常量指针，并且仍然指向原来的对象；
 常量引用被转换成非常量引用，并且仍然指向原来的对象；常量对象被转换成非常量对象。
注意：用于去除变量的只读属性，强制转换的目标类型必须是指针或引用
比如：下面代码第二行会报错，“const_cast”: 无法从“const int”转换为“int”，值得注意的是，强转去掉常量属性之后通过指针修改变量，并不能改变原本常量的值，在【C++const常量玩出新花样】中有讲到
结果：
reinterpret_cast
用法：reinterpret_cast (expression)
 它可以把一个指针转换成一个整数，也可以把一个整数转换成一个指针(先把一个指针转换成一个整数，在把该整数转换成原类型的指针，还可以得到原先的指针值)。
 该运算符的用法比较多。
 该运算符平台移植性比价差。
注意：type-id必须是一个指针、引用、算术类型、函数指针或者成员指针。用于指针类型之间、整数和指针类型之间的转换
比如：下面代码第三行会报错，“reinterpret_cast”: 无法从“float”转换为“int”。
dynamic_cast
用法：dynamic_cast (expression)该运算符把expression转换成type_id类型的对象。type_id必须是类的指针、引用或者void*；如果type_id是类指针类型，那么expression也必须是一个指针，如果type_id是一个引用，那么expression也必须是一个引用。 dynamic_cast主要用于有继承关系的类层次间的上行转换和下行转换，还可以用于类之间的交叉转换。
在类层次间进行上行转换时，dynamic_cast和static_cast的效果是一样的；
在进行下行转换时，dynamic_cast具有类型检查的功能，比static_cast更安全。
#include using namespace std;class parent{public:virtual void print(){cout << "parent" << endl;}};class son :public parent{public: void print(){cout << "son" << endl; } void printData() { cout << "printData" << endl; }};int main(){parent* ppParent = new son;  //调用是子类中与virtual 的同名函数ppParent->print();//调用是子类中与virtual 的同名函数son* ppSon = nullptr;if ((ppSon = dynamic_cast(ppParent)) != nullptr){ppSon->print(); ppSon->printData();}else{cout << "转换失败" << endl;}system("pause");return 0;}
尾言
如果足下基础比较差，不妨关注下人人都可以学习的视频教程通俗易懂，深入浅出，一个视频只讲一个知识点。视频不深奥，不需要钻研，在公交、在地铁、在厕所都可以观看，随时随地涨姿势的视频教程

本文仅作为《算法》第四版图的相关知识的个人笔记。
几个概念：
1.连通图：

从任意一个顶点都存在一条路径到达另一个任意顶点。非连通图由若干连通图组成，都是极大连通子图。

2.树是一个无环连通图。连通图的生成树是其一个子图，拥有图的所有顶点。

3.二分图

一种能够将所有节点分为两部分的图。简单的说，如果按双色上色，二分图的任意两个相邻的顶点的颜色不同。

4. 两个顶点通过一条边连接，称为相邻的。顶点的度数为与他相连的边的总数。有向图中的度数分为入度和出度，入度为指向该顶点的边的总数，出度为从该顶点指出的边的总数。

5. 自环：一条连接顶点和其自身的边

6. 一对顶点的两条边称为平行边。
PartOne:无向图相关算法
一、无向图
1.1 数据结构
 /**
     * 顶点数目
     */
    private final int V;
    /**
     * 边的数目
     */
    private int E;
    /**
     * 邻接表，Bag为背包，为一个只入不出的队列，adj[v]即表示与顶点v相连的顶点，因此相邻的两个顶点v和w分别会出现在对方的邻接表中
     */
    private Bag<Integer>[] adj;


1.2 构造
 public Graph(int v) {
        V = v;
        this.E=0;
        adj=new Bag[V];
        for (int i = 0; i < V; i++) {
            adj[i]=new Bag<>();
        }
    }

1.3 相关方法
两顶点是否相邻：
  public boolean hasEdge(int v,int w){
  		//遍历顶点v的邻接表，查找有无顶点w
        for(int x:adj(v)){
            if (x==w){
                return true;
            }
        }
        return false;
    }

添加一条边：
 public void addEdge(int v,int w){
       //也可以通过判断v==w和hasEdge(v,w)决定是否允许自环和平行边
            adj[v].add(w);
            adj[w].add(v);
            E++;
   

    }

//顶点度数
 public  int degree(int v){
        int degree=0;
        for (int w:adj(v)){
            degree++;
        }
        return degree;
    }
    //最大度数
    public  int maxDegree(){
        int max=0;
        for (int v = 0; v < V; v++) {
            int degree = degree(v);
            if (degree>max){
                max=degree;
            }
        }
        return max;
    }
    //自环数
    public int numOfSelfLoops(Graph graph){
        int loops=0;
        for (int i = 0; i < graph.V(); i++) {
            for(int w:graph.adj(i)){
                if (w==i){
                    loops++;
                }
            }
        }
        return loops/2;
    }

二、深度优先搜索
简单的说就是 从给定顶点出发，一直向下走，直到下面没有路了，然后返回上一个顶点，继续进行同样方式遍历，直到遍历完所有的顶点。
因此我们需要如下的数据结构：

 /**
     * 标记顶点i是否被访问
     */
    private boolean[] marked;
    /**
     * 从起点到一个顶点的已知路径上的最后一个顶点
     * 如 v->w->x  则edgeTo[w]=v,edgeTo[x]=w
     */
    private int[] edgeTo;
    /**
     * 遍历的起点
     */
    private final int s;      


构造函数：
public DepthFirstPaths(Graph G, int s) {
        this.s = s;
        //初始化两个数组
        edgeTo = new int[G.V()];
        marked = new boolean[G.V()];
        dfs(G, s);
    }

深度优先遍历：
private void dfs(Graph G, int v) {
		//标记当前顶点为true
        marked[v] = true;
        //遍历与当前顶点相邻的顶点
        for (int w : G.adj(v)) {
        	//如果没有被访问
            if (!marked[w]) {
            	//标记起点到当前顶点的最后一个路径
                edgeTo[w] = v;
                //从当前节点继续进行遍历
                dfs(G, w);
            }
        }
    }

是否存在从起点到指定顶点的路径：
 public boolean hasPathTo(int v) {
        validateVertex(v);
        return marked[v];
    }

返回从起点到指定顶点的路径，如果不存在返回null：
 public  Iterable<Integer> pathTo(int v) {
        if (!hasPathTo(v)){
           //没有到达路径，返回null
            return null;
        }
        //因为edgeTo保存的是到达当前节点的父节点，因此使用栈结构，这样从当前节点到起始顶点的顶点依此入栈，遍历的时候便是从起点到该顶点的完整路径
        Stack paths=new Stack();
        for (int i = v; i !=s ; i=edgeTo[i]) {
            paths.push(i);
        }
        paths.push(s);

        return paths;
    }

测试：
 public static void main(String[] args) {
        Graph graph=new Graph(6);
        graph.addEdge(0,2);
        graph.addEdge(0,1);
        graph.addEdge(0,5);
        graph.addEdge(2,1);
        graph.addEdge(2,3);
        graph.addEdge(2,4);
        graph.addEdge(3,5);
        graph.addEdge(3,4);
        DepthFirstPaths dfs=new DepthFirstPaths(graph,0);
        Iterable<Integer> paths = dfs.pathTo(4);
        for (Integer i:paths){
            System.out.println(i.toString());
        }
    }

结果：
0
5
3
4

三、广度优先搜索：
广度优先搜索的思想是，从当前节点，先遍历与该节点相邻的所有节点，然后再对相邻顶点进行广度优先遍历。

深度优先是纵向遍历，广度优先是横向遍历。
数据结构：

广度优先搜索的数据结构同深度基本一样：
public class BreadthFirstPaths {
	private final int start;
    private int[] edgeTo;
    private boolean[] marked;

    public BreadthFirstPaths(Graph graph,int start) {
        this.start = start;
        edgeTo=new int[graph.V()];
        marked=new boolean[graph.V()];
        bfs(graph,start);
    }
}    

但在遍历的时候采用队列进行辅助，思想如下：

1.将当前顶点加入队列

2.从出队出队一个顶点（第一次时出队的就是当前节点），遍历该顶点的所有相邻顶点，置marked[v]为true，并依此入队。

3.当队列非空时，循环步骤2
代码如下：
private void bfs(Graph graph, int start) {
        Queue<Integer> queue=new Queue<>();
        queue.enqueue(start);
        marked[start]=true;
        while (!queue.isEmpty()){
            int v = queue.dequeue();
            for (int w:graph.adj(v)){
                queue.enqueue(w);
                edgeTo[w]=v;
                marked[w]=true;
            }
        }
    }

四、连通分量
数据结构如下：
public class CC {
	 private boolean[] marked;   
    /**
     * 顶点属于哪个连通分量 如 顶点v属于第count个连通分量，则id[v]=count
     */
    private int[] id;
    /**
     * 第count个连通分量的顶点数
     */
    private int[] size;
    /**
     * 连通分量数
     */
    private int count;
    
}    

思想如下：

遍历所有的顶点，对每个顶点都执行dfs深度优先遍历，如果两个顶点在同一个连通分量，那么在对一个顶点进行dfs遍历的时候，两个顶点必然会在构造函数的一个dfs中被访问到，属于同一个连通分量。

构造函数：
public CC(Graph G) {
        marked = new boolean[G.V()];
        id = new int[G.V()];
        size = new int[G.V()];
        //代码1
        for (int v = 0; v < G.V(); v++) {
            if (!marked[v]) {
                dfs(G, v);
                //与顶点v连通的所有顶点都遍历完毕后，说明该连通分量所有顶点已遍历完毕，增加count
                count++;
            }
        }
 }
 private void dfs(Graph G, int v) {
        marked[v] = true;
        //顶点v属于第count个分量
        id[v] = count;
        //第count个分量的顶点数加1
        size[count]++;
        for (int w : G.adj(v)) {
            if (!marked[w]) {
                dfs(G, w);
            }
        }
    }


五、判断是否为无环图
对于无向图而言，判断其是否为无环图很简单，在对某个顶点进行dfs遍历时，假如它的相邻顶点已被访问过，那么有两种可能：

以

3-4-5-3为例

每次dfs都传递要遍历的节点，和当前刚刚被遍历过的节点

一开始三个顶点都未被访问

1.现在对3进行dfs，访问到5,5被标记为true；

2.再对5进行dfs，此时3已经被访问，但是此时的3属于顶点5的父级，不构成环，再访问4，标记4为true；

3.接着对4进行dfs，此时顶点5被访问，同2一样，顶点5属于顶点4的“父级”，不构成环，但是3也被访问了，且3不是顶点4的“父级”，因此此处出现环。

关键代码如下：
private boolean[] marked;
    private boolean hasCycle;

    public Cycle(Graph G) {
        marked=new boolean[G.V()];
        for (int i = 0; i < G.V(); i++) {
            if (!marked[i]){
                dfs(G,i,i);
            }
        }
    }

    private void dfs(Graph G,int v, int u){
        marked[v]=true;
        for(int w:G.adj(v)){
            if (!marked[w]){
                dfs(G,w,v);
            }else if (w!=u){//如 3:5 5:3 就不构成环
                hasCycle=true;
            }
        }
    }

六、二分图问题
这个同无环图问题类型，在对一个顶点进行dfs遍历时，将其未被访问的临接顶点置为与该顶点对立的颜色，若已经被访问，则判断该顶点的颜色与当前顶点的颜色是否不一样，如果一样，则不是二分图。
关键代码如下：
 private void dfs(Graph graph, int v) {
        marked[v]=true;
        for (int w: graph.adj(v)){
            if (!marked[w]){
                color[w]=!color[v];
                dfs(graph,w);
            }else if (color[w]==color[v]){
                isTwoColorable=false;
                break;
            }
        }
    }

PartTwo:有向图相关算法
有向图的定义和无向图基本一样，这里也是基于临接表实现，但在插入边的时候，有向图只需要操作边的始点的邻接表，不需像无向图一样两个顶点的邻接表都插入对应的顶点。
public class Digraph {
    private final int V;
    private int E;
    private Bag<Integer>[] adj;

    public Digraph(int v) {
        V = v;
        this.E=0;
        adj=new Bag[V];
        for (int i = 0; i < v; i++) {
            adj[i]=new Bag<>();
        }
    }
    public int V(){
        return V;
    }
    public int E(){
        return E;
    }
    public void addEdge(int v,int w){
        adj[v].add(w);
        E++;
    }
    public Iterable<Integer> adj(int v){
        return adj[v];
    }
    /**
    * 获取当前有向图的反转图
    */
    public Digraph reverse(){
        Digraph R=new Digraph(V);
        for (int v = 0; v < V; v++) {
            for (int w: adj(v)){
                R.addEdge(w,v);
            }
        }
        return R;
    }
}


一、有向图的可达性：
这里同无向图一样，只需将Graph换为Digraph即可：

进行DFS遍历:
public class DirectedDFS {
    private boolean[] marked;

    /**
     * 单点可达性
     * 经过此方法，从marked(int v)返回是否存在一条从s到达给定顶点v的有向路径
     * @param digraph
     * @param s
     */
    public DirectedDFS(Digraph digraph,int s) {
        marked=new boolean[digraph.V()];
        dfs(digraph,s);
    }

    /**
     * 多点可达性
     * 是否存在一条从集合中的任意顶点到达给定顶点v的有向路径
     * @param digraph
     * @param sources
     */
    public DirectedDFS(Digraph digraph,Iterable<Integer> sources) {
        marked=new boolean[digraph.V()];
        for (int s:sources){
            if (!marked[s]){
                dfs(digraph,s);
            }
        }

    }

    private void dfs(Digraph digraph, int v) {
        marked[v]=true;
        for (int w:digraph.adj(v)){
            if (!marked[w]){
                dfs(digraph,w);
            }
        }
    }

    public boolean marked(int v){
        return marked[v];
    }

    public static void main(String[] args) {
        Digraph graph=new Digraph(6);
        graph.addEdge(0,2);
        graph.addEdge(0,1);
        graph.addEdge(0,5);
        graph.addEdge(2,1);
        graph.addEdge(2,3);
        graph.addEdge(4,5);

        DirectedDFS dfs=new DirectedDFS(graph,0);
        System.out.println(dfs.marked(3));

    }

}


顶点对的可达性
借助DirectedDFS数组，我们可以实现顶点对的可达性：

无论对于稀疏还是稠密的图，它都是理想的解决方案，但不适用于实际应用中的大型有向图，因为构造函数所需的空间和V²成正比，所需时间和V（V+E）成正比
public class TransitiveClosure {
    private DirectedDFS[] directedDFS;  // tc[v] = reachable from v

    /**
     * 构造函数
     * 所需空间与V²成正比
     * 所需时间与 V(V+E)成正比
     * @param G
     */
    public TransitiveClosure(Digraph G) {
        directedDFS = new DirectedDFS[G.V()];
        for (int v = 0; v < G.V(); v++)
            directedDFS[v] = new DirectedDFS(G, v);
    }

    boolean reachable(int v,int w){
        return directedDFS[v].marked(w);
    }

}


二、单点有向路径和单点最短有向路径
同无向图一样，单点有向路径就是借助DFS，对从s到v路径上的每一个顶点，使用edgeTo数组保存从s到该顶点的路径上的最后一个顶点坐标；而单点最短路径就是以同样的方式借助BFS保存从s到指定顶点的路径，这样得出的路径就是到达该顶点的最短路径。
三、环和无环图（拓扑排序）
在调度问题中，限制条件是这些任务的执行方法和起始时间，但最重要的限制条件叫做有限制级限制，它指明了任务间执行的先后顺序。
我们需要在一个有优先级限制的任务中，按该限制条件找出安排完成任务的顺序。这也等价于一个基本问题：拓扑排序，即在一个有向图中，将所有顶点排序，满足所有的有向边均从排在前面的元素指向排在后面的元素（或指出无法做到这一点）。
以高校课程安排为例，一些课程的开课必须要求学生修完前面的某些课，而拓扑排序就是在这种限制条件下，找出学生选修课程的顺序。
而一旦一个优先级限制的问题中存在有向环，那么这个问题一定是无解的。因此我们需要进行有向环的检测。

有向无环图就是不含有有向环的有向图
检测有向环的思路如下：

对有向图的每个顶点都进行DFS遍历，假设从顶点v开始深度优先遍历，将从该顶点递归调用路径上的所有顶点marked标记后再使用一个boolean[] onStack标记是否在递归栈上，如果对一个顶点的DFS递归调用没有发现有向环，则递归结束前再让该节点的onStack状态改为false；而如果对某个顶点的递归调用时发现另一个顶点已经被标记了，且onStack为true，则说明这个路径上一定存在有向环，这时将该环上的所有点加入Stack cycle栈中。
public class DirectedCycle {
    private boolean[]marked;
    private int[] edgeTo;
    /**
     * 有向环中的所有顶点（如果存在）
     */
    private Stack<Integer>cycle;

    /**
     * 递归调用的栈上的所有顶点
     */
    private boolean[] onStack;

    public DirectedCycle(Digraph digraph) {
        marked=new boolean[digraph.V()];
        edgeTo=new int[digraph.V()];
        onStack=new boolean[digraph.V()];
        for (int v = 0; v < digraph.V(); v++) {
            if (!marked[v]){
                dfs(digraph,v);
            }
        }
    }

    /**
     * 使用不带权的Digraph
     * @param digraph
     * @param v
     */
    private void dfs(Digraph digraph, int v) {
        onStack[v]=true;
        marked[v]=true;
        for (int w: digraph.adj(v)){
            if (this.hasCycle()){
            //如果已经找到有向环，则返回
                return;
            } else if (!marked[w]){
                edgeTo[w]=v;
                dfs(digraph,w);
            }else if (onStack[w]){
                cycle=new Stack<>();
                for (int x = v; x != w; x=edgeTo[x]) {
                    cycle.push(x);
                }
                cycle.push(w);
                cycle.push(v);
            }
        }
        //对v的一次递归调用后，如果没发现环，则重置为false
        onStack[v]=false;

    }
    public Iterable<Integer>cycle(){
        return cycle;
    }
    public boolean hasCycle(){
        return cycle!=null;
    }
}


测试：
public static void main(String[] args) {
        Digraph digraph=new Digraph(4);
        digraph.addEdge(0,1);
        digraph.addEdge(2,3);
        digraph.addEdge(3,1);
        digraph.addEdge(1,2);
        //存在环3>1->2>3
        DirectedCycle cycle = new DirectedCycle(digraph);
        if (cycle.hasCycle()){
            System.out.println("存在环");
            Stack<Integer> stack = cycle.cycle;
            while (!stack.isEmpty()){
                System.out.println(stack.pop());
            }
        }
    }

结果：
存在环
3
1
2
3

《算法4》中给出：

一幅有向无环图的拓扑排序就是所有顶点的逆后排序

那么什么是逆后排序呢？

我们规定：

前序： 在对顶点v递归调用前就将该顶点加入队列，最后出队的顺序就是前序

后序：在对顶点v递归调用后将该顶点加入队列，最后出队的顺序就是后序

逆后序：在对顶点v递归调用后将该顶点加入栈中，最后出栈的顺序就是逆后序
实现如下：
/**
 * 有向图中基于深度优先搜索的顶点排序
 * @author MaoLin Wang
 * @date 2020/2/2214:55
 */
public class DepthFirstOrder {
    private boolean[]marked;
    /**
     * 所有顶点的前序遍历(递归调用前加入队列)
     */
    private Queue<Integer> pre;
    /**
     * 所有顶点的后序遍历(递归调用后加入队列)
     */
    private Queue<Integer> post;
    /**
     * 所有顶点的逆后序遍历(递归调用后压入栈)
     */
    private Stack<Integer> reversePost;

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

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

    }

     private void dfs(Digraph digraph, int v) {
        System.out.println("dfs("+v+")");

        pre.enqueue(v);
        marked[v]=true;
        for (int w: digraph.adj(v)){
            if (!marked[w]){
                dfs(digraph,w);
            }
        }
        System.out.println(v+"完成");

        post.enqueue(v);
        reversePost.push(v);
    }

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

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


我们先测试一下一张有向无环图的各个排序的顺序：
public static void main(String[] args) {
        Digraph digraph = new Digraph(13);
        digraph.addEdge(0,5);
        digraph.addEdge(0,1);
        digraph.addEdge(0,6);
        digraph.addEdge(2,0);
        digraph.addEdge(2,3);
        digraph.addEdge(3,5);
        digraph.addEdge(5,4);
        digraph.addEdge(6,4);
        digraph.addEdge(6,9);
        digraph.addEdge(7,6);
        digraph.addEdge(8,7);
        digraph.addEdge(9,10);
        digraph.addEdge(9,11);
        digraph.addEdge(9,12);
        digraph.addEdge(11,12);
        DepthFirstOrder depthFirstOrder = new DepthFirstOrder(digraph);
        Stack<Integer> reversePost = depthFirstOrder.reversePost;


    }

调用结果及形成的队列如下：

边的构造顺序不一样，得到的拓扑排序也会不一样，但是结果一定是满足拓扑排序优先级限制的。
			  pre     			   post				 			reversePost
dfs(0)  	  0
  dfs(6)	  0 6
    dfs(9)    0 6 9
	  dfs(12) 0 6 9 12 
	  12完成 						12							 12
	  dfs(11) 0 6 9 12 11
	  11完成						12 11						 11 12
	  dfs(10)0 6 9 12 11 10			    					
	  10完成						12 11 10    		 		 10 11 12
	9完成							12 11 10 9					 9 10 11 12
    dfs(4)	0 6 9 12 11 10 4			
	4完成							12 11 10 9 4            	 4 9 10 11 12
  6完成								12 11 10 9 4 6 				 6 4 9 10 11 12
dfs(1)		0 6 9 12 11 10 4 1	
1完成								12 11 10 9 4 6 1 			 1 6 4 9 10 11 12
dfs(5)		0 6 9 12 11 10 4 1 5
5完成								12,11,10,9,4,6,1,5 			 5 1 6 4 9 10 11 12
0完成								12,11,10,9,4,6,1,5,0    	 0,5,1,6,4,9,10,11,12
dfs(2)	   0,6,9,12,11,10,4,1,5,2		
 dfs(3)    0,6,9,12,11,10,4,1,5,2,3
 3完成								12,11,10,9,4,6,1,5,0,3  	 3,0,5,1,6,4,9,10,11,12
2完成								12,11,10,9,4,6,1,5,0,3,2     2,3,0,5,1,6,4,9,10,11,12
dfs(7)     0,6,9,12,11,10,4,1,5,2,3,7
7完成   							12,11,10,9,4,6,1,5,0,3,2,7   7,2,3,0,5,1,6,4,9,10,11,12
dfs(8)
8完成								12,11,10,9,4,6,1,5,0,3,2,7,8   8,7,2,3,0,5,1,6,4,9,10,11,12

我们发现其逆后序就是我们要的拓扑排序，那么为什么逆后序就是拓扑排序呢？

对于任意边v->w，调用dfs(v)时，一定会出现以下三种情况之一：

1.dfs（w）已调用过，且已经结束（w被标记过了）

2.dfs（w）未被调用（w没被标记），因此dfs（v）时会调用dfs（w），且dfs(w)会在dfs(v)之前返回

3.dfs（w）被调用过了，且没有返回。这个就是有有向环时会出现的情况，但进行拓扑排序的前提的没有有向环，因为该情况不会出现。

因此 情况1和2都是w在v之前结束调用，则w在后序排序中，一定在v之前，相反，在逆后序中，w一定在v之后，因此对于任意v->w都是排名较前点指向排名较后的点。

这样我们就可以得到拓扑排序的实现：
public class TopologicalSort {
    //顶点的拓扑排序
    private Iterable<Integer>order;

    public TopologicalSort(Digraph digraph) {
        DirectedCycle directedCycle=new DirectedCycle(digraph);
        //排序前进行有向环检测，没有环才可以进行拓扑排序
        if (!directedCycle.hasCycle()){
            //返回拓扑排序
            DepthFirstOrder dfs=new DepthFirstOrder(digraph);
            order=dfs.reversePost();
        }

    }


    public Iterable<Integer>order(){
        return order;
    }
    public boolean hasOrder(){
        return order!=null;
    }
}

四、有向图的强连通性
定义：

如果两个顶点是互相可达的，则称是强连通的。如果一个有向图的任意两个顶点都是强连通的，则该有向图是强连通的。

有向图的极大强连通子图，称为强连通分量(strongly connected components)。

如下：每个颜色代表一个强联通分量。



计算强连通分量的最常用的方法是Kosaraju算法：

其思想是：

1.使用DFS查找给定有向图G的反向图G^R

2.根据反向图G^R求得其逆后序列

3.对2求得的逆后序进行DFS遍历，访问未被标记的点

4.在构造函数中，所有在同一个dfs调用中被访问的顶点都在同一个强连通分量中，按无向图中求连通分量的方法求强连通分量。
有关该思想的证明如下：

我们只要证明以下两个问题即可：

（树上的证明猛一看可能看的不太懂，下面用自己的理解讲的细一点）

1.每个和s强连通的顶点v都会在构造函数调用的dfs(G,s)中被访问到

2.构造函数调用的dfs(G,s)所到达的任意顶点v都必然是和s强连通的。
对命题1，我们使用反证法：

1.假设一个和s强连通的顶点v在dfs(G,s)的调用中没有被访问到

2.由于存在一条从s->v的路径，所以如果顶点v没有在dfs(G,s)中被访问，就一定在之前调用了dfs(G,v)，并且访问到了v。

3.又因为s和v是强连通的，所以也存在v->s的路径，在dfs(G,v)中，s一定会被标记，而s被标记，就一定不会再次进行dfs(G,s)的调用，矛盾，因此命题1成立。
对命题2：

1.要证明s和任意顶点v强连通，只要证明s->v且v->s，因为v是dfs(G,s)调用中访问到的任意顶点，所以一定存在s->v，接下来只要证明存在v->s即可。

2.要证明存在v->s，就相当于证明反向图中存在s1->v1

如下：



因为我们是按照逆后序进行深度优先遍历的，按照逆序，我们是在dfs(G,s)的调用中调用dfs(G,v)，即先访问s再访问v，所以在反向图GR中，我们就应该是先访问v再访问s，对应上图GR中的点就是，先访问s1再访问v1。

即只要证明dfs(G,v1)在dfs（G,s1）之前结束，则这样就有如下两个情况：
1. dfs（G，v1）在调用dfs(G,s1)之前，且在dfs（G，s1）的调用开始前结束。

2. dfs（G，v1）在调用dfs（G,s1）之后，且在dfs（G,s1）的调用结束前结束。
如果出现情况1，这显然不可能，因为如果v1在s1之前就结束了，那么得出的逆后序应该是s1,v1，对应G中的v和s，先调用v再调用s，但是显然G是先调用s再调用v，所以该情况不存在。

如果是情况2，则说明存在一条路径s1>v1，即原图G中存在一条路径v->s，命题2正确。
下面是Kosaraju算法的实现：
/**
 * 计算强连通分量的Kosaraju算法
 * @author MaoLin Wang
 * @date 2020/2/2216:54
 */
public class KosarajuSCC {
    private boolean[] marked;
    /**
     * 强连通分量的标识符
     */
    private int[] id;
    /**
     * 强连通分量个数
     */
    private int count;

    public KosarajuSCC(Digraph digraph){
        marked=new boolean[digraph.V()];
        id=new int[digraph.V()];
        //求反向图的逆后序
        DepthFirstOrder order=new DepthFirstOrder(digraph.reverse());
        //对逆后序进行dfs遍历
        for(int s: order.reversePost()){
            if (!marked[s]){
                dfs(digraph,s);
                count++;
            }
        }
    }

    private void dfs(Digraph digraph, int v) {
        marked[v]=true;
        //顶点v属于第count个强连通分量
        id[v]=count;
        for (int w: digraph.adj(v)){
            if (!marked[w]){
                dfs(digraph,w);
            }
        }
    }
    /*v和w是否强连通*/
    public boolean stronglyConnected(int v,int w){
        return id[v]==id[w];
    }
    public int id(int v){
        return id[v];
    }
    public int count(){
        return count;
    }
}

c方式的强制类型转换存在的问题 
过于粗暴 
任意之间都可以进行转换，编译器很难判断其正确性
难于定位 

    - 在源码中无法快速定位所有使用强制类型转换的语句
c++的强制类型转换分为四种


static_cast
const_cast
dynamic_cast
reinterpret_cast 



  用法： xxx_cast(Expression) 
static_cast
  
用于基本类型间的转换
  
不能用于基本类型指针间的转换
  
==用于==有继承关系类对象之间的转换和类指针的转换
  
const_cast
  
用于去除变量的只读属性
  
强制转换的目标==必须是指针或者引用==
  
reinterpret_cast
  
用于指针类型间的强制转换
  
用于整数和指针类型间的强制转换
  
dynamic_cast
  
用于有继承关系的类指针间的转换
  
用于有交叉关系的类指针间的转换
  
具有类型检查的功能
  
需要虚函数的支持


#include <stdio.h>

void static_cast_demo()
{
    int i = 0x12345;
    char c = 'c';
    int* pi = &i;
    char* pc = &c;

    c = static_cast<char>(i);
    pc = static_cast<char*>(pi);//error
}

void const_cast_demo()
{
    const int& j = 1;
    int& k = const_cast<int&>(j);

    const int x = 2;                //进入符号表
    int& y = const_cast<int&>(x);

    int z = const_cast<int>(x); //error

    k = 5;

    printf("k = %d\n", k);   //k = 5
    printf("j = %d\n", j);   // j = 5

    y = 8;

    printf("x = %d\n", x);   // x = 2
    printf("y = %d\n", y);   // y = 8
    printf("&x = %p\n", &x);  //&x  和&y相同
    printf("&y = %p\n", &y);
}

void reinterpret_cast_demo()
{
    int i = 0;
    char c = 'c';
    int* pi = &i;
    char* pc = &c;

    pc = reinterpret_cast<char*>(pi);
    pi = reinterpret_cast<int*>(pc);
    pi = reinterpret_cast<int*>(i);
    c = reinterpret_cast<char>(i); //error
}

void dynamic_cast_demo()
{
    int i = 0;
    int* pi = &i;
    char* pc = dynamic_cast<char*>(pi); //error
}

int main()
{
    static_cast_demo();
    const_cast_demo();
    reinterpret_cast_demo();
    dynamic_cast_demo();

    return 0;
}

本文转载自：https://yq.aliyun.com/articles/307547

分布式锁一般存在三种实现方式，1、通过数据库的乐观锁；2、redis  3、ZooKeeper。

本文将介绍一下第二种方式，基于redis实现分布式锁，其实网上有很多代码，但都多多少少存在不同的问题，它们根本不能满足分布锁的要求。本篇博客将详细介绍如何正确地实现Redis分布式锁。

可靠性

首先，为了确保分布式锁可用，我们至少要确保锁的实现同时满足以下四个条件：

互斥性。在任意时刻，只有一个客户端能持有锁。

不会发生死锁。即使有一个客户端在持有锁的期间崩溃而没有主动解锁，也能保证后续其他客户端能加锁。

具有容错性。只要大部分的Redis节点正常运行，客户端就可以加锁和解锁。

解铃还须系铃人。加锁和解锁必须是同一个客户端，客户端自己不能把别人加的锁给解了。

代码实现

组件依赖

首先我们要通过Maven引入Jedis开源组件，在pom.xml文件加入下面的代码：

<dependency>
    <groupId>redis.clients</groupId>
    <artifactId>jedis</artifactId>
    <version>2.9.0</version>
</dependency>

加锁代码

正确姿势

Talk is cheap, show me the code。先展示代码，再解释为什么这样实现：

    /**
     *
     * @param lockKey 分布式锁key
     * @param requestId 锁的值
     * @param acquireTimeout 尝试获取锁的超时时间，单位毫秒
     * @param expireTime 锁的过期时间，单位毫秒
     * @return
     */
    public boolean tryLock(String lockKey,String requestId,long acquireTimeout,long expireTime){

        long end = System.currentTimeMillis() + acquireTimeout;
        while(System.currentTimeMillis() < end){
            String result = jedis.set(lockKey, requestId, SET_IF_NOT_EXIST, SET_WITH_EXPIRE_TIME, expireTime);

            if (LOCK_SUCCESS.equals(result)) {
                return true;
            }
            try {
                //尝试获取锁失败，休眠10ms再试
                Thread.sleep(10);
            } catch (InterruptedException e) {
                Thread.currentThread().interrupt();
                log.error("RedisLock中断异常",e);
                return false;
            }
        }
        return false;
    }

可以看到，我们加锁就一行代码：jedis.set(String key, String value, String nxxx, String expx, int time)，这个set()方法一共有五个形参：

第一个为key，我们使用key来当锁，因为key是唯一的。

第二个为value，我们传的是requestId，很多童鞋可能不明白，有key作为锁不就够了吗，为什么还要用到value？原因就是我们在上面讲到可靠性时，分布式锁要满足第四个条件解铃还须系铃人，通过给value赋值为requestId，我们就知道这把锁是哪个请求加的了，在解锁的时候就可以有依据。requestId可以使用UUID.randomUUID().toString()方法生成。

第三个为nxxx，这个参数我们填的是NX，意思是SET IF NOT EXIST，即当key不存在时，我们进行set操作；若key已经存在，则不做任何操作；XX表示存在才进行set操作。

第四个为expx，这个参数我们传的是PX，表示key的过期时间单位为ms，EX表示过期时间单位为s

第五个为time，与第四个参数相呼应，代表key的过期时间。

总的来说，执行上面的set()方法就只会导致两种结果：1. 当前没有锁（key不存在），那么就进行加锁操作，并对锁设置个有效期，同时value表示加锁的客户端。2. 已有锁存在，不做任何操作。

如上代码，还加入了获取锁的一个超时时间(acquireTimeout)，在这段时间内一直尝试获取锁，如果超时还获取不到则返回false。

心细的童鞋就会发现了，我们的加锁代码满足我们可靠性里描述的三个条件。首先，set()加入了NX参数，可以保证如果已有key存在，则函数不会调用成功，也就是只有一个客户端能持有锁，满足互斥性。其次，由于我们对锁设置了过期时间，即使锁的持有者后续发生崩溃而没有解锁，锁也会因为到了过期时间而自动解锁（即key被删除），不会发生死锁。最后，因为我们将value赋值为requestId，代表加锁的客户端请求标识，那么在客户端在解锁的时候就可以进行校验是否是同一个客户端。由于我们只考虑Redis单机部署的场景，所以容错性我们暂不考虑。当然这里肯定可以通过redis机器来弥补容错性的问题。

错误示例1

比较常见的错误示例就是使用jedis.setnx()和jedis.expire()组合实现加锁，代码如下：

public static void wrongGetLock1(Jedis jedis, String lockKey, String requestId, int expireTime) {

    Long result = jedis.setnx(lockKey, requestId);
    if (result == 1) {
        // 若在这里程序突然崩溃，则无法设置过期时间，将发生死锁
        jedis.expire(lockKey, expireTime);
    }

}

setnx()方法作用就是SET IF NOT EXIST，expire()方法就是给锁加一个过期时间。乍一看好像和前面的set()方法结果一样，然而由于这是两条Redis命令，不具有原子性，如果程序在执行完setnx()之后突然崩溃，导致锁没有设置过期时间。那么将会发生死锁。网上之所以有人这样实现，是因为低版本的jedis并不支持多参数的set()方法。

错误示例2

这一种错误示例就比较难以发现问题，而且实现也比较复杂。实现思路：使用jedis.setnx()命令实现加锁，其中key是锁，value是锁的过期时间。执行过程：1. 通过setnx()方法尝试加锁，如果当前锁不存在，返回加锁成功。2. 如果锁已经存在则获取锁的过期时间，和当前时间比较，如果锁已经过期，则设置新的过期时间，返回加锁成功。代码如下：

public static boolean wrongGetLock2(Jedis jedis, String lockKey, int expireTime) {

    long expires = System.currentTimeMillis() + expireTime;
    String expiresStr = String.valueOf(expires);

    // 如果当前锁不存在，返回加锁成功
    if (jedis.setnx(lockKey, expiresStr) == 1) {
        return true;
    }

    // 如果锁存在，获取锁的过期时间
    String currentValueStr = jedis.get(lockKey);
    if (currentValueStr != null && Long.parseLong(currentValueStr) < System.currentTimeMillis()) {
        // 锁已过期，获取上一个锁的过期时间，并设置现在锁的过期时间
        String oldValueStr = jedis.getSet(lockKey, expiresStr);
        if (oldValueStr != null && oldValueStr.equals(currentValueStr)) {
            // 考虑多线程并发的情况，只有一个线程的设置值和当前值相同，它才有权利加锁
            return true;
        }
    }

    // 其他情况，一律返回加锁失败
    return false;

}

那么这段代码问题在哪里？1. 由于是客户端自己生成过期时间，所以需要强制要求分布式下每个客户端的时间必须同步。 2. 当锁过期的时候，如果多个客户端同时执行jedis.getSet()方法，那么虽然最终只有一个客户端可以加锁，但是这个客户端的锁的过期时间可能被其他客户端覆盖。3. 锁不具备拥有者标识，即任何客户端都可以解锁。

解锁代码

正确姿势

还是先展示代码，再带大家慢慢解释为什么这样实现：

    /**
     * 尝试释放分布式锁
     * @param lockKey
     * @param requestId
     */
    public boolean tryRelease(String lockKey,String requestId){
        String script = "if redis.call('get', KEYS[1]) == ARGV[1] then return redis.call('del', KEYS[1]) else return 0 end";
        Object result = jedis.eval(script, Collections.singletonList(lockKey), Collections.singletonList(requestId));

        if (RELEASE_SUCCESS.equals(result)) {
            return true;
        }
        return false;
    }

可以看到，我们解锁只需要两行代码就搞定了！第一行代码，我们写了一个简单的Lua脚本代码，上一次见到这个编程语言还是在《黑客与画家》里，没想到这次居然用上了。第二行代码，我们将Lua代码传到jedis.eval()方法里，并使参数KEYS[1]赋值为lockKey，ARGV[1]赋值为requestId。eval()方法是将Lua代码交给Redis服务端执行。

那么这段Lua代码的功能是什么呢？其实很简单，首先获取锁对应的value值，检查是否与requestId相等，如果相等则删除锁（解锁）。

那么为什么要使用Lua语言来实现呢？因为要确保上述操作是原子性的。关于非原子性会带来什么问题，可以阅读【解锁代码-错误示例2】 。

那为什么执行eval()方法可以确保原子性，源于Redis的特性，下面是官网对eval命令的部分解释：

简单来说，就是在eval命令执行Lua代码的时候，Lua代码将被当成一个命令去执行，并且直到eval命令执行完成，Redis才会执行其他命令。

错误示例1

最常见的解锁代码就是直接使用jedis.del()方法删除锁，这种不先判断锁的拥有者而直接解锁的方式，会导致任何客户端都可以随时进行解锁，即使这把锁不是它的。

public static void wrongReleaseLock1(Jedis jedis, String lockKey) {
    jedis.del(lockKey);
}

错误示例2

这种解锁代码乍一看也是没问题，甚至我之前也差点这样实现，与正确姿势差不多，唯一区别的是分成两条命令去执行，代码如下：

public static void wrongReleaseLock2(Jedis jedis, String lockKey, String requestId) {

    // 判断加锁与解锁是不是同一个客户端
    if (requestId.equals(jedis.get(lockKey))) {
        // 若在此时，这把锁突然不是这个客户端的，则会误解锁
        jedis.del(lockKey);
    }

}

如代码注释，问题在于如果调用jedis.del()方法的时候，这把锁已经不属于当前客户端的时候会解除他人加的锁。那么是否真的有这种场景？答案是肯定的，比如客户端A加锁，一段时间之后客户端A解锁，在执行jedis.del()之前，锁突然过期了，此时客户端B尝试加锁成功，然后客户端A再执行del()方法，则将客户端B的锁给解除了。

总结

本文主要介绍了如何使用Java代码正确实现Redis分布式锁，对于加锁和解锁也分别给出了两个比较经典的错误示例。其实想要通过Redis实现分布式锁并不难，只要保证能满足可靠性里的四个条件。

分布锁主要是用在什么场景？需要同步的地方，比如说插入一条数据，需要事先检查数据库是否有类似的数据，多个请求同时插入的时候，可能会判断到数据库都返回没有类似的数据，则都可以加入。这时候需要进行同步处理，但是直接数据库锁表太耗时间，所以采用redis分布式锁，同时只能有一个线程去进行插入数据这个操作，其他的线程都等待。

如果你的项目中Redis是多机部署的，那么可以尝试使用Redisson实现分布式锁，这是Redis官方提供的Java组件，链接在参考阅读章节已经给出。