若干定义
图范指由顶点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);
}
