若干定義
圖范指由頂點(diǎn)V(vetex)和邊(edge)組成的集合褒颈，可以表示G=(V,E).
有向圖，無(wú)向圖
頂點(diǎn)之間有順序?yàn)橛邢驁D，無(wú)順序?yàn)闊o(wú)向圖
有圈圖隶债，無(wú)圈圖
存在從頂點(diǎn)到自身的路徑秉溉，稱為有圈圖力惯，否則稱為無(wú)圈圖
有向圖的表示
1.二維數(shù)組表示法：
A[u][v] = true 表示存在從u到v的邊，否則不存在
其中true也可以用權(quán)值表示召嘶，用一個(gè)非常大或者非常小的值表示不存在的邊
空間需求:|v|的平方父晶，也就是頂點(diǎn)個(gè)數(shù)的平方
有點(diǎn)：簡(jiǎn)單明了
缺點(diǎn)：對(duì)于邊多的圖合適，但是對(duì)于稀疏的圖弄跌，效率較低
2.鄰接表示法：
通過(guò)Map表示甲喝，key為頂點(diǎn)值，value為頂點(diǎn)值對(duì)對(duì)應(yīng)的頂點(diǎn)組合
拓?fù)渑判?/h4>
對(duì)于有向無(wú)圈圖的一種排序铛只，拓?fù)渑判蚩赡懿恢挂粋€(gè)結(jié)果埠胖。
如下圖所示：v1-v2-v5-v4-v3-v7-v6和v1-v2-v5-v4-v7-v3-v6都是正確的拓?fù)渑判颉?/p>
拓?fù)渑判騻未a
最短路徑算法
對(duì)于賦權(quán)圖，計(jì)算點(diǎn)到點(diǎn)的最短路徑所用到的算法就是最短路徑算法淳玩。解決單源最短路徑算法一般叫做Dijkstra算法直撤。也屬于貪婪算法的一個(gè)例子。假如有如下有項(xiàng)圖G：
要計(jì)算從V1->V6的最短路徑蜕着，下面是具體的代碼實(shí)現(xiàn)：
int max = 10000;
//graph定義了任意點(diǎn)到點(diǎn)的權(quán)值谊惭，如果連個(gè)點(diǎn)之間不連通，則值為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]; //保存了每個(gè)節(jié)點(diǎn)最短路徑的前置節(jié)點(diǎn)
int []cost = new int[6]; //保存每個(gè)節(jié)點(diǎn)的最短路徑值
具體實(shí)現(xiàn)函數(shù)：
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)//如果是出發(fā)點(diǎn)
{
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個(gè)
{
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 獲取最小權(quán)值的節(jié)點(diǎn)
if (curNode == -1) break;//剩下都是不可通行的節(jié)點(diǎn)，跳出循環(huán)
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];//更新權(quán)值
path[w] = curNode;//更新路徑
}
}//for 更新其他節(jié)點(diǎn)的權(quán)值（距離）和路徑
}//
}
執(zhí)行結(jié)果：
節(jié)點(diǎn)最短路徑值cost:v1-0,v2-2,v3-3,v4-1,v5-3,v6-6,v7-5,
前置節(jié)點(diǎn)path:0,0,3,0,3,6,3,
網(wǎng)絡(luò)流問(wèn)題
低于有向圖悄雅，有一種情況驱敲，邊上的權(quán)值表示可以通過(guò)此邊的最大流量，因此宽闲，求兩個(gè)點(diǎn)之間的最大流量众眨，稱為網(wǎng)絡(luò)流網(wǎng)體握牧，這種算法也稱為求最大流算法。假如有如下有向圖：
要求從s到t的最大流娩梨，一種簡(jiǎn)單的算法沿腰，先找出一條從s到t的有效路徑，這條路徑所能通多的最大流量為此條路徑的最小值狈定，之后把此條路徑的經(jīng)過(guò)的邊減去當(dāng)前所得的流量值颂龙。然后再重復(fù)操作，直到無(wú)法找到從s到t的有效路徑為止纽什。
具體代碼實(shí)現(xiàn)：
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);
}
