目錄導讀：
- 1.基本概念
- 2.圖的存儲概念(5中方式)
鄰接矩陣
鄰接表
- 3.圖的遍歷
深度優(yōu)先遍歷
廣度優(yōu)先遍歷
- 4.最小生成樹
普里姆算法(Prim)
克魯斯卡爾算法(kruskal)
- 5.最短路徑
迪杰斯特拉算法(Dijkstra)
佛羅伊德算法(Floyd)
- 6.拓撲排序
- 6.關(guān)鍵路徑
1.圖(Graph)
由頂點的有窮非空集合和頂點之間邊的集合組成颠通，通常表示為：G(V,E)
其中，G 表示一個圖倘零，V 是圖G中頂點的集合谎仲，E是圖G中邊的集合
注意：
- 圖的頂點集 V 不可以為空，至少要為1,但是邊集 E 可以為空算行。
- 線性表中數(shù)據(jù)元素叫元素梧油，樹中數(shù)據(jù)元素叫結(jié)點，圖中數(shù)據(jù)元素叫頂點
2.若干個定義
無向邊(Edge):(vi, vj) ——> 無向圖：圖中所有邊均為無向邊
有向邊(Arc州邢，也稱為弧): <vi, vj> ——> 有向圖：圖中所有邊均有有向邊
簡單圖：不存在頂點到其自身的邊儡陨，且同一條邊也不重復。
完全圖：如果任意兩個頂點之間都存在邊
圖分類
(1)按邊分：
無向圖 （頂點+無向邊）
有向圖（頂點+有向邊(弧)）量淌，弧有弧頭和弧尾之分
(2)按邊的多少分：(這里是模糊概念)
稀疏圖
稠密圖
(3)按任意兩頂點之間是否相連
無向完全圖：任意兩個頂點之間都存在邊
有向完全圖：任意兩個頂點之間都存在邊且邊是有向的
無向完全圖的邊數(shù)：n(n-1)/2 (按等差數(shù)列來理解)
有向完全圖的邊數(shù)：n(n-1)
因此骗村，對于n個頂點和e條邊的圖來說有：
無向圖：0 ≤ e ≤ n(n-1)/2
有向圖：0 ≤ e ≤ n(n-1)
網(wǎng)(NetWork):圖的邊或弧有相關(guān)的數(shù)(該樹叫做權(quán)值weight)
子圖：
假設圖G=(V,{E})和圖G'=(V,{E'})有：
V' ≤ V ,這里應該用包含符號
E' ≤ E ,這里應該用包含符號
則有，G' ≤ G 稱G'是G的字圖（subgraph）
2)圖的頂點與邊的關(guān)系
無向圖 G = (V,{E})呀枢，邊(v,v')依附于頂點v,v'胚股，而v與v'互為鄰接
度：指針對具體的頂點而言的，指與該頂點相連的邊數(shù)裙秋。
各頂點度之和 = 1/2*邊數(shù)之和
有向圖 G = (V,{E}),弧<v,v'>和頂點v,v'相關(guān)聯(lián)琅拌，v鄰接到v'，v'鄰接自v
度 = 出度+入度
各頂點出度之和 = 入度之和 = 弧數(shù)之和
3)路徑
回環(huán)（回路）
簡單路徑
簡單回環(huán)
4)連通圖
在無向圖中残吩，任意兩個頂點之間都是連通的（即存在路徑）财忽，則稱該圖是"連通圖"
連通分量：又稱為無向圖中的極大連通子圖（換言之，就是盡可能多的的包含
頂點數(shù)的連通子圖）
注意連通分量的概念泣侮，它強調(diào)：
是子圖
子圖要連通
連通子圖包含"極大"頂點數(shù)即彪、
包含依附這些頂點的所有邊
在有向圖中，任意兩個頂點之間都是連通的(不一定是直接連通)，則稱該圖是"強連通圖"
強連通分量：又稱為有向圖中的極大強連通子圖
5）生成樹
針對連通圖而言的隶校。是連通圖的一個極小的連通子圖漏益，它含有圖中全部的 n 個頂點，n-1 條邊
注意：最小生成樹深胳，生成樹中構(gòu)造連通網(wǎng)的代價最小的生成樹稱為最小生成樹
6）有向樹
在有向圖中绰疤，只有一個頂點的入度為0，求余頂點的入度均為1
7）生成森林
3.圖的存儲結(jié)構(gòu)
由于圖的結(jié)構(gòu)復雜舞终，因此無法以數(shù)據(jù)元素在內(nèi)存中的物理存儲位置來反映元素之間
的邏輯關(guān)系
5種存儲結(jié)構(gòu)：
(1)鄰接矩陣(Adjacency Martix)
該存儲方式是用兩個數(shù)組來表示圖：一個一維數(shù)組存儲頂點信息轻庆，一個二維數(shù)組
存儲(稱為鄰接矩陣)圖中邊或弧的信息。
圖G(V,{E}) 有 n 個頂點敛劝，則其鄰接矩陣定義為：
┌ 1, 若(vi,vj)屬于E,此時可以看成權(quán)值為1
arc[i][j] = │
└ 0, 反之
注意：對于無向圖余爆，很容易得知該鄰接矩陣是對稱矩陣
有了鄰接矩陣求某一點的度就是該點所在的行或列元素之和
網(wǎng)G(V,{E}),有n個頂點，則其鄰接矩陣定義為：
┌ Wij, 若(vi,vj)屬于E,
│
arc[i][j] = │ 0, i = j;(自身到自身的權(quán)值是0)
│
└ ∞, 反之
V0 邊數(shù)組： 頂點數(shù)組：
╱ │ ╲ ┌ ┐ ┌──┬──┬──┬──┐
V1 │ V3 │0 1 1 1│ │V0│V1│V2│V3│
╲ │ ╱ │1 0 1 0│ └──┴──┴──┴──┘
V2 │1 1 0 1│
│1 0 1 0│
└ ┘
'鄰接矩陣存儲'數(shù)據(jù)結(jié)構(gòu)
import java.util.Scanner;
/**
* 圖夸盟、網(wǎng)的鄰接矩陣存儲方式
* @author Administrator
*
* @param <T>
*/
public class AdjMartix<T> {
private T[] vertexArr; //用于存放圖的頂點(一維數(shù)組)
private int[][] adjMar; //鄰接矩陣(二維數(shù)組),存放權(quán)值
private int vertexNum; //圖的頂點數(shù)
private int edgesNum; //圖的邊數(shù)
private final int MAX = 999; //表示網(wǎng)中權(quán)值是無窮大,數(shù)值可調(diào)
private final int MAXSIZE = 10; //鄰接矩陣中存儲頂點的最大默認數(shù)量
public AdjMartix() {
vertexArr = (T[])new Object[MAXSIZE];
adjMar = new int[MAXSIZE][MAXSIZE];
}
//創(chuàng)建無向圖的鄰接矩陣
public void createAdjMartix() {
Scanner sc = new Scanner(System.in);
System.out.print("請輸入圖的頂點數(shù)：");
vertexNum = sc.nextInt();
System.out.print("請輸入圖的邊數(shù)：");
edgesNum = sc.nextInt();
System.out.print("請輸入頂點信息：");
String ver = sc.next();
//初始化頂點存儲數(shù)組
for(int i = 0; i < ver.length(); i++) {
vertexArr[i] = (T)(Object)ver.charAt(i);
}
System.out.println("輸入邊的信息：");
for(int j = 0; j < edgesNum; j++) {
System.out.print("輸入第" + (j+1) + "條邊的兩個端點：");
String str = sc.next();
T v1 = (T)(Object)str.charAt(0);
T v2 = (T)(Object)str.charAt(1);
//獲取端點所在的位置
int h = locatVer(v1); //橫坐標
int v = locatVer(v2); //縱坐標
if(h >= 0 && v >= 0) {
//給鄰接矩陣賦值蛾方，
adjMar[h][v] = 1;
adjMar[v][h] = 1; //注意：無向圖的鄰接矩陣是對稱的
}
}
}
/**
* 根據(jù)端點獲得所在頂點數(shù)組中的存儲位置
* 如果存在就返回存儲位置，否則就返回-1
* @param t
* @return
*/
private int locatVer(T t) {
for(int i = 0; i < vertexArr.length; i++) {
if(vertexArr[i] == t) {
return i;
}
}
return -1; //表示不存在
}
}
(2)鄰接表(Adjacency List)
當圖中邊數(shù)遠小于頂點個數(shù)時(即稀疏圖)上陕，采用鄰接矩陣的話桩砰，就是造成極大的空間浪費。
因此释簿，我們可以考慮使用對邊或弧使用鏈式存儲的方式來避免空間浪費
數(shù)組和鏈表相結(jié)合的存儲方法稱為鄰接表亚隅。
data,firstedge
┌──┬──┐ adjvex(鄰接點域),next(邊表下一結(jié)點的指針)
V0 0 │V0│ │→ 1| → 2| → 3|^
╱ │ ╲ ├──┼──┤
V1 │ V3 1 │V1│ │→ 1| → 2|^
╲ │ ╱ ├──┼──┤
V2 2 │V2│ │→ 0| → 1| → 3|^
├──┼──┤
3 │V3│ │→ 0| → 2|^
└──┴──┘
鄰接表的建立：
1.建立頂點表：圖中頂點用一個一維數(shù)組存儲（用鏈表也可以，只是數(shù)組方便讀取頂點信息）
每個數(shù)據(jù)元素還需要存儲指向第一個鄰接點的指針辕万，便于查找該頂點的邊的信息
2.建立邊表：圖中每個頂點Vi的所有鄰接點構(gòu)成一個線性表枢步，由于每個頂點的鄰接點的個數(shù)
不定沉删，所以渐尿，采用單鏈表來存儲這些鄰接點。該線性表對于無向圖稱為頂點Vi的邊表矾瑰，
對于有向圖則稱為以頂點Vi為弧尾的出邊表砖茸。
注意:對于有向圖而言，以每個頂點為弧尾建立的鄰接表稱為鄰接表(便于得到頂點的出度)
對于有向圖而言殴穴，以每個頂點為弧頭建立的鄰接表稱為逆鄰接表(便于得到頂點的入度)
對于網(wǎng)圖凉夯，可以在邊表結(jié)點定義中再增加一個weight的數(shù)據(jù)域，用于存儲權(quán)值
實現(xiàn)（看下面）該鄰接表的算法復雜度：O(n+e)采幌， n為頂點個數(shù)劲够，e為邊的條數(shù)
'代碼描述'
package chapter05.graph.storage;
import java.util.Scanner;
/**
* 圖的鄰接表的存儲方式
* VerNode： 表示頂點表的結(jié)構(gòu)
* ArcNode：表示邊表的結(jié)構(gòu)
* @author Administrator
*
*/
public class AdjListGraph<T> {
protected final int MAXSIZE = 10;
protected VerNode[] adjList; //存儲頂點結(jié)點的數(shù)組
int n; //表示頂點數(shù)
int e; //表示弧數(shù)
public AdjListGraph() {
adjList = new VerNode[MAXSIZE];
}
//建立無向圖的鄰接表
public void createAdjGraph() {
String str; //用于接受字符串而已
Scanner sc = new Scanner(System.in);
System.out.println("請輸入圖的頂點數(shù)：");
n = sc.nextInt();
System.out.println("請輸入圖的邊數(shù)：");
e = sc.nextInt();
System.out.println("請輸入圖的頂點信息");
str = sc.next();
//初始化頂點信息
for (int i = 0; i < str.length(); i++) {
adjList[i] = new VerNode<T>();
adjList[i].data = str.charAt(i); //將頂點信息存入新建的頂點中
adjList[i].firstArc = null;
}
System.out.println("請輸入圖的邊的信息:");
ArcNode s; //重復利用的邊表結(jié)點
for(int j = 0; j < e; j++) {
System.out.println("請輸入第" + (j + 1) + "條邊的兩個端點：");
str = sc.next();
//得到邊的連個端點
T v1 = (T)(Object)str.charAt(0);
T v2 = (T)(Object)str.charAt(1);
//確定這連個頂點在圖中的位置
int loc1 = locateVex(v1);
int loc2 = locateVex(v2);
//在相應位置插入邊表結(jié)點
if (loc1 >= 0 && loc2 >= 0) {
//下面這段代碼可以創(chuàng)建有向圖的出邊鄰接表
s = new ArcNode();
s.adjVer = loc2;
s.next = adjList[loc1].firstArc;
adjList[loc1].firstArc = s;
/**
* 由于是無向圖，因此是對稱的.
* 如果是創(chuàng)建有向圖的出邊鄰接表休傍，則只需注釋掉下面的這段
* 代碼即可征绎。
*/
s = new ArcNode();
s.adjVer = loc1;
s.next = adjList[loc2].firstArc;
adjList[loc2].firstArc = s;
}
}
}
/**
* 在圖G中查找頂點v在頂點數(shù)組的位置。若不存在則返回-1
* @param v
* @return
*/
public int locateVex(T v) {
for (int i =0 ; i < n; i++) {
if(adjList[i].data == v) {
return i;
}
}
return -1;
}
//打印鄰接表
public void disPlayAdjList() {
ArcNode p;
System.out.print("圖的鄰接表的表示：");
for(int i = 0; i < n; i++) {
System.out.print("\n " + adjList[i].data);
p = adjList[i].firstArc;
while(p != null) {
System.out.print("-->" + p.adjVer);
p = p.next;
}
}
}
}
4.圖的遍歷(Traversing Graph)
含義：從圖中某一頂點出發(fā)訪問遍歷圖中其余頂點磨取，且使每一個頂點僅被訪問一次人柿，這
一過程就是圖的遍歷
兩種遍歷方式：
(1)深度優(yōu)先(Deep First Search, DFS)
(2)廣度優(yōu)先(Breadth First Search, BFS)
1.深度優(yōu)先遍歷(DFS)
類似于樹的先序遍歷柴墩，是樹的先序遍歷的推廣。
思想過程：
1)首先訪問出發(fā)點V
2)然后依次從V出發(fā)搜索V的每個'鄰接點'W, 若W未曾訪問過凫岖，則以W為新的出發(fā)
點為深度優(yōu)先搜索遍歷江咳，直至圖中所有和源點V有路徑相同的頂點均已被訪問為止
3)若此圖中仍有未訪問的頂點，則選另一個尚未被訪問的頂點作為新的源點重復
上述過程哥放，直至圖中所有頂點均已被訪問為止歼指。
上述遍歷過程就是遞歸的過程。
下面分別用鄰接矩陣和鄰接表來實現(xiàn)圖的深度優(yōu)先遍歷
注意：對于點多邊少的圖而言甥雕，鄰接表結(jié)構(gòu)效率更高 O(n+e), n為頂點個數(shù)东臀，e為邊數(shù)
(1)用鄰接矩陣來實現(xiàn)：算法時間復雜度O(n^2)
'代碼描述'
//深度優(yōu)先遍歷圖
public void DFSTraverse() {
//其實這段是可以不用的，因為boolean的默認值就是false
for(int i = 0; i < vertexNum; i++) {
visited[i] = false; //默認所有的頂點均為被訪問到
}
System.out.println("圖的深度優(yōu)先遍歷序列：");
for(int j = 0; j < vertexNum; j++) {
//判斷該點是否被訪問到過
if(!visited[j]) {
//表示該點沒有被訪問到過
DFS(j); //則從i好點開始進行深度優(yōu)先遍歷
}
}
}
/**
* 利用鄰接矩陣完成連通圖的遍歷
* @param i
*/
private void DFS(int n) {
System.out.print(vertexArr[n] + " "); //訪問到第i個點犀农，并打印出來
visited[n] = true;
for(int i = 0; i < vertexNum; i++) {
if(!visited[i] && (adjMar[n][i] == 1)) {
DFS(i);
}
}
}
(2)利用鄰接表實現(xiàn)深度優(yōu)先遍歷：算法時間復雜度 O(n+e)
//深度優(yōu)先遍歷
public void DFSTraverse() {
//其實這段是可以不用的惰赋，因為boolean的默認值就是false
for(int i = 0; i < n; i++) {
visited[i] = false; //默認所有的頂點均為被訪問到
}
System.out.println("圖的深度優(yōu)先遍歷序列：");
for(int j = 0; j < n; j++) {
//判斷該點是否被訪問到過
if(!visited[j]) {
//表示該點沒有被訪問到過
DFS(j); //則從i好點開始進行深度優(yōu)先遍歷
}
}
}
/**
* 采用鄰接表完成圖的深度優(yōu)先遍歷
* @param n
*/
private void DFS(int n) {
System.out.print(adjList[n].data + " "); //訪問到第i個點，并打印出來
visited[n] = true;
ArcNode p;
p = adjList[n].firstArc;
while(p != null) {
if(!visited[p.adjVer]) {
DFS(p.adjVer);
}
p = p.next;
}
}
2.廣度優(yōu)先遍歷(BFS)
類似于樹的層序遍歷呵哨，是樹的層序遍歷的推廣赁濒。
過程：
1)首先訪問出發(fā)點V
2)接著訪問頂點V的所有鄰接點V1,V2,...Vt
3)然后依次訪問V1，V2,...Vt的所有鄰接點
4)依次執(zhí)行孟害，直至圖中所有的頂點都被訪問到
由該遍歷過程可知拒炎，該過程用迭代即可完成
(1)利用鄰接矩陣實現(xiàn)的圖的廣度優(yōu)先搜索：O(n^2)
'代碼描述'
/**
* 廣度優(yōu)先搜索
*/
public void BFSTraverse() {
System.out.println("圖的廣度優(yōu)先遍歷");
for(int i = 0; i < vertexNum; i++) {
visited[i] = false;
}
for(int j = 0; j < vertexNum; j++) {
if(!visited[j]) {
BFS(j);
}
}
}
/**
* 鄰接矩陣實現(xiàn)的廣度優(yōu)先遍歷：類似于樹的層序遍歷
* 該部分只能實現(xiàn)圖的一個連通子圖
* @param n
*/
private void BFS(int n) {
System.out.print(verArr[n] + " ");
Queue<Integer> queue = new LinkedList<Integer>();
visited[n] = true;
queue.offer(n); //當前頂點進隊
while(!queue.isEmpty()) {
int i = queue.poll();
for(int j = 0; j < vertexNum; j++) {
if(!visited[j] && (adjMar[i][j] == 1)) {
System.out.print(verArr[j] + " ");
visited[j] = true;
queue.offer(j);
}
}
}
}
(2)利用鄰接表實現(xiàn)的圖的廣度優(yōu)先搜索：O(n+e)
'代碼描述'
/**
* 用鄰接表實現(xiàn)的圖的廣度優(yōu)先搜索
*/
public void BFSTraverse() {
System.out.println("廣度優(yōu)先遍歷：");
for(int i = 0; i < n; i++) {
visited[i] = false;
}
for(int j = 0; j < n; j++) {
if(!visited[j]) {
BFS(j);
}
}
}
/**
* 輔助方法
* 該部分只能實現(xiàn)圖的一個連通子圖
* @param n
*/
private void BFS(int n) {
System.out.print(adjList[n].data + " ");
Queue<Integer> queue = new LinkedList<Integer>();
visited[n] = true;
queue.offer(n); //當前頂點進隊
int i;
ArcNode p;
while(!queue.isEmpty()) {
i = queue.poll();
p = adjList[i].firstArc;
while(p != null) {
if(!visited[p.adjVer]) {
System.out.print(adjList[p.adjVer].data + " ");
queue.offer(p.adjVer);
visited[p.adjVer] = true;
}
p = p.next;
}
}
}
5.最小生成樹
含義：生成樹中構(gòu)造連通網(wǎng)的代價最小(即權(quán)值最小的)的生成樹稱為最小生成樹
注意：一個連通網(wǎng)的生成樹是不唯一的
而對于非連通的網(wǎng)，其各個連通分量的生成樹組成的集合為其生成森林挨务。
如何尋找連通網(wǎng)的最小生成樹：
(1)普里姆算法(Prim)
(2)克魯斯卡算法(Kruskal)
1.普里姆算法：
基本思想：設G=(V,E)是具有n個頂點的網(wǎng)击你，T=(U, TE)為G的最小生成樹，U是T的頂點集合谎柄，
TE是T的邊集丁侄。
則其構(gòu)建過程：
首先從集合V中任選取一點(如V0)放入集合U中，這是U={V0}, TE{Ф},然后選擇這樣的
一條邊：一個頂點在集合U中朝巫，另一個頂點在集合V-U中,且權(quán)值最小的邊(u,v)（u∈U, v∈V-U）
將該邊放入TE中鸿摇，并將頂點v加入到U中。重復上述過程劈猿，知道U=V位置拙吉，此時TE中有n-1條邊，那
么T=(U,TE)就是G的一顆最小生成樹揪荣。
算法分析：普里姆算法對頂點數(shù)量敏感筷黔，因此，它適合稠密圖
時間復雜度：O(n^2)
"代碼描述"
/**
* 建立網(wǎng)的最小生成樹
* @param adjMar 表示網(wǎng)圖的鄰接矩陣
* @param n 表示從第n個頂點開始搜索最小生成樹
*/
public void miniSpanTree_Prim(int[][] adjMar, int n) {
//對輸入的參數(shù)進行校驗
if(n > vertexNum || n < 1) {
System.out.println("輸入的起始頂點位置有誤仗颈！");
return;
}
//保存相關(guān)頂點下標,
int adjvex[] = new int[vertexNum];
/**
* 用于存放已進入最小生成樹中的頂點到其余未進入生成樹中的頂點之間
* 權(quán)值最小的邊
*/
int lowcost[] = new int[vertexNum];
/**
* lowcost[i]對應的值為0就表示將該頂點Vi加入生成樹
*/
lowcost[n-1] = 0; //表示將第一個頂點V0加入生成樹中
adjvex[n-1] = n-1; //初始化第一個頂點下標為0
for(int i = 0; i < vertexNum; i++) {
//將于V0有關(guān)的邊的權(quán)值存儲起來佛舱，沒有直接相連的也要存儲
if(i == n-1) {
continue;
}
lowcost[i] = adjMar[n-1][i];
adjvex[i] = n-1;
}
//構(gòu)造最小生成樹
int min;
int j;
int k;
for(int i = 0; i < vertexNum; i++) {
j = 0;
k = 0;//用于記錄當前權(quán)值最小的頂點下標
if(i == n-1 || j == n-1) {
//由于n-1時，在一開始已經(jīng)進行過初始化了，因此這里就不能再進行篩選了
continue;
}
min = MAX; //初始化min的值為無窮大
while(j < vertexNum) {
if(lowcost[j] != 0 && lowcost[j] < min) {
min = lowcost[j];
k = j; //將權(quán)值最小的頂點的下標存入K中
}
j++;
}
System.out.println(vertexArr[adjvex[k]] + "" + vertexArr[k]);
lowcost[k] = 0; //將當前頂點的加入生成樹種
// 重新更新lowcost[]數(shù)組 ,使其始終保持著最小權(quán)值
for(j = 0; j < vertexNum; j++) {
if((j != n-1) && lowcost[j] != 0 && adjMar[k][j] < lowcost[j]) {
lowcost[j] = adjMar[k][j];
adjvex[j] = k; //將下標為k的頂點存入adjvex[]中名眉，
}
}
}
}
2.克魯斯卡爾算法：
基本思想：是按權(quán)值遞增的次序來構(gòu)造的粟矿，使生成樹中每一條邊的權(quán)值盡可能地小。
構(gòu)建過程：
先構(gòu)造一個只含n個頂點的子圖G'损拢，然后從網(wǎng)中權(quán)值最小的邊開始陌粹，若它的添加不
使G'中產(chǎn)生回路，則在G'上加上這條邊福压，如此反復掏秩，直到G'中加上 n-1 條邊為止。
算法分析：克魯斯卡爾算法是針對邊展開的荆姆，因此蒙幻，它適合稀疏圖
時間復雜度：O(eloge)
"代碼描述"
對網(wǎng)的邊封裝成一個類
public class Edge {
int begin; //表示該邊的起始端點
int end; //表示該邊的結(jié)束端點
int weight; //表示該邊上的權(quán)值
}
/**
* 克魯斯卡爾求最小生成樹的算法
*/
public void miniSpanTree_Kruskal(int[][] adjMar) {
Edge[] edges; //定義邊集數(shù)組
//定義一個數(shù)組用來判斷邊與邊是否形成環(huán)路
int[] parent = new int[vertexNum];
egdes = adjMarToEdge(adjMar); //這里只是一個虛擬方法，并沒有真正去實現(xiàn)它胆筒。實際上實現(xiàn)也很容易
//對parent[]數(shù)組進行初始化,所有的頂點均沒有進入最小生成樹中
for(int i = 0; i < vertexNum; i++) {
parent[i] = 0;
}
int n;
int m;
//對每一條邊結(jié)合edges[], parent[]進行掃面檢查邮破，
for(int j = 0; j < edgesNum; j++) {
n = find(parent, edges[j].begin);
m = find(parent, edges[j].end);
if(n != m) {
//n != m , 表明邊(n, m)還沒有進入最小生成樹中。
parent[n] = m; //將此邊的結(jié)尾頂點放入下標為起點的parent中仆救，表示此邊(n,m)已經(jīng)進入最小生成樹
//打印出已加入最小生成樹中的邊
System.out.println(vertexArr[edges[j].begin] + "" + vertexArr[edges[j].end]);
}
}
}
//查找連線頂點的尾部下標
private int find(int[] parent, int f) {
//如果parent[f] = 0抒和，則表明該頂點還沒有進入最小生成樹中
//此部分時間復雜度：O(loge), e表示邊數(shù)
while(parent[f] > 0) {
/**
* 表明該頂點(準確來說是 邊(f,parent[f]) 的結(jié)束點parent[f])已經(jīng)進入最
* 小生成樹中，因此彤蔽，要繼續(xù)追蹤下去摧莽，看看以此結(jié)束點parent[f]為起始點的
* 下一條邊的結(jié)束點是什么樣的？有可能和已進入最小生成樹的頂點構(gòu)成環(huán)
*/
f = parent[f];
}
return f;
}
6.最短路徑
對于網(wǎng)圖(有權(quán)值)和非網(wǎng)圖(權(quán)值可以看成都是1)來說顿痪，他們的最短路徑含義是不同的镊辕。
非網(wǎng)圖：是指兩頂點之間經(jīng)過的邊數(shù)最少的路徑
網(wǎng)圖：是指兩頂點之間經(jīng)過的權(quán)值之和最小的路徑
我們主要研究網(wǎng)圖的最短路徑，且第一個頂點是源點蚁袭，最后一個頂點是終點征懈。
求最短路徑的算法：
迪杰斯特拉算法(Dijkstra)
弗洛伊德算法(Floyd)
1.迪杰斯特拉算法
是求某一點到其余各點的最短路徑問題的，其核心思想是窮舉法撕阎，因此計算效率不高
整個過程是基于已經(jīng)求出的最短路徑的基礎受裹，在來求得更遠頂點的最短路徑碌补。最終虏束，可以
得到我們想要到的那個點的最短路徑。
算法分析：時間復雜度O(n^2)
"代碼描述"
/**
* 計算從頂點n到其余各點的最短距離
* 注意：此算法目前只能計算無向圖厦章，對于有向圖需要修改代碼
* @param adjMar 網(wǎng)圖的鄰接矩陣
* @param n 起始頂點
*/
public void dijisktraShortPath(int[][] adjMar, int n) {
//對輸入的參數(shù)進行校驗
if(n < 1 || n > vertexNum) {
System.out.println("輸入的起始頂點不合理");
return;
}
int s = n - 1;
//用于記錄是否已經(jīng)計算出s到vi點的最短路徑镇匀，
int[] isFinal = new int[vertexNum]; //isFinal[w]=1時,表示已確定到點w的最短路徑
int[] distance = new int[vertexNum]; //表示s到vi的最短路徑長度
int[] path = new int[vertexNum]; //表示在最短路徑上到當前點的前驅(qū)頂點下標， -1表示到此點沒有路徑
for(int i = 0; i < vertexNum; i++) {
isFinal[i] = 0; //全部置為0袜啃，表示還沒有找到到任何點的最短路徑
distance[i] = adjMar[s][i]; //初始化s到其余各點最短路徑長度
/**
* 默認沒有路徑汗侵，初始化為s，是為了后面好處理
* 這里最好的初始化為-1來表示沒有路徑，但對于無向圖來說無所謂晰韵，因為網(wǎng)中只要沒有
* 孤立頂點发乔，那么兩個頂點之間一定是連通的額，但是對于有向圖而言雪猪，情況就不一樣了
* 這里就應該初始化為-1
*/
path[i] = s;
}
distance[s] = 0; //s到s的路徑長度為0
isFinal[s] = 1; //s到s的最短路徑是不需要確定的栏尚，也就相當于已經(jīng)確定了
path[s] = s; //表示s到s的前驅(qū)點下標為自身
int min; //記錄s到vi的最短距離
int k = 0; //輔助變量，用于記錄每次確定到s最短距離的那個頂點的下標
//計算s到所有頂點的最短路徑
for(int j = 0; j < vertexNum; j++) {
if(j == s) {
continue;
}
min = MAX;
//尋找離s最近的頂點
for(int w = 0; w < vertexNum; w++) {
if(isFinal[w] == 0 && distance[w] < min) {
k = w;
min = distance[w];
}
}
isFinal[k] = 1; //表明s到k頂點的最短路徑已確定
// 更新當前最短路徑及距離
for(int t = 0; t < vertexNum; t++) {
if(isFinal[t] == 0 && (min + adjMar[k][t] < distance[t])) {
//表明找到了更短的距離
distance[t] = min + adjMar[k][t];
path[t] = k;
}
}
}
//打印s到各點的最短路徑
displayPath(s, path);
}
/**
* 根據(jù)前驅(qū)節(jié)點數(shù)組打印最短路徑
* @param s
* @param path
*/
private void displayPath(int s, int[] path) {
for(int i = 0; i < path.length; i++) {
System.out.print(path[i] + " ");
}
System.out.println();
int temp;
for(int i = 0; i < path.length; i++) {
System.out.print(vertexArr[s] + "->" + vertexArr[i] + ": " + i);
temp = i;
while(path[temp] != s) {
System.out.print(" " + path[temp]);
temp = path[temp];
if(temp == -1) {
break;
}
}
System.out.println(" " + s);
}
}
2.弗洛伊德算法
是求所有頂點到所有頂點的最短路徑只恨。
算法分析：O(n^3)
"代碼描述"
/**
* 計算從頂點n到其余各點的最短距離
* 注意：此算法目前只能計算無向圖译仗，對于有向圖需要修改代碼
* @param graph 網(wǎng)圖的鄰接矩陣
* @param n 起始頂點
*/
public void floydShortPath() {
//定義初始化最短路徑矩陣,初始狀態(tài)為網(wǎng)圖的鄰接矩陣，可以用來計算最小路徑長度
int[][] shortPath = new int[MAXSIZE][MAXSIZE];
//定義前驅(qū)結(jié)點矩陣,可以用來求出最短路徑
int[][] path = new int[MAXSIZE][MAXSIZE];
//初始化前驅(qū)節(jié)點矩陣和最短路徑權(quán)值矩陣
for(int i = 0; i < vertexNum; i++) {
for(int j = 0; j < vertexNum; j++) {
shortPath[i][j] = adjMar[i][j];
path[i][j] = j;
}
}
/**
* 是決定該算法時間復雜度的主要地方：
* 三層循環(huán)官觅，很容易得知時間復雜度為：O(n^3)
* 計算所有點其他各點的最短路徑
* w表示中轉(zhuǎn)頂點的下標纵菌，m是起點，n是結(jié)束頂點
* 挨著以w控制的頂點作為中轉(zhuǎn)點休涤，來求所有點到其余所有點的最短路徑距離
*/
for(int w = 0; w < vertexNum; w++) {
for(int m = 0; m < vertexNum; m++) {
/**
* 注意：這個n當然也可以是從0開始咱圆，但是下面的
* shortPath[n][m] = shortPath[m][n];
* 顯得多余了, 但是對于有向圖就不能這么寫了。要注意改寫
* 改寫成下面這種形式功氨，可以減少循環(huán)的次數(shù)闷堡，從而提高程序部分性能
*/
for(int n = m; n < vertexNum; n++) {
if(shortPath[m][n] > (shortPath[m][w] + shortPath[w][n])) {
//如果經(jīng)過下標為w的頂點比原來兩點間的路徑更短，就要修正這兩點間的距離
shortPath[m][n] = shortPath[m][w] + shortPath[w][n];
shortPath[n][m] = shortPath[m][n]; //因為該矩陣是對稱的疑故，所以可以這么寫
/**
* 修改路徑經(jīng)過下標為w的頂點杠览，表示到相應的點時，要經(jīng)過該點,
* 準確說纵势，這個點是到達該點的前驅(qū)結(jié)點踱阿。
*/
path[m][n] = path[m][w];
path[n][m] = path[m][n]; //因為該矩陣是對稱的，所以可以這么寫
}
}
}
}
//顯示最短路徑
displayPath(path, shortPath);
}
/**
* 打印所有點到其余所有點的最短路徑
* @param path 最短路徑的前驅(qū)結(jié)點下標矩陣（在該矩陣上縱向打印路徑）
* @param shortPath 最短路徑矩陣
*/
private void displayPath(int[][] path, int[][] shortPath) {
int k;
for(int i = 0; i < vertexNum; i++) {
for(int j = i; j < vertexNum; j++) {
System.out.print(i + " " + j + " (" + shortPath[i][j] + ") ");
k = path[i][j]; //獲得第一個路徑頂點下標
System.out.print("path: " + i);
while(k != j) {
System.out.print("->" + k);
k = path[k][j]; //獲得下一個路徑頂點的下標
}
System.out.println("->" + j);
}
System.out.println();
}
}
思考：分析迪杰斯特啦和弗洛伊德求最短路徑的算法钦铁，二者均可求出所有點到其余所有點
之間的最短路徑软舌。只不過對于迪杰斯特拉算法而言，需要循環(huán)調(diào)用迪杰斯特拉算法牛曹，時間
復雜度為O(n^3), 而弗洛伊德算法只需一次調(diào)用即可全部計算出來佛点，盡管其時間復雜度也
為O(n^3)，弗洛伊德算法更加簡潔黎比。
7.拓撲排序(Topological Sort)
這里的排序并不是平時理解的安大小排序的超营，而是安工作步驟先后順序排序的，主要解決一個工程能否
順利進行阅虫。
用于工程施工演闭、生產(chǎn)流程、教學安排等應用中來合理安排工作流程步驟
這些流程圖都是無環(huán)的有向圖(圖中的活動都是有先后順序的)
(1)AOV網(wǎng)(Activity On Vertex Network): 在一個表示工程的有向圖中颓帝，用頂點表示活動米碰，用弧表示
活動之間的優(yōu)先關(guān)系窝革，這樣的有向圖稱為AOV網(wǎng)
注意：AOV網(wǎng)中沒有回路
(2)拓撲序列：設G=(V,E)是一個具有n個頂點的有向圖，V中的頂點序列V1,V2,...Vn吕座，滿足若從Vi到Vj有
一條路徑虐译，則在頂點序列中頂點Vi必在頂點Vj之前，則我們成這樣的頂點序列為拓撲序列吴趴。
(3)拓撲排序：就是對一個有向圖構(gòu)造拓撲序列的過程
(4)拓撲排序算法：
基本思想：從AOV網(wǎng)中選擇一個入讀為0的頂點輸出菱蔬，然后刪除此頂點，并刪除以此頂點為尾的弧史侣，
繼續(xù)重復此步驟拴泌，知道輸出全部頂點或者AOV網(wǎng)中不存在入讀為0的頂點為止。
因為在排序的過程中要頻繁刪除頂點惊橱，因此選擇使用鄰接表來做存儲結(jié)構(gòu)（而不用鄰接矩陣做存儲結(jié)構(gòu)）
由于要查找入度為0的頂點蚪腐，需要在鄰接表的頂點結(jié)構(gòu)中增加入度域in，
鄰接表頂點結(jié)構(gòu)：
┌─────┬──────┬───────────┐
│ in │ data │ firstedge │
└─────┴──────┴───────────┘
算法分析：O(n+e)
"代碼描述"
1.鄰接表頂點結(jié)構(gòu)
public class VerNode<T> {
public T data; //存儲頂點的名稱或相關(guān)信息
public ArcNode firstArc; //指向頂點Vi的第一個鄰接點的邊結(jié)點
public int in;//增加一個入度域税朴，方便拓撲排序時
public VerNode() {
this.data = null;
this.firstArc = null;
}
}
2.拓撲排序
/**
* 進行拓撲排序
* 要用到棧這個數(shù)據(jù)結(jié)構(gòu)回季，我們就選用前面棧一章寫的棧數(shù)據(jù)結(jié)構(gòu)
*/
public void topologicalSort() {
//定義一個棧(用的之前在棧一章的數(shù)據(jù)結(jié)構(gòu))，用于存儲入度為0的頂點
LinkStack<VerNode<String>> stack = new LinkStack<VerNode<String>>();
//將入度為0的頂點存入棧中：O(n)
for(int i = 0; i < n; i++) {
if(adjList[i].in == 0) {
stack.push(adjList[i]);
}
}
int count = 0; //用于記錄輸出頂點的個數(shù)
ArcNode arcEdge; //用于循環(huán)使用, 鄰接表結(jié)構(gòu)中的邊表結(jié)點結(jié)構(gòu)
VerNode<String> p; //用于循環(huán)使用, 鄰接表結(jié)構(gòu)中的頂點結(jié)構(gòu)
int k; //用于循環(huán)接受邊表中結(jié)點在頂點表中的位置
//當棧不為空正林，循環(huán)始終進行
while(!stack.isEmpty()) {
//打印此入度為0的頂點
p = stack.pop();
if(count == (n - 1)) {
System.out.print(p.data);
}else{
System.out.print(p.data + "->");
}
//統(tǒng)計輸出的頂點數(shù)
count ++;
arcEdge = p.firstArc;
//處理與p鄰接的結(jié)點：O(e)
while(arcEdge != null) {
k = arcEdge.adjVer;
/**
* --adjList[k].in 泡一，這個動作就表明將到與上面p結(jié)點相連的
* 結(jié)點的之間的邊刪除了
*/
if((--adjList[k].in) == 0) {
stack.push(adjList[k]); //將入度為0的頂點入棧
}
arcEdge = arcEdge.next;
}
}
//可用于檢查網(wǎng)中有沒有環(huán)
if (count < n) {
//System.out.println("網(wǎng)中存有環(huán)");
}else {
//System.out.println("正常");
}
}
8.關(guān)鍵路徑
拓撲排序主要是為解決一個工程能否順序進行的問題，而關(guān)鍵路徑主要是解決工程完成需要的最短時間的問題
(1)AOE網(wǎng)(Activity On Edge NetWork)
在一個表示工程的的帶權(quán)有向圖中觅廓，用頂點表示事件鼻忠，用有向邊表示活動，用邊上的權(quán)值表示活動的
持續(xù)時間杈绸，這種有向圖的邊表示活動網(wǎng)帖蔓，我們稱之為AOE網(wǎng)
源點：沒有入邊，只有出邊
匯點：沒有出邊瞳脓，只有入邊
注意：AOV網(wǎng)的頂點表示活動塑娇， 邊表示活動之間的優(yōu)先關(guān)系
AOE網(wǎng)的邊表示活動，邊也表示優(yōu)先關(guān)系劫侧，邊上的權(quán)值表示活動持續(xù)的時間
AOE網(wǎng)是建立在活動之間制約關(guān)系(先后關(guān)系)沒有矛盾的基礎上埋酬，再來分析完成整個工程至少需要多少時間
(2)關(guān)鍵路徑
把路徑上各個活動所持續(xù)的時間之和稱為路徑長度，從源點到匯點的最大長度的路徑叫關(guān)鍵路徑烧栋，
在關(guān)鍵路徑上的活動叫關(guān)鍵活動写妥。
那么，如果我們想縮短整個工程活動的完成時間劲弦，就只需在關(guān)鍵路徑上算短相應的活動時間就能
做到整體工期縮短
(3)關(guān)鍵路徑的算法實現(xiàn)
基本思想：在整個AOE網(wǎng)上尋找所有活動的最早開始時間和最晚開始時間耳标，并比較它們，如果而二者
相等邑跪，則表明該活動是關(guān)鍵活動（當然也就是關(guān)鍵路徑上的一段了）次坡，如果不想等那就不是關(guān)鍵活動
需要知道的幾個參數(shù)：
1)事件的最早發(fā)生時間etv(earliest tiem of vertex)：即頂點vk的最早發(fā)生時間
注意：etv[i]的求解必須在所有前驅(qū)的最早發(fā)生時間求得之后才能確定，因此是在拓撲有序的基礎上進行的
2)事件的最晚發(fā)生時間ltv：即在不推遲整個工程的前提下画畅，頂點vk的最晚發(fā)生時間
注意：ltv[i]必須在其所有后繼的最晚發(fā)生時間求得之后才能確定砸琅，因此是在逆拓撲有序的基礎上進行的
3)活動<Vi,Vj>所需的時間：t(i,j),即AOE網(wǎng)上的邊的權(quán)值
4)活動<Vi,Vj>最早開工時間ete(earliest time of edge)：即弧ak的最早發(fā)生時間
ete(i,j) = etv[i];
5)活動<Vi,Vj>最晚開工時間lte：即在不推遲整個工程的前提下，弧ak的最晚發(fā)生時間
lte(i,j) = ltv[i] - t(i,j)
由 etv 和 ltv 求得ete, lte
當 ete[k] == lte[k] 時轴踱，該活動為關(guān)鍵活動
算法描述：
時間復雜度：O(n+e)
"代碼描述"
1.頂點表結(jié)點結(jié)構(gòu)
//表示頂點表結(jié)點的結(jié)構(gòu)
public class VerNode<T> {
public T data; //存儲頂點的名稱或相關(guān)信息
public ArcNode firstArc; //指向頂點Vi的第一個鄰接點的邊結(jié)點
public int in;//增加一個入度域症脂，方便拓撲排序時
public VerNode() {
this.data = null;
this.firstArc = null;
}
}
2.邊表結(jié)點的結(jié)構(gòu)
public class ArcNode {
public int adjVer; //鄰接點域，用于存儲該該點結(jié)點域數(shù)組中的下標
public int weight; //用于網(wǎng)圖存儲權(quán)值
public ArcNode next; //指向下一個鄰接點
public ArcNode() {
adjVer = 0;
weight = 0;
next = null;
}
}
3.關(guān)鍵路徑的算法實現(xiàn)
/**
* 尋找關(guān)鍵路徑：是建立在拓撲序列的基礎上進行相關(guān)關(guān)鍵路徑的尋找
*/
public void getCriticalPath() {
Object[] obj = topologicalSort(); //拓撲排序：O(n+e)
//通過拓撲排序返回各個事件最早完成時間
int[] eventEarly = (int[])obj[0];
//返回拓撲序列
LinkStack<Integer> topPath = (LinkStack<Integer>)obj[1];
int[] eventLast = new int[n];//定義事件發(fā)生最晚的數(shù)組淫僻，好好理解這個
int actEarly; //活動最早發(fā)生時間變量
int actLast; //活動最晚發(fā)生時間變量
//初始化最晚事件數(shù)組:O(n)
for(int i = 0; i < n; i++) {
/**
* 因為事件的最晚發(fā)生時間必須在其所有后繼的最遲發(fā)生的時間確定后才能確定的
* 而最后一個事件(匯點)的最晚發(fā)生時間就要保正整個工程部耽誤诱篷，因此，它的最晚
* 發(fā)生時間就是整個工程的最早發(fā)生時間雳灵。
* 因此棕所，才會這樣初始化
*/
eventLast[i] = eventEarly[n-1];
}
int temp; //循環(huán)中，用來臨時存儲topPath出棧的頂點下標號
int k; //用于循環(huán)接受邊表中結(jié)點在頂點表中的位置
ArcNode p;//用于循環(huán)使用, 鄰接表結(jié)構(gòu)中的邊表結(jié)點結(jié)構(gòu)
//計算各個頂點的最晚發(fā)生時間,整個過程是在逆拓撲序列的基礎上進行的:O(n+e)
while(!topPath.isEmpty()) {
//將拓撲序列順序出棧
temp = topPath.pop();
p = adjList[temp].firstArc;
while(p != null) {
k = p.adjVer;
if((eventLast[k] - p.weight) < eventLast[temp]) {
eventLast[temp] = eventLast[k] - p.weight;
}
p = p.next;
}
}
//求關(guān)鍵活動悯辙，當活動的最早時間和最晚時間是一樣的時候琳省，就表明該
//活動間的路徑為關(guān)鍵活動：O(n+e)
for(int j = 0; j < n; j++) {
p = adjList[j].firstArc;
while(p != null) {
k = p.adjVer;
actEarly = eventEarly[j]; //活動最早發(fā)生時間
actLast = eventLast[k] - p.weight; //活動的最晚發(fā)生時間
if(actEarly == actLast) {
//兩者相等則表明該活動在關(guān)鍵路徑上
System.out.print("<" +adjList[j].data + "," + adjList[k].data +">(" +p.weight+") ");
}
p = p.next;
}
}
}
/**
* 進行拓撲排序:O(n+e)
* 要用到棧這個數(shù)據(jù)結(jié)構(gòu)，我們就選用前面棧一章寫的棧數(shù)據(jù)結(jié)構(gòu)
*/
private Object[] topologicalSort() {
/**
* 定義一個棧躲撰，用于存儲入度為0的頂點
* 存儲拓撲序列的頂點下標號(即該頂點在鄰接表的頂點數(shù)組中的存儲位置针贬，從0開始的)
* 為啥不直接存儲該頂點呢？
* 一開始也是采用存儲的頂點拢蛋，但是該頂點結(jié)構(gòu)在存儲的時候并沒有存儲其位置
* 信息桦他，導致下面在計算各頂點的最早事件發(fā)生時間時，無法獲取存儲相應的最早事件發(fā)生的
* 數(shù)組中的元素內(nèi)容谆棱。相反直接存儲入度為0的頂點的下標號瞬铸，那么想找該頂點時可以直接在adjList[]數(shù)組中獲取。
*/
LinkStack<Integer> stack = new LinkStack<Integer>();
//定義事件發(fā)生最早的數(shù)組（最早發(fā)生即到該點的最長路徑）
int[] eventEarly = new int[n];
//將入度為0的頂點存入棧中,同時初始化earlyTiem
for(int i = 0; i < n; i++) {
eventEarly[i] = 0; //全部初始化為0
if(adjList[i].in == 0) {
stack.push(i);
}
}
/**
* 拓撲序列不用直接在控制臺打印出來础锐，而是用topPath存儲這些序列頂點
* 同上面的stack一樣嗓节，也是直接存儲相應的頂點下標號
*/
LinkStack<Integer> topPath = new LinkStack<Integer>();
int count = 0; //用于記錄輸出頂點的個數(shù)
ArcNode arcEdge; //用于循環(huán)使用, 鄰接表結(jié)構(gòu)中的邊表結(jié)點結(jié)構(gòu)
VerNode<String> p; //用于循環(huán)使用, 鄰接表結(jié)構(gòu)中的頂點結(jié)構(gòu)
int k; //用于循環(huán)接受邊表中結(jié)點在頂點表中的位置
int temp; //用于臨時存儲從stack中取出的頂點下標號
//當棧不為空，循環(huán)繼續(xù)進行
while(!stack.isEmpty()) {
//打印此入度為0的頂點
temp = stack.pop();
p = adjList[temp]; //由下標號結(jié)合adjList[]可直接獲取對應的頂點
topPath.push(temp); //將拓撲頂點標號順序存入,不用在控制臺打印出來
//統(tǒng)計輸出的頂點數(shù)
count ++;
arcEdge = p.firstArc; //獲取與p鄰接的頂點
//處理與p鄰接的結(jié)點
while(arcEdge != null) {
k = arcEdge.adjVer; //該頂點在頂點數(shù)組中的存儲位置
/**
* --adjList[k].in 皆警，這個動作就表明將到與上面p頂點相連的
* 頂點之間的邊刪除了拦宣，同時該點的入度也就跟著減1
*/
if((--adjList[k].in) == 0) {
//stack.push(adjList[k]); //將入度為0的頂點入棧
stack.push(k); //將入度為0的頂點入棧
}
//計算該頂點(事件)的最早發(fā)生時間
if((eventEarly[temp] + arcEdge.weight) > eventEarly[k]) {
eventEarly[k] = eventEarly[temp] + arcEdge.weight;
}
arcEdge = arcEdge.next;
}
}
//可用于檢查網(wǎng)中有沒有環(huán)
if (count < n) {
//System.out.println("網(wǎng)中存有環(huán)");
}else {
//System.out.println("正常");
}
//返回兩個重要的結(jié)果
return new Object[]{eventEarly, topPath};
}