图论算法

若干定义

图范指由顶点V(vetex)和边(edge)组成的集合，可以表示G=(V,E).

有向图，无向图

顶点之间有顺序为有向图，无顺序为无向图

WX20190418-161310@2x.png

有圈图，无圈图

存在从顶点到自身的路径，称为有圈图，否则称为无圈图

有向图的表示

1.二维数组表示法：
A[u][v] = true 表示存在从u到v的边，否则不存在
其中true也可以用权值表示，用一个非常大或者非常小的值表示不存在的边
空间需求:|v|的平方，也就是顶点个数的平方
有点：简单明了
缺点：对于边多的图合适，但是对于稀疏的图，效率较低
2.邻接表示法：
通过Map表示，key为顶点值，value为顶点值对对应的顶点组合

WX20190418-163257@2x.png

拓扑排序

对于有向无圈图的一种排序，拓扑排序可能不止一个结果。
如下图所示：v1-v2-v5-v4-v3-v7-v6和v1-v2-v5-v4-v7-v3-v6都是正确的拓扑排序。

WX20190508-141508@2x.png

拓扑排序伪代码

WX20190522-161053@2x.png

最短路径算法

对于赋权图，计算点到点的最短路径所用到的算法就是最短路径算法。解决单源最短路径算法一般叫做Dijkstra算法。也属于贪婪算法的一个例子。假如有如下有项图G：

WX20190527-100002@2x.png

要计算从V1->V6的最短路径，下面是具体的代码实现：

        int max = 10000;
        //graph定义了任意点到点的权值，如果连个点之间不连通，则值为max
        int[][] graph = {
                {max,2,max,1,max,max,max},
                {max,max,max,3,10,max,max},
                {4,max,max,max,max,5,max},
                {max,max,2,max,2,8,4},
                {max,max,max, max,max, max,6},
                {max,max,max,max,max,max,max},
                {max,max,max,max,max,1,max}
        };
        int []path = new int[6]; //保存了每个节点最短路径的前置节点
        int []cost = new int[6]; //保存每个节点的最短路径值

具体实现函数：

 public static void findShortestPath(int[][] graph,int startIndex, int[] path, int[] cost,int max)
    {
        int nodeCount = graph.length;
        Boolean[] v = new Boolean[nodeCount];
        //初始化 path，cost，V
        for (int i = 0; i <nodeCount ; i++)
        {
            if (i == startIndex)//如果是出发点
            {
                v[i] = true;//
            }
            else
            {
                cost[i] = graph[startIndex][i];
                if (cost[i] < max) path[i] = startIndex;
                else path[i] = -1;
                v[i] = false;
            }
        }
        //
        for(int i=1;i<nodeCount;i++)//求解nodeCount-1个
        {
            int minCost = max ;
            int curNode=-1;
            for (int w = 0; w < nodeCount; w++)
            {
                if (!v[w])//未在V集合中
                {
                    if(cost[w]<minCost)
                    {
                        minCost = cost[w];
                        curNode = w;
                    }
                }
            }//for  获取最小权值的节点
            if (curNode == -1) break;//剩下都是不可通行的节点，跳出循环
            v[curNode] = true;
            for (int w = 0; w < nodeCount; w++)
            {
                if (!v[w] && (graph[curNode][w] + cost[curNode] < cost[w]))
                {
                    cost[w] = graph[curNode][w] + cost[curNode];//更新权值
                    path[w] = curNode;//更新路径
                }
            }//for 更新其他节点的权值（距离）和路径
        }//
    }

执行结果：

节点最短路径值cost:v1-0,v2-2,v3-3,v4-1,v5-3,v6-6,v7-5,
前置节点path:0,0,3,0,3,6,3,

网络流问题

低于有向图，有一种情况，边上的权值表示可以通过此边的最大流量，因此，求两个点之间的最大流量，称为网络流网体，这种算法也称为求最大流算法。假如有如下有向图：

WX20190528-135652@2x.png

要求从s到t的最大流，一种简单的算法，先找出一条从s到t的有效路径，这条路径所能通多的最大流量为此条路径的最小值，之后把此条路径的经过的边减去当前所得的流量值。然后再重复操作，直到无法找到从s到t的有效路径为止。

具体代码实现：

private boolean getPath(int[][] graph,int start ,int end){
        Boolean[] vistor = new Boolean[end-start+1];
        for(int i = 0; i <= end ;i++){
            pre[i] = -1;
            vistor[i] = false;
        }
        vistor[start] = true;
        Queue<Integer> queue = new ArrayDeque<>();
        queue.offer(start);
        while(queue.size() > 0){
            int index = queue.poll();
            for(int i = 0;i<= end;i++){
                if(graph[index][i] > 0 && !vistor[i]){
                    queue.offer(i);
                    pre[i] = index;
                    vistor[i] = true;
                    if(i == end){
                        return true;
                    }
                }
            }
        }
        return false;
    }

    private void calMaxFlow(int[][] graph,int start, int end){
        int maxFlow = 0;
        while(getPath(graph,start,end)){
            int min = 10000;
            for(int n = end; n != 0; n = pre[n]){
                if(graph[pre[n]][n] < min){
                    min = graph[pre[n]][n];
                }
            }
            for(int n = end; n!=start;n = pre[n]){
                graph[pre[n]][n] -= min;
                graph[n][pre[n]] += min;
            }
            maxFlow += min;
        }
        System.out.printf("maxFlow:"+maxFlow);
    }