目錄導(dǎo)讀：
- 1.基本概念
- 2.圖的存儲概念(5中方式)
鄰接矩陣
鄰接表
- 3.圖的遍歷
深度優(yōu)先遍歷
廣度優(yōu)先遍歷
- 4.最小生成樹
普里姆算法(Prim)
克魯斯卡爾算法(kruskal)
- 5.最短路徑
迪杰斯特拉算法(Dijkstra)
佛羅伊德算法(Floyd)
- 6.拓?fù)渑判?- 6.關(guān)鍵路徑
1.圖(Graph)
由頂點(diǎn)的有窮非空集合和頂點(diǎn)之間邊的集合組成，通常表示為：G(V,E)
其中，G 表示一個(gè)圖，V 是圖G中頂點(diǎn)的集合，E是圖G中邊的集合
注意：
- 圖的頂點(diǎn)集 V 不可以為空，至少要為1,但是邊集 E 可以為空。
- 線性表中數(shù)據(jù)元素叫元素，樹中數(shù)據(jù)元素叫結(jié)點(diǎn)，圖中數(shù)據(jù)元素叫頂點(diǎn)
2.若干個(gè)定義
無向邊(Edge):(vi, vj) ——> 無向圖：圖中所有邊均為無向邊
有向邊(Arc，也稱為弧): <vi, vj> ——> 有向圖：圖中所有邊均有有向邊
簡單圖：不存在頂點(diǎn)到其自身的邊，且同一條邊也不重復(fù)。
完全圖：如果任意兩個(gè)頂點(diǎn)之間都存在邊
圖分類
(1)按邊分：
無向圖 （頂點(diǎn)+無向邊）
有向圖（頂點(diǎn)+有向邊(弧)），弧有弧頭和弧尾之分
(2)按邊的多少分：(這里是模糊概念)
稀疏圖
稠密圖
(3)按任意兩頂點(diǎn)之間是否相連
無向完全圖：任意兩個(gè)頂點(diǎn)之間都存在邊
有向完全圖：任意兩個(gè)頂點(diǎn)之間都存在邊且邊是有向的
無向完全圖的邊數(shù)：n(n-1)/2 (按等差數(shù)列來理解)
有向完全圖的邊數(shù)：n(n-1)
因此，對于n個(gè)頂點(diǎn)和e條邊的圖來說有：
無向圖：0 ≤ e ≤ n(n-1)/2
有向圖：0 ≤ e ≤ n(n-1)
網(wǎng)(NetWork):圖的邊或弧有相關(guān)的數(shù)(該樹叫做權(quán)值weight)
子圖：
假設(shè)圖G=(V,{E})和圖G'=(V,{E'})有：
V' ≤ V ,這里應(yīng)該用包含符號
E' ≤ E ,這里應(yīng)該用包含符號
則有，G' ≤ G 稱G'是G的字圖（subgraph）
2)圖的頂點(diǎn)與邊的關(guān)系
無向圖 G = (V,{E})，邊(v,v')依附于頂點(diǎn)v,v'，而v與v'互為鄰接
度：指針對具體的頂點(diǎn)而言的，指與該頂點(diǎn)相連的邊數(shù)。
各頂點(diǎn)度之和 = 1/2*邊數(shù)之和
有向圖 G = (V,{E}),弧<v,v'>和頂點(diǎn)v,v'相關(guān)聯(lián)，v鄰接到v'，v'鄰接自v
度 = 出度+入度
各頂點(diǎn)出度之和 = 入度之和 = 弧數(shù)之和
3)路徑
回環(huán)（回路）
簡單路徑
簡單回環(huán)
4)連通圖
在無向圖中，任意兩個(gè)頂點(diǎn)之間都是連通的（即存在路徑），則稱該圖是"連通圖"
連通分量：又稱為無向圖中的極大連通子圖（換言之，就是盡可能多的的包含
頂點(diǎn)數(shù)的連通子圖）
注意連通分量的概念，它強(qiáng)調(diào)：
是子圖
子圖要連通
連通子圖包含"極大"頂點(diǎn)數(shù)、
包含依附這些頂點(diǎn)的所有邊
在有向圖中，任意兩個(gè)頂點(diǎn)之間都是連通的(不一定是直接連通)，則稱該圖是"強(qiáng)連通圖"
強(qiáng)連通分量：又稱為有向圖中的極大強(qiáng)連通子圖
5）生成樹
針對連通圖而言的。是連通圖的一個(gè)極小的連通子圖，它含有圖中全部的 n 個(gè)頂點(diǎn)，n-1 條邊
注意：最小生成樹，生成樹中構(gòu)造連通網(wǎng)的代價(jià)最小的生成樹稱為最小生成樹
6）有向樹
在有向圖中，只有一個(gè)頂點(diǎn)的入度為0，求余頂點(diǎn)的入度均為1
7）生成森林
3.圖的存儲結(jié)構(gòu)
由于圖的結(jié)構(gòu)復(fù)雜，因此無法以數(shù)據(jù)元素在內(nèi)存中的物理存儲位置來反映元素之間
的邏輯關(guān)系
5種存儲結(jié)構(gòu)：
(1)鄰接矩陣(Adjacency Martix)
該存儲方式是用兩個(gè)數(shù)組來表示圖：一個(gè)一維數(shù)組存儲頂點(diǎn)信息，一個(gè)二維數(shù)組
存儲(稱為鄰接矩陣)圖中邊或弧的信息。
圖G(V,{E}) 有 n 個(gè)頂點(diǎn)，則其鄰接矩陣定義為：
┌ 1, 若(vi,vj)屬于E,此時(shí)可以看成權(quán)值為1
arc[i][j] = │
└ 0, 反之
注意：對于無向圖，很容易得知該鄰接矩陣是對稱矩陣
有了鄰接矩陣求某一點(diǎn)的度就是該點(diǎn)所在的行或列元素之和
網(wǎng)G(V,{E}),有n個(gè)頂點(diǎn)，則其鄰接矩陣定義為：
┌ Wij, 若(vi,vj)屬于E,
│
arc[i][j] = │ 0, i = j;(自身到自身的權(quán)值是0)
│
└ ∞, 反之
V0 邊數(shù)組： 頂點(diǎn)數(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; //用于存放圖的頂點(diǎn)(一維數(shù)組)
private int[][] adjMar; //鄰接矩陣(二維數(shù)組),存放權(quán)值
private int vertexNum; //圖的頂點(diǎn)數(shù)
private int edgesNum; //圖的邊數(shù)
private final int MAX = 999; //表示網(wǎng)中權(quán)值是無窮大,數(shù)值可調(diào)
private final int MAXSIZE = 10; //鄰接矩陣中存儲頂點(diǎn)的最大默認(rèn)數(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("請輸入圖的頂點(diǎn)數(shù)：");
vertexNum = sc.nextInt();
System.out.print("請輸入圖的邊數(shù)：");
edgesNum = sc.nextInt();
System.out.print("請輸入頂點(diǎn)信息：");
String ver = sc.next();
//初始化頂點(diǎn)存儲數(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) + "條邊的兩個(gè)端點(diǎn)：");
String str = sc.next();
T v1 = (T)(Object)str.charAt(0);
T v2 = (T)(Object)str.charAt(1);
//獲取端點(diǎn)所在的位置
int h = locatVer(v1); //橫坐標(biāo)
int v = locatVer(v2); //縱坐標(biāo)
if(h >= 0 && v >= 0) {
//給鄰接矩陣賦值，
adjMar[h][v] = 1;
adjMar[v][h] = 1; //注意：無向圖的鄰接矩陣是對稱的
}
}
}
/**
* 根據(jù)端點(diǎn)獲得所在頂點(diǎn)數(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)
當(dāng)圖中邊數(shù)遠(yuǎn)小于頂點(diǎn)個(gè)數(shù)時(shí)(即稀疏圖)，采用鄰接矩陣的話，就是造成極大的空間浪費(fèi)。
因此，我們可以考慮使用對邊或弧使用鏈?zhǔn)酱鎯Φ姆绞絹肀苊饪臻g浪費(fèi)
數(shù)組和鏈表相結(jié)合的存儲方法稱為鄰接表。
data,firstedge
┌──┬──┐ adjvex(鄰接點(diǎn)域),next(邊表下一結(jié)點(diǎn)的指針)
V0 0 │V0│ │→ 1| → 2| → 3|^
╱ │ ╲ ├──┼──┤
V1 │ V3 1 │V1│ │→ 1| → 2|^
╲ │ ╱ ├──┼──┤
V2 2 │V2│ │→ 0| → 1| → 3|^
├──┼──┤
3 │V3│ │→ 0| → 2|^
└──┴──┘
鄰接表的建立：
1.建立頂點(diǎn)表：圖中頂點(diǎn)用一個(gè)一維數(shù)組存儲（用鏈表也可以，只是數(shù)組方便讀取頂點(diǎn)信息）
每個(gè)數(shù)據(jù)元素還需要存儲指向第一個(gè)鄰接點(diǎn)的指針，便于查找該頂點(diǎn)的邊的信息
2.建立邊表：圖中每個(gè)頂點(diǎn)Vi的所有鄰接點(diǎn)構(gòu)成一個(gè)線性表，由于每個(gè)頂點(diǎn)的鄰接點(diǎn)的個(gè)數(shù)
不定，所以，采用單鏈表來存儲這些鄰接點(diǎn)。該線性表對于無向圖稱為頂點(diǎn)Vi的邊表，
對于有向圖則稱為以頂點(diǎn)Vi為弧尾的出邊表。
注意:對于有向圖而言，以每個(gè)頂點(diǎn)為弧尾建立的鄰接表稱為鄰接表(便于得到頂點(diǎn)的出度)
對于有向圖而言，以每個(gè)頂點(diǎn)為弧頭建立的鄰接表稱為逆鄰接表(便于得到頂點(diǎn)的入度)
對于網(wǎng)圖，可以在邊表結(jié)點(diǎn)定義中再增加一個(gè)weight的數(shù)據(jù)域，用于存儲權(quán)值
實(shí)現(xiàn)（看下面）該鄰接表的算法復(fù)雜度：O(n+e)， n為頂點(diǎn)個(gè)數(shù)，e為邊的條數(shù)
'代碼描述'
package chapter05.graph.storage;
import java.util.Scanner;
/**
* 圖的鄰接表的存儲方式
* VerNode： 表示頂點(diǎn)表的結(jié)構(gòu)
* ArcNode：表示邊表的結(jié)構(gòu)
* @author Administrator
*
*/
public class AdjListGraph<T> {
protected final int MAXSIZE = 10;
protected VerNode[] adjList; //存儲頂點(diǎn)結(jié)點(diǎn)的數(shù)組
int n; //表示頂點(diǎ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("請輸入圖的頂點(diǎn)數(shù)：");
n = sc.nextInt();
System.out.println("請輸入圖的邊數(shù)：");
e = sc.nextInt();
System.out.println("請輸入圖的頂點(diǎn)信息");
str = sc.next();
//初始化頂點(diǎn)信息
for (int i = 0; i < str.length(); i++) {
adjList[i] = new VerNode<T>();
adjList[i].data = str.charAt(i); //將頂點(diǎn)信息存入新建的頂點(diǎn)中
adjList[i].firstArc = null;
}
System.out.println("請輸入圖的邊的信息:");
ArcNode s; //重復(fù)利用的邊表結(jié)點(diǎn)
for(int j = 0; j < e; j++) {
System.out.println("請輸入第" + (j + 1) + "條邊的兩個(gè)端點(diǎn)：");
str = sc.next();
//得到邊的連個(gè)端點(diǎn)
T v1 = (T)(Object)str.charAt(0);
T v2 = (T)(Object)str.charAt(1);
//確定這連個(gè)頂點(diǎn)在圖中的位置
int loc1 = locateVex(v1);
int loc2 = locateVex(v2);
//在相應(yīng)位置插入邊表結(jié)點(diǎn)
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中查找頂點(diǎn)v在頂點(diǎn)數(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)
含義：從圖中某一頂點(diǎn)出發(fā)訪問遍歷圖中其余頂點(diǎn)，且使每一個(gè)頂點(diǎn)僅被訪問一次，這
一過程就是圖的遍歷
兩種遍歷方式：
(1)深度優(yōu)先(Deep First Search, DFS)
(2)廣度優(yōu)先(Breadth First Search, BFS)
1.深度優(yōu)先遍歷(DFS)
類似于樹的先序遍歷，是樹的先序遍歷的推廣。
思想過程：
1)首先訪問出發(fā)點(diǎn)V
2)然后依次從V出發(fā)搜索V的每個(gè)'鄰接點(diǎn)'W, 若W未曾訪問過，則以W為新的出發(fā)
點(diǎn)為深度優(yōu)先搜索遍歷，直至圖中所有和源點(diǎn)V有路徑相同的頂點(diǎn)均已被訪問為止
3)若此圖中仍有未訪問的頂點(diǎn)，則選另一個(gè)尚未被訪問的頂點(diǎn)作為新的源點(diǎn)重復(fù)
上述過程，直至圖中所有頂點(diǎn)均已被訪問為止。
上述遍歷過程就是遞歸的過程。
下面分別用鄰接矩陣和鄰接表來實(shí)現(xiàn)圖的深度優(yōu)先遍歷
注意：對于點(diǎn)多邊少的圖而言，鄰接表結(jié)構(gòu)效率更高 O(n+e), n為頂點(diǎn)個(gè)數(shù)，e為邊數(shù)
(1)用鄰接矩陣來實(shí)現(xiàn)：算法時(shí)間復(fù)雜度O(n^2)
'代碼描述'
//深度優(yōu)先遍歷圖
public void DFSTraverse() {
//其實(shí)這段是可以不用的，因?yàn)閎oolean的默認(rèn)值就是false
for(int i = 0; i < vertexNum; i++) {
visited[i] = false; //默認(rèn)所有的頂點(diǎn)均為被訪問到
}
System.out.println("圖的深度優(yōu)先遍歷序列：");
for(int j = 0; j < vertexNum; j++) {
//判斷該點(diǎn)是否被訪問到過
if(!visited[j]) {
//表示該點(diǎn)沒有被訪問到過
DFS(j); //則從i好點(diǎn)開始進(jìn)行深度優(yōu)先遍歷
}
}
}
/**
* 利用鄰接矩陣完成連通圖的遍歷
* @param i
*/
private void DFS(int n) {
System.out.print(vertexArr[n] + " "); //訪問到第i個(gè)點(diǎn)，并打印出來
visited[n] = true;
for(int i = 0; i < vertexNum; i++) {
if(!visited[i] && (adjMar[n][i] == 1)) {
DFS(i);
}
}
}
(2)利用鄰接表實(shí)現(xiàn)深度優(yōu)先遍歷：算法時(shí)間復(fù)雜度 O(n+e)
//深度優(yōu)先遍歷
public void DFSTraverse() {
//其實(shí)這段是可以不用的，因?yàn)閎oolean的默認(rèn)值就是false
for(int i = 0; i < n; i++) {
visited[i] = false; //默認(rèn)所有的頂點(diǎn)均為被訪問到
}
System.out.println("圖的深度優(yōu)先遍歷序列：");
for(int j = 0; j < n; j++) {
//判斷該點(diǎn)是否被訪問到過
if(!visited[j]) {
//表示該點(diǎn)沒有被訪問到過
DFS(j); //則從i好點(diǎn)開始進(jìn)行深度優(yōu)先遍歷
}
}
}
/**
* 采用鄰接表完成圖的深度優(yōu)先遍歷
* @param n
*/
private void DFS(int n) {
System.out.print(adjList[n].data + " "); //訪問到第i個(gè)點(diǎn)，并打印出來
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ā)點(diǎn)V
2)接著訪問頂點(diǎn)V的所有鄰接點(diǎn)V1,V2,...Vt
3)然后依次訪問V1，V2,...Vt的所有鄰接點(diǎn)
4)依次執(zhí)行，直至圖中所有的頂點(diǎn)都被訪問到
由該遍歷過程可知，該過程用迭代即可完成
(1)利用鄰接矩陣實(shí)現(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);
}
}
}
/**
* 鄰接矩陣實(shí)現(xiàn)的廣度優(yōu)先遍歷：類似于樹的層序遍歷
* 該部分只能實(shí)現(xiàn)圖的一個(gè)連通子圖
* @param n
*/
private void BFS(int n) {
System.out.print(verArr[n] + " ");
Queue<Integer> queue = new LinkedList<Integer>();
visited[n] = true;
queue.offer(n); //當(dāng)前頂點(diǎn)進(jìn)隊(duì)
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)利用鄰接表實(shí)現(xiàn)的圖的廣度優(yōu)先搜索：O(n+e)
'代碼描述'
/**
* 用鄰接表實(shí)現(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);
}
}
}
/**
* 輔助方法
* 該部分只能實(shí)現(xiàn)圖的一個(gè)連通子圖
* @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); //當(dāng)前頂點(diǎn)進(jìn)隊(duì)
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)的代價(jià)最小(即權(quán)值最小的)的生成樹稱為最小生成樹
注意：一個(gè)連通網(wǎng)的生成樹是不唯一的
而對于非連通的網(wǎng)，其各個(gè)連通分量的生成樹組成的集合為其生成森林。
如何尋找連通網(wǎng)的最小生成樹：
(1)普里姆算法(Prim)
(2)克魯斯卡算法(Kruskal)
1.普里姆算法：
基本思想：設(shè)G=(V,E)是具有n個(gè)頂點(diǎn)的網(wǎng)，T=(U, TE)為G的最小生成樹，U是T的頂點(diǎn)集合，
TE是T的邊集。
則其構(gòu)建過程：
首先從集合V中任選取一點(diǎn)(如V0)放入集合U中，這是U={V0}, TE{Ф},然后選擇這樣的
一條邊：一個(gè)頂點(diǎn)在集合U中，另一個(gè)頂點(diǎn)在集合V-U中,且權(quán)值最小的邊(u,v)（u∈U, v∈V-U）
將該邊放入TE中，并將頂點(diǎn)v加入到U中。重復(fù)上述過程，知道U=V位置，此時(shí)TE中有n-1條邊，那
么T=(U,TE)就是G的一顆最小生成樹。
算法分析：普里姆算法對頂點(diǎn)數(shù)量敏感，因此，它適合稠密圖
時(shí)間復(fù)雜度：O(n^2)
"代碼描述"
/**
* 建立網(wǎng)的最小生成樹
* @param adjMar 表示網(wǎng)圖的鄰接矩陣
* @param n 表示從第n個(gè)頂點(diǎn)開始搜索最小生成樹
*/
public void miniSpanTree_Prim(int[][] adjMar, int n) {
//對輸入的參數(shù)進(jìn)行校驗(yàn)
if(n > vertexNum || n < 1) {
System.out.println("輸入的起始頂點(diǎn)位置有誤！");
return;
}
//保存相關(guān)頂點(diǎn)下標(biāo),
int adjvex[] = new int[vertexNum];
/**
* 用于存放已進(jìn)入最小生成樹中的頂點(diǎn)到其余未進(jìn)入生成樹中的頂點(diǎn)之間
* 權(quán)值最小的邊
*/
int lowcost[] = new int[vertexNum];
/**
* lowcost[i]對應(yīng)的值為0就表示將該頂點(diǎn)Vi加入生成樹
*/
lowcost[n-1] = 0; //表示將第一個(gè)頂點(diǎn)V0加入生成樹中
adjvex[n-1] = n-1; //初始化第一個(gè)頂點(diǎn)下標(biāo)為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;//用于記錄當(dāng)前權(quán)值最小的頂點(diǎn)下標(biāo)
if(i == n-1 || j == n-1) {
//由于n-1時(shí)，在一開始已經(jīng)進(jìn)行過初始化了，因此這里就不能再進(jìn)行篩選了
continue;
}
min = MAX; //初始化min的值為無窮大
while(j < vertexNum) {
if(lowcost[j] != 0 && lowcost[j] < min) {
min = lowcost[j];
k = j; //將權(quán)值最小的頂點(diǎn)的下標(biāo)存入K中
}
j++;
}
System.out.println(vertexArr[adjvex[k]] + "" + vertexArr[k]);
lowcost[k] = 0; //將當(dāng)前頂點(diǎn)的加入生成樹種
// 重新更新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; //將下標(biāo)為k的頂點(diǎn)存入adjvex[]中，
}
}
}
}
2.克魯斯卡爾算法：
基本思想：是按權(quán)值遞增的次序來構(gòu)造的，使生成樹中每一條邊的權(quán)值盡可能地小。
構(gòu)建過程：
先構(gòu)造一個(gè)只含n個(gè)頂點(diǎn)的子圖G'，然后從網(wǎng)中權(quán)值最小的邊開始，若它的添加不
使G'中產(chǎn)生回路，則在G'上加上這條邊，如此反復(fù)，直到G'中加上 n-1 條邊為止。
算法分析：克魯斯卡爾算法是針對邊展開的，因此，它適合稀疏圖
時(shí)間復(fù)雜度：O(eloge)
"代碼描述"
對網(wǎng)的邊封裝成一個(gè)類
public class Edge {
int begin; //表示該邊的起始端點(diǎn)
int end; //表示該邊的結(jié)束端點(diǎn)
int weight; //表示該邊上的權(quán)值
}
/**
* 克魯斯卡爾求最小生成樹的算法
*/
public void miniSpanTree_Kruskal(int[][] adjMar) {
Edge[] edges; //定義邊集數(shù)組
//定義一個(gè)數(shù)組用來判斷邊與邊是否形成環(huán)路
int[] parent = new int[vertexNum];
egdes = adjMarToEdge(adjMar); //這里只是一個(gè)虛擬方法，并沒有真正去實(shí)現(xiàn)它。實(shí)際上實(shí)現(xiàn)也很容易
//對parent[]數(shù)組進(jìn)行初始化,所有的頂點(diǎn)均沒有進(jìn)入最小生成樹中
for(int i = 0; i < vertexNum; i++) {
parent[i] = 0;
}
int n;
int m;
//對每一條邊結(jié)合edges[], parent[]進(jìn)行掃面檢查，
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)還沒有進(jìn)入最小生成樹中。
parent[n] = m; //將此邊的結(jié)尾頂點(diǎn)放入下標(biāo)為起點(diǎn)的parent中，表示此邊(n,m)已經(jīng)進(jìn)入最小生成樹
//打印出已加入最小生成樹中的邊
System.out.println(vertexArr[edges[j].begin] + "" + vertexArr[edges[j].end]);
}
}
}
//查找連線頂點(diǎn)的尾部下標(biāo)
private int find(int[] parent, int f) {
//如果parent[f] = 0，則表明該頂點(diǎn)還沒有進(jìn)入最小生成樹中
//此部分時(shí)間復(fù)雜度：O(loge), e表示邊數(shù)
while(parent[f] > 0) {
/**
* 表明該頂點(diǎn)(準(zhǔn)確來說是 邊(f,parent[f]) 的結(jié)束點(diǎn)parent[f])已經(jīng)進(jìn)入最
* 小生成樹中，因此，要繼續(xù)追蹤下去，看看以此結(jié)束點(diǎn)parent[f]為起始點(diǎn)的
* 下一條邊的結(jié)束點(diǎn)是什么樣的？有可能和已進(jìn)入最小生成樹的頂點(diǎn)構(gòu)成環(huán)
*/
f = parent[f];
}
return f;
}
6.最短路徑
對于網(wǎng)圖(有權(quán)值)和非網(wǎng)圖(權(quán)值可以看成都是1)來說，他們的最短路徑含義是不同的。
非網(wǎng)圖：是指兩頂點(diǎn)之間經(jīng)過的邊數(shù)最少的路徑
網(wǎng)圖：是指兩頂點(diǎn)之間經(jīng)過的權(quán)值之和最小的路徑
我們主要研究網(wǎng)圖的最短路徑，且第一個(gè)頂點(diǎn)是源點(diǎn)，最后一個(gè)頂點(diǎn)是終點(diǎn)。
求最短路徑的算法：
迪杰斯特拉算法(Dijkstra)
弗洛伊德算法(Floyd)
1.迪杰斯特拉算法
是求某一點(diǎn)到其余各點(diǎn)的最短路徑問題的，其核心思想是窮舉法，因此計(jì)算效率不高
整個(gè)過程是基于已經(jīng)求出的最短路徑的基礎(chǔ)，在來求得更遠(yuǎn)頂點(diǎn)的最短路徑。最終，可以
得到我們想要到的那個(gè)點(diǎn)的最短路徑。
算法分析：時(shí)間復(fù)雜度O(n^2)
"代碼描述"
/**
* 計(jì)算從頂點(diǎn)n到其余各點(diǎn)的最短距離
* 注意：此算法目前只能計(jì)算無向圖，對于有向圖需要修改代碼
* @param adjMar 網(wǎng)圖的鄰接矩陣
* @param n 起始頂點(diǎn)
*/
public void dijisktraShortPath(int[][] adjMar, int n) {
//對輸入的參數(shù)進(jìn)行校驗(yàn)
if(n < 1 || n > vertexNum) {
System.out.println("輸入的起始頂點(diǎn)不合理");
return;
}
int s = n - 1;
//用于記錄是否已經(jīng)計(jì)算出s到vi點(diǎn)的最短路徑，
int[] isFinal = new int[vertexNum]; //isFinal[w]=1時(shí),表示已確定到點(diǎn)w的最短路徑
int[] distance = new int[vertexNum]; //表示s到vi的最短路徑長度
int[] path = new int[vertexNum]; //表示在最短路徑上到當(dāng)前點(diǎn)的前驅(qū)頂點(diǎn)下標(biāo)， -1表示到此點(diǎn)沒有路徑
for(int i = 0; i < vertexNum; i++) {
isFinal[i] = 0; //全部置為0，表示還沒有找到到任何點(diǎn)的最短路徑
distance[i] = adjMar[s][i]; //初始化s到其余各點(diǎn)最短路徑長度
/**
* 默認(rèn)沒有路徑，初始化為s，是為了后面好處理
* 這里最好的初始化為-1來表示沒有路徑，但對于無向圖來說無所謂，因?yàn)榫W(wǎng)中只要沒有
* 孤立頂點(diǎn)，那么兩個(gè)頂點(diǎn)之間一定是連通的額，但是對于有向圖而言，情況就不一樣了
* 這里就應(yīng)該初始化為-1
*/
path[i] = s;
}
distance[s] = 0; //s到s的路徑長度為0
isFinal[s] = 1; //s到s的最短路徑是不需要確定的，也就相當(dāng)于已經(jīng)確定了
path[s] = s; //表示s到s的前驅(qū)點(diǎn)下標(biāo)為自身
int min; //記錄s到vi的最短距離
int k = 0; //輔助變量，用于記錄每次確定到s最短距離的那個(gè)頂點(diǎn)的下標(biāo)
//計(jì)算s到所有頂點(diǎn)的最短路徑
for(int j = 0; j < vertexNum; j++) {
if(j == s) {
continue;
}
min = MAX;
//尋找離s最近的頂點(diǎn)
for(int w = 0; w < vertexNum; w++) {
if(isFinal[w] == 0 && distance[w] < min) {
k = w;
min = distance[w];
}
}
isFinal[k] = 1; //表明s到k頂點(diǎn)的最短路徑已確定
// 更新當(dāng)前最短路徑及距離
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到各點(diǎn)的最短路徑
displayPath(s, path);
}
/**
* 根據(jù)前驅(qū)節(jié)點(diǎn)數(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.弗洛伊德算法
是求所有頂點(diǎn)到所有頂點(diǎn)的最短路徑。
算法分析：O(n^3)
"代碼描述"
/**
* 計(jì)算從頂點(diǎn)n到其余各點(diǎn)的最短距離
* 注意：此算法目前只能計(jì)算無向圖，對于有向圖需要修改代碼
* @param graph 網(wǎng)圖的鄰接矩陣
* @param n 起始頂點(diǎn)
*/
public void floydShortPath() {
//定義初始化最短路徑矩陣,初始狀態(tài)為網(wǎng)圖的鄰接矩陣，可以用來計(jì)算最小路徑長度
int[][] shortPath = new int[MAXSIZE][MAXSIZE];
//定義前驅(qū)結(jié)點(diǎn)矩陣,可以用來求出最短路徑
int[][] path = new int[MAXSIZE][MAXSIZE];
//初始化前驅(qū)節(jié)點(diǎn)矩陣和最短路徑權(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;
}
}
/**
* 是決定該算法時(shí)間復(fù)雜度的主要地方：
* 三層循環(huán)，很容易得知時(shí)間復(fù)雜度為：O(n^3)
* 計(jì)算所有點(diǎn)其他各點(diǎn)的最短路徑
* w表示中轉(zhuǎn)頂點(diǎn)的下標(biāo)，m是起點(diǎn)，n是結(jié)束頂點(diǎn)
* 挨著以w控制的頂點(diǎn)作為中轉(zhuǎn)點(diǎn)，來求所有點(diǎn)到其余所有點(diǎn)的最短路徑距離
*/
for(int w = 0; w < vertexNum; w++) {
for(int m = 0; m < vertexNum; m++) {
/**
* 注意：這個(gè)n當(dāng)然也可以是從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)過下標(biāo)為w的頂點(diǎn)比原來兩點(diǎn)間的路徑更短，就要修正這兩點(diǎn)間的距離
shortPath[m][n] = shortPath[m][w] + shortPath[w][n];
shortPath[n][m] = shortPath[m][n]; //因?yàn)樵摼仃囀菍ΨQ的，所以可以這么寫
/**
* 修改路徑經(jīng)過下標(biāo)為w的頂點(diǎn)，表示到相應(yīng)的點(diǎn)時(shí)，要經(jīng)過該點(diǎn),
* 準(zhǔn)確說，這個(gè)點(diǎn)是到達(dá)該點(diǎn)的前驅(qū)結(jié)點(diǎn)。
*/
path[m][n] = path[m][w];
path[n][m] = path[m][n]; //因?yàn)樵摼仃囀菍ΨQ的，所以可以這么寫
}
}
}
}
//顯示最短路徑
displayPath(path, shortPath);
}
/**
* 打印所有點(diǎn)到其余所有點(diǎn)的最短路徑
* @param path 最短路徑的前驅(qū)結(jié)點(diǎn)下標(biāo)矩陣（在該矩陣上縱向打印路徑）
* @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]; //獲得第一個(gè)路徑頂點(diǎn)下標(biāo)
System.out.print("path: " + i);
while(k != j) {
System.out.print("->" + k);
k = path[k][j]; //獲得下一個(gè)路徑頂點(diǎn)的下標(biāo)
}
System.out.println("->" + j);
}
System.out.println();
}
}
思考：分析迪杰斯特啦和弗洛伊德求最短路徑的算法，二者均可求出所有點(diǎn)到其余所有點(diǎn)
之間的最短路徑。只不過對于迪杰斯特拉算法而言，需要循環(huán)調(diào)用迪杰斯特拉算法，時(shí)間
復(fù)雜度為O(n^3), 而弗洛伊德算法只需一次調(diào)用即可全部計(jì)算出來，盡管其時(shí)間復(fù)雜度也
為O(n^3)，弗洛伊德算法更加簡潔。
7.拓?fù)渑判?Topological Sort)
這里的排序并不是平時(shí)理解的安大小排序的，而是安工作步驟先后順序排序的，主要解決一個(gè)工程能否
順利進(jìn)行。
用于工程施工、生產(chǎn)流程、教學(xué)安排等應(yīng)用中來合理安排工作流程步驟
這些流程圖都是無環(huán)的有向圖(圖中的活動(dòng)都是有先后順序的)
(1)AOV網(wǎng)(Activity On Vertex Network): 在一個(gè)表示工程的有向圖中，用頂點(diǎn)表示活動(dòng)，用弧表示
活動(dòng)之間的優(yōu)先關(guān)系，這樣的有向圖稱為AOV網(wǎng)
注意：AOV網(wǎng)中沒有回路
(2)拓?fù)湫蛄校涸O(shè)G=(V,E)是一個(gè)具有n個(gè)頂點(diǎn)的有向圖，V中的頂點(diǎn)序列V1,V2,...Vn，滿足若從Vi到Vj有
一條路徑，則在頂點(diǎn)序列中頂點(diǎn)Vi必在頂點(diǎn)Vj之前，則我們成這樣的頂點(diǎn)序列為拓?fù)湫蛄小?
(3)拓?fù)渑判颍壕褪菍σ粋€(gè)有向圖構(gòu)造拓?fù)湫蛄械倪^程
(4)拓?fù)渑判蛩惴ǎ?基本思想：從AOV網(wǎng)中選擇一個(gè)入讀為0的頂點(diǎn)輸出，然后刪除此頂點(diǎn)，并刪除以此頂點(diǎn)為尾的弧，
繼續(xù)重復(fù)此步驟，知道輸出全部頂點(diǎn)或者AOV網(wǎng)中不存在入讀為0的頂點(diǎn)為止。
因?yàn)樵谂判虻倪^程中要頻繁刪除頂點(diǎn)，因此選擇使用鄰接表來做存儲結(jié)構(gòu)（而不用鄰接矩陣做存儲結(jié)構(gòu)）
由于要查找入度為0的頂點(diǎn)，需要在鄰接表的頂點(diǎn)結(jié)構(gòu)中增加入度域in，
鄰接表頂點(diǎn)結(jié)構(gòu)：
┌─────┬──────┬───────────┐
│ in │ data │ firstedge │
└─────┴──────┴───────────┘
算法分析：O(n+e)
"代碼描述"
1.鄰接表頂點(diǎn)結(jié)構(gòu)
public class VerNode<T> {
public T data; //存儲頂點(diǎn)的名稱或相關(guān)信息
public ArcNode firstArc; //指向頂點(diǎn)Vi的第一個(gè)鄰接點(diǎn)的邊結(jié)點(diǎn)
public int in;//增加一個(gè)入度域，方便拓?fù)渑判驎r(shí)
public VerNode() {
this.data = null;
this.firstArc = null;
}
}
2.拓?fù)渑判?/**
* 進(jìn)行拓?fù)渑判? * 要用到棧這個(gè)數(shù)據(jù)結(jié)構(gòu)，我們就選用前面棧一章寫的棧數(shù)據(jù)結(jié)構(gòu)
*/
public void topologicalSort() {
//定義一個(gè)棧(用的之前在棧一章的數(shù)據(jù)結(jié)構(gòu))，用于存儲入度為0的頂點(diǎn)
LinkStack<VerNode<String>> stack = new LinkStack<VerNode<String>>();
//將入度為0的頂點(diǎn)存入棧中：O(n)
for(int i = 0; i < n; i++) {
if(adjList[i].in == 0) {
stack.push(adjList[i]);
}
}
int count = 0; //用于記錄輸出頂點(diǎn)的個(gè)數(shù)
ArcNode arcEdge; //用于循環(huán)使用, 鄰接表結(jié)構(gòu)中的邊表結(jié)點(diǎn)結(jié)構(gòu)
VerNode<String> p; //用于循環(huán)使用, 鄰接表結(jié)構(gòu)中的頂點(diǎn)結(jié)構(gòu)
int k; //用于循環(huán)接受邊表中結(jié)點(diǎn)在頂點(diǎn)表中的位置
//當(dāng)棧不為空，循環(huán)始終進(jìn)行
while(!stack.isEmpty()) {
//打印此入度為0的頂點(diǎn)
p = stack.pop();
if(count == (n - 1)) {
System.out.print(p.data);
}else{
System.out.print(p.data + "->");
}
//統(tǒng)計(jì)輸出的頂點(diǎn)數(shù)
count ++;
arcEdge = p.firstArc;
//處理與p鄰接的結(jié)點(diǎn)：O(e)
while(arcEdge != null) {
k = arcEdge.adjVer;
/**
* --adjList[k].in ，這個(gè)動(dòng)作就表明將到與上面p結(jié)點(diǎn)相連的
* 結(jié)點(diǎn)的之間的邊刪除了
*/
if((--adjList[k].in) == 0) {
stack.push(adjList[k]); //將入度為0的頂點(diǎn)入棧
}
arcEdge = arcEdge.next;
}
}
//可用于檢查網(wǎng)中有沒有環(huán)
if (count < n) {
//System.out.println("網(wǎng)中存有環(huán)");
}else {
//System.out.println("正常");
}
}
8.關(guān)鍵路徑
拓?fù)渑判蛑饕菫榻鉀Q一個(gè)工程能否順序進(jìn)行的問題，而關(guān)鍵路徑主要是解決工程完成需要的最短時(shí)間的問題
(1)AOE網(wǎng)(Activity On Edge NetWork)
在一個(gè)表示工程的的帶權(quán)有向圖中，用頂點(diǎn)表示事件，用有向邊表示活動(dòng)，用邊上的權(quán)值表示活動(dòng)的
持續(xù)時(shí)間，這種有向圖的邊表示活動(dòng)網(wǎng)，我們稱之為AOE網(wǎng)
源點(diǎn)：沒有入邊，只有出邊
匯點(diǎn)：沒有出邊，只有入邊
注意：AOV網(wǎng)的頂點(diǎn)表示活動(dòng)， 邊表示活動(dòng)之間的優(yōu)先關(guān)系
AOE網(wǎng)的邊表示活動(dòng)，邊也表示優(yōu)先關(guān)系，邊上的權(quán)值表示活動(dòng)持續(xù)的時(shí)間
AOE網(wǎng)是建立在活動(dòng)之間制約關(guān)系(先后關(guān)系)沒有矛盾的基礎(chǔ)上，再來分析完成整個(gè)工程至少需要多少時(shí)間
(2)關(guān)鍵路徑
把路徑上各個(gè)活動(dòng)所持續(xù)的時(shí)間之和稱為路徑長度，從源點(diǎn)到匯點(diǎn)的最大長度的路徑叫關(guān)鍵路徑，
在關(guān)鍵路徑上的活動(dòng)叫關(guān)鍵活動(dòng)。
那么，如果我們想縮短整個(gè)工程活動(dòng)的完成時(shí)間，就只需在關(guān)鍵路徑上算短相應(yīng)的活動(dòng)時(shí)間就能
做到整體工期縮短
(3)關(guān)鍵路徑的算法實(shí)現(xiàn)
基本思想：在整個(gè)AOE網(wǎng)上尋找所有活動(dòng)的最早開始時(shí)間和最晚開始時(shí)間，并比較它們，如果而二者
相等，則表明該活動(dòng)是關(guān)鍵活動(dòng)（當(dāng)然也就是關(guān)鍵路徑上的一段了），如果不想等那就不是關(guān)鍵活動(dòng)
需要知道的幾個(gè)參數(shù)：
1)事件的最早發(fā)生時(shí)間etv(earliest tiem of vertex)：即頂點(diǎn)vk的最早發(fā)生時(shí)間
注意：etv[i]的求解必須在所有前驅(qū)的最早發(fā)生時(shí)間求得之后才能確定，因此是在拓?fù)溆行虻幕A(chǔ)上進(jìn)行的
2)事件的最晚發(fā)生時(shí)間ltv：即在不推遲整個(gè)工程的前提下，頂點(diǎn)vk的最晚發(fā)生時(shí)間
注意：ltv[i]必須在其所有后繼的最晚發(fā)生時(shí)間求得之后才能確定，因此是在逆拓?fù)溆行虻幕A(chǔ)上進(jìn)行的
3)活動(dòng)<Vi,Vj>所需的時(shí)間：t(i,j),即AOE網(wǎng)上的邊的權(quán)值
4)活動(dòng)<Vi,Vj>最早開工時(shí)間ete(earliest time of edge)：即弧ak的最早發(fā)生時(shí)間
ete(i,j) = etv[i];
5)活動(dòng)<Vi,Vj>最晚開工時(shí)間lte：即在不推遲整個(gè)工程的前提下，弧ak的最晚發(fā)生時(shí)間
lte(i,j) = ltv[i] - t(i,j)
由 etv 和 ltv 求得ete, lte
當(dāng) ete[k] == lte[k] 時(shí)，該活動(dòng)為關(guān)鍵活動(dòng)
算法描述：
時(shí)間復(fù)雜度：O(n+e)
"代碼描述"
1.頂點(diǎn)表結(jié)點(diǎn)結(jié)構(gòu)
//表示頂點(diǎn)表結(jié)點(diǎn)的結(jié)構(gòu)
public class VerNode<T> {
public T data; //存儲頂點(diǎn)的名稱或相關(guān)信息
public ArcNode firstArc; //指向頂點(diǎn)Vi的第一個(gè)鄰接點(diǎn)的邊結(jié)點(diǎn)
public int in;//增加一個(gè)入度域，方便拓?fù)渑判驎r(shí)
public VerNode() {
this.data = null;
this.firstArc = null;
}
}
2.邊表結(jié)點(diǎn)的結(jié)構(gòu)
public class ArcNode {
public int adjVer; //鄰接點(diǎn)域，用于存儲該該點(diǎn)結(jié)點(diǎn)域數(shù)組中的下標(biāo)
public int weight; //用于網(wǎng)圖存儲權(quán)值
public ArcNode next; //指向下一個(gè)鄰接點(diǎn)
public ArcNode() {
adjVer = 0;
weight = 0;
next = null;
}
}
3.關(guān)鍵路徑的算法實(shí)現(xiàn)
/**
* 尋找關(guān)鍵路徑：是建立在拓?fù)湫蛄械幕A(chǔ)上進(jìn)行相關(guān)關(guān)鍵路徑的尋找
*/
public void getCriticalPath() {
Object[] obj = topologicalSort(); //拓?fù)渑判颍篛(n+e)
//通過拓?fù)渑判蚍祷馗鱾€(gè)事件最早完成時(shí)間
int[] eventEarly = (int[])obj[0];
//返回拓?fù)湫蛄? LinkStack<Integer> topPath = (LinkStack<Integer>)obj[1];
int[] eventLast = new int[n];//定義事件發(fā)生最晚的數(shù)組，好好理解這個(gè)
int actEarly; //活動(dòng)最早發(fā)生時(shí)間變量
int actLast; //活動(dòng)最晚發(fā)生時(shí)間變量
//初始化最晚事件數(shù)組:O(n)
for(int i = 0; i < n; i++) {
/**
* 因?yàn)槭录淖钔戆l(fā)生時(shí)間必須在其所有后繼的最遲發(fā)生的時(shí)間確定后才能確定的
* 而最后一個(gè)事件(匯點(diǎn))的最晚發(fā)生時(shí)間就要保正整個(gè)工程部耽誤，因此，它的最晚
* 發(fā)生時(shí)間就是整個(gè)工程的最早發(fā)生時(shí)間。
* 因此，才會這樣初始化
*/
eventLast[i] = eventEarly[n-1];
}
int temp; //循環(huán)中，用來臨時(shí)存儲topPath出棧的頂點(diǎn)下標(biāo)號
int k; //用于循環(huán)接受邊表中結(jié)點(diǎn)在頂點(diǎn)表中的位置
ArcNode p;//用于循環(huán)使用, 鄰接表結(jié)構(gòu)中的邊表結(jié)點(diǎn)結(jié)構(gòu)
//計(jì)算各個(gè)頂點(diǎn)的最晚發(fā)生時(shí)間,整個(gè)過程是在逆拓?fù)湫蛄械幕A(chǔ)上進(jìn)行的:O(n+e)
while(!topPath.isEmpty()) {
//將拓?fù)湫蛄许樞虺鰲? 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)鍵活動(dòng)，當(dāng)活動(dòng)的最早時(shí)間和最晚時(shí)間是一樣的時(shí)候，就表明該
//活動(dòng)間的路徑為關(guān)鍵活動(dòng)：O(n+e)
for(int j = 0; j < n; j++) {
p = adjList[j].firstArc;
while(p != null) {
k = p.adjVer;
actEarly = eventEarly[j]; //活動(dòng)最早發(fā)生時(shí)間
actLast = eventLast[k] - p.weight; //活動(dòng)的最晚發(fā)生時(shí)間
if(actEarly == actLast) {
//兩者相等則表明該活動(dòng)在關(guān)鍵路徑上
System.out.print("<" +adjList[j].data + "," + adjList[k].data +">(" +p.weight+") ");
}
p = p.next;
}
}
}
/**
* 進(jìn)行拓?fù)渑判?O(n+e)
* 要用到棧這個(gè)數(shù)據(jù)結(jié)構(gòu)，我們就選用前面棧一章寫的棧數(shù)據(jù)結(jié)構(gòu)
*/
private Object[] topologicalSort() {
/**
* 定義一個(gè)棧，用于存儲入度為0的頂點(diǎn)
* 存儲拓?fù)湫蛄械捻旤c(diǎn)下標(biāo)號(即該頂點(diǎn)在鄰接表的頂點(diǎn)數(shù)組中的存儲位置，從0開始的)
* 為啥不直接存儲該頂點(diǎn)呢？
* 一開始也是采用存儲的頂點(diǎn)，但是該頂點(diǎn)結(jié)構(gòu)在存儲的時(shí)候并沒有存儲其位置
* 信息，導(dǎo)致下面在計(jì)算各頂點(diǎn)的最早事件發(fā)生時(shí)間時(shí)，無法獲取存儲相應(yīng)的最早事件發(fā)生的
* 數(shù)組中的元素內(nèi)容。相反直接存儲入度為0的頂點(diǎn)的下標(biāo)號，那么想找該頂點(diǎn)時(shí)可以直接在adjList[]數(shù)組中獲取。
*/
LinkStack<Integer> stack = new LinkStack<Integer>();
//定義事件發(fā)生最早的數(shù)組（最早發(fā)生即到該點(diǎn)的最長路徑）
int[] eventEarly = new int[n];
//將入度為0的頂點(diǎn)存入棧中,同時(shí)初始化earlyTiem
for(int i = 0; i < n; i++) {
eventEarly[i] = 0; //全部初始化為0
if(adjList[i].in == 0) {
stack.push(i);
}
}
/**
* 拓?fù)湫蛄胁挥弥苯釉诳刂婆_打印出來，而是用topPath存儲這些序列頂點(diǎn)
* 同上面的stack一樣，也是直接存儲相應(yīng)的頂點(diǎn)下標(biāo)號
*/
LinkStack<Integer> topPath = new LinkStack<Integer>();
int count = 0; //用于記錄輸出頂點(diǎn)的個(gè)數(shù)
ArcNode arcEdge; //用于循環(huán)使用, 鄰接表結(jié)構(gòu)中的邊表結(jié)點(diǎn)結(jié)構(gòu)
VerNode<String> p; //用于循環(huán)使用, 鄰接表結(jié)構(gòu)中的頂點(diǎn)結(jié)構(gòu)
int k; //用于循環(huán)接受邊表中結(jié)點(diǎn)在頂點(diǎn)表中的位置
int temp; //用于臨時(shí)存儲從stack中取出的頂點(diǎn)下標(biāo)號
//當(dāng)棧不為空，循環(huán)繼續(xù)進(jìn)行
while(!stack.isEmpty()) {
//打印此入度為0的頂點(diǎn)
temp = stack.pop();
p = adjList[temp]; //由下標(biāo)號結(jié)合adjList[]可直接獲取對應(yīng)的頂點(diǎn)
topPath.push(temp); //將拓?fù)漤旤c(diǎn)標(biāo)號順序存入,不用在控制臺打印出來
//統(tǒng)計(jì)輸出的頂點(diǎn)數(shù)
count ++;
arcEdge = p.firstArc; //獲取與p鄰接的頂點(diǎn)
//處理與p鄰接的結(jié)點(diǎn)
while(arcEdge != null) {
k = arcEdge.adjVer; //該頂點(diǎn)在頂點(diǎn)數(shù)組中的存儲位置
/**
* --adjList[k].in ，這個(gè)動(dòng)作就表明將到與上面p頂點(diǎn)相連的
* 頂點(diǎn)之間的邊刪除了，同時(shí)該點(diǎn)的入度也就跟著減1
*/
if((--adjList[k].in) == 0) {
//stack.push(adjList[k]); //將入度為0的頂點(diǎn)入棧
stack.push(k); //將入度為0的頂點(diǎn)入棧
}
//計(jì)算該頂點(diǎn)(事件)的最早發(fā)生時(shí)間
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("正常");
}
//返回兩個(gè)重要的結(jié)果
return new Object[]{eventEarly, topPath};
}