資料結構：關鍵路徑，利用DFS遍歷每一條關鍵路徑JAVA語言實現
這是我們學校做的資料結構課設，要求分別輸出關鍵路徑，我查遍資料java版的只能找到關鍵路徑，但是無法分別輸出關鍵路徑
c++有可以分別輸出的，所以在明白思想後自己寫了一個java版的
函式帶有輸入函式也有已經存進去的圖
如上圖關鍵路徑被分別輸出（採用了DFS演算法）：
例： AOE 圖如下：
演算法設計如下：
1. 首先，要求關鍵路徑，要先要先寫拓撲排序，如果圖中有環， 就無法進行關鍵路徑的求解，直接跳出。
拓撲排序：利用棧 stack，先將入度為0事件節點的加入棧中， 然後編歷後面的活動節點，每次給活動節點的入度減一，然 後將入度為 0的加入棧 stack中，每次出棧的加入棧stack 中， stack1中的元素拓撲排序的逆序，然後 根據核心算 法：
if ( etv [p.getData()]+p1.getInfo()> etv [p1.getAdjvex()]){
etv [p1.getAdjvex()]= etv [p.getData()]+p1.getInfo();
}
計算出事件的最早發生時間的事件存入 etv
然後根據 count 來判斷圖中有沒有迴路。
2. 然後對拓撲排序的逆序求事件的最晚發生時間，根據核心法：
if ( ltv [p1.getAdjvex()]-p1.getInfo()< ltv [p.getData()]){
ltv [p.getData()]=Math. abs ( ltv [p1.getAdjvex()]-p1.getInfo());
}
算出事件的最晚發生時間存入陣列 ltv中。
3. 接著求活動的最晚發生時間 el和活動的最早發生時間ee
ee= etv [i];
el= ltv [pn.getAdjvex()]-pn.getInfo();
當 ee和el相等的時候，本活動就為關鍵活動，關鍵路徑算出 來了。
解決輸出每條關鍵路徑：
4. 輸出每一條關鍵路徑：利用 DFS演算法（回溯演算法），圖在遍 歷以前已經將關鍵路徑用 visited 陣列標記了，故遍歷的時候 只遍歷關鍵路徑，原理如圖：
當 visited 為 0 的時候為關鍵節點，然後遍歷此節點進入遞迴：
while (p!= null ){
if ( visited [p.getAdjvex()]!= 1 ){
/**
* 是關鍵路徑就入棧
*/
stack2 .push(p);
DFS(p.getAdjvex());
/**
* 遇見死路回退的時候出棧
*/
stack2 .pop();
}
本演算法類似 走迷宮，並且每走一個點，就把這個點入棧，並且將 visited陣列中的本節點的值存為1，代表遍歷過了：
visited [k]= 1 ;
然後遞迴進入下一個節點，遇見終點就先遍歷並輸出棧中的元素：
if (k== finall ) {
for ( int i= 0 ;i< stack2 . size ;i++) {
System. out .print( stack2 .peekTravel(i).getName() + "->" );
}
}
一邊退回一邊出棧：
DFS(p.getAdjvex());
/**
* 遇見死路回退的時候出棧
*/
stack2 .pop();
即棧中元素只到分岔點，退回上一次的分岔點，然後遞迴進入下一條路，直到遍歷結束，然後輸出了全部的關鍵路徑。
DFS演算法全部程式碼：
/**
* 為了輸出每條關鍵路徑用到 DFS 演算法
* @param k 起點再陣列中的下標
*/
public void DFS ( int k){
visited [k]= 1 ;
lineNode p= new lineNode();
p= vexList [k].getNext();
/**
* 終點永遠是關鍵節點
*/
visited [ finall ]= 0 ;
/**
* 如果走到終點遍歷棧的元素
*/
if (k== finall ) {
for ( int i= 0 ;i< stack2 . size ;i++) {
System. out .print( stack2 .peekTravel(i).getName() + "->" );
}
}
/**
* 遍歷節點後面的連結串列
*/
while (p!= null ){
if ( visited [p.getAdjvex()]!= 1 ){
/**
* 是關鍵路徑就入棧
*/
stack2 .push(p);
DFS(p.getAdjvex());
/**
* 遇見死路回退的時候出棧
*/
stack2 .pop();
}
System. out .println();
p=p.getNext();
}
}
DFS 演算法流程圖：
（流程圖有問題，左端回退出棧少了迴圈）
原始碼如下：
package dataproject.importanRoad;
import dataproject.stack.myArrayStack;
import java.util.Scanner;
/**
* @author 李正陽17060208112
*/
public class lessonWord {
/**
* 頂點陣列
*/
private vertexNode[] vexList;
/**
* etv 事件最早發生時間(即頂點）
* ltv 事件最晚發生時間
*/
private int etv[], ltv[];
/**
* 拓撲排序所用到的棧
*/
private myArrayStack<vertexNode> stack=new myArrayStack<>();
private myArrayStack<vertexNode> stack1=new myArrayStack<>();
/**
* 為了輸出關鍵路徑，標明哪些是關鍵節點
*/
static int MAX_VERTEXNUM = 100;
static int [] visited = new int[MAX_VERTEXNUM];
/**
*關鍵路徑用到的棧隊，陣列
*/
private myArrayStack<lineNode> stack2=new myArrayStack<>();
private static int finall;
/**
* 使用鍵盤輸入來構建圖構建圖
*/
public void createGraph(){
vertexNode pl1=new vertexNode();
lineNode pl=new lineNode();
int n;
Scanner in=new Scanner(System.in);
System.out.println("請輸入共有多少個節點：");
n=in.nextInt();
vexList = new vertexNode[n];
for (int i=0;i<n;i++){
int p;
/**
* 構建節點
*/
System.out.println("節點"+(i+1)+"節點存在陣列中的位置 "+"節點名字");
vertexNode v= new vertexNode( in.nextInt(), null, in.nextLine());
pl1=v;
pl=v.getNext();
System.out.println("請輸入此節點後有多少個邊：");
p=in.nextInt();
for (int j=0;j<p;j++){
/**
* 構建活動即事件
*/
System.out.println("邊"+(j+1)+"後續節點在陣列中的位置 "+"權值 "+"邊的名字");
lineNode a= new lineNode(in.nextInt(),in.nextInt(), in.nextInt(), null,in.next(),false);
if(j==0){
pl1.setNext(a);
pl=pl1.getNext();
}else {
pl.setNext(a);
pl=pl.getNext();
}
}
vexList[i]=v;
}
}
/**
* 儲存下的圖，和我畫出的圖一樣，方便測試
*/
public void craeteGraph() {
/**
* 所有節點即事件
*/
vertexNode v1 = new vertexNode( 0, null, "v1");
vertexNode v2 = new vertexNode( 1, null, "v2");
vertexNode v3 = new vertexNode(2, null, "v3");
vertexNode v4 = new vertexNode( 3, null, "v4");
vertexNode v5 = new vertexNode(4, null, "v5");
vertexNode v6 = new vertexNode(5, null, "v6");
vertexNode v7 = new vertexNode(6, null, "v7");
vertexNode v8 = new vertexNode(7, null, "v8");
vertexNode v9 = new vertexNode(8, null, "v9");
/**
* v1節點
* a1活動，a2活動，a3活動
*/
lineNode v12 = new lineNode(0,1, 6, null,"a1",false);
lineNode v13 = new lineNode(0,2, 4, null,"a2",false);
lineNode v14 = new lineNode(0,3, 5, null,"a3",false);
lineNode a12=new lineNode(0,9,5,null,"a12",false);
v1.setNext(v12);
v12.setNext(v13);
v13.setNext(v14);
v14.setNext(a12);
/**
* v2節點
* a4活動
*/
lineNode v25 = new lineNode(1, 4, 1, null,"a4",false);
v2.setNext(v25);
/**
* v3節點
* a5活動
*/
lineNode v35 = new lineNode(2,4, 1, null,"a5",false);
v3.setNext(v35);
/**
* v4節點
* a6活動
*/
lineNode v46 = new lineNode(3,5, 2, null,"a6",false);
v4.setNext(v46);
/**
* v5節點
* a7活動 a8活動
*/
lineNode v57 = new lineNode(4,6, 9, null,"a7",false);
lineNode v58 = new lineNode(4,7, 7, null,"a8",false);
v5.setNext(v57);
v57.setNext(v58);
/**
* v6節點
* a9活動
*/
lineNode v68 = new lineNode(5,7, 4, null,"a9",false);
v6.setNext(v68);
/**
* v7節點
* a10活動
*/
lineNode v79 = new lineNode(6,8, 2, null,"a10",false);
v7.setNext(v79);
/**
* v8節點
* a11活動
*/
lineNode v89 = new lineNode(7,8, 4, null,"a11",false);
v8.setNext(v89);
/**
* v10節點
*
*/
vertexNode v10=new vertexNode(9,null,"西安");
/**
* v11節點
*/
vertexNode v11=new vertexNode(10,null,"北京");
lineNode a13=new lineNode(8,10,6,null,"a13",false);
lineNode a14=new lineNode(9,8,7,null,"a14",false);
v11.setNext(a14);
v10.setNext(a13);
/**
* 物件陣列：vexList，儲存節點構建了圖
*/
vexList = new vertexNode[11];
vexList[0] = v1;
vexList[1] = v2;
vexList[2] = v3;
vexList[3] = v4;
vexList[4] = v5;
vexList[5] = v6;
vexList[6] = v7;
vexList[7] = v8;
vexList[8] = v9;
vexList[9]=v10;
vexList[10]=v11;
}
/**
* 拓撲排序
* @return true 排序成功 false 失敗
*/
public boolean topologicalSort() {
/**
* 計算入度：初始化所有節點的入度
*/
for (int i=0;i<vexList.length;i++){
vexList[i].setIn(0);
}
/**
* 遍歷每個節點後面的連結串列，然後就給弧尾頂點加一
*/
for (int i=0;i<vexList.length;i++){
lineNode p=new lineNode();
p=vexList[i].getNext();
while (p!=null){
vertexNode vertexNode=new vertexNode();
vertexNode=vexList[p.getAdjvex()];
vertexNode.setIn(vertexNode.getIn()+1);
p=p.getNext();
}
}
/**
* 計數：用來判斷是否無環
*/
int count=0;
vertexNode p = new vertexNode();
lineNode p1 = new lineNode();
System.out.println("拓撲排序：");
/**
* 對事件最早發生時間陣列初始化
*/
etv=new int[vexList.length];
for (int i=0;i<etv.length;i++){
etv[i]=0;
}
/**
* 將度為0的入棧
*/
for (int i = 0; i < vexList.length; i++) {
if (vexList[i].in == 0) {
stack.push(vexList[i]);
}
}
/**
* 遍歷領接表裡面邊結點，遍歷到入度就減一
*/
while (!stack .empty()) {
p=stack.pop();
count++;
/**
* 拓撲排序的逆序加入棧2中
*/
stack1.push(p);
System.out.print(p.getName()+" ");
if(p.getNext()!=null){
p1=p.getNext();
}
/**
* 核心演算法計算事件最早發生時間etv
*/
while (p1!=null){
vexList[p1.getAdjvex()].setIn(vexList[p1.getAdjvex()].getIn()-1);
if(vexList[p1.getAdjvex()].getIn()==0){
stack.push(vexList[p1.getAdjvex()]);
}
if(etv[p.getData()]+p1.getInfo()>etv[p1.getAdjvex()]){
etv[p1.getAdjvex()]=etv[p.getData()]+p1.getInfo();
}
p1=p1.getNext();
}
}
/**
* 計數小於節點數就有迴路
* 等於就無迴路
*/
if(count!=vexList.length){
System.out.println();
System.out.println("圖有迴路！！");
return true;
}else {
System.out.println();
System.out.println("圖無迴路！！");
}
return false;
}
/**
* 關鍵路徑的方法
*/
public void criticalPath() {
/**
* 活動的最早發生時間 ee
* 活動發生的最晚時間 el
* p 指標掃描事件節點
* p1 掃描活動節點
*/
int ee,el;
vertexNode p = new vertexNode();
lineNode p1 = new lineNode();
/**
* 先進行拓撲排序判斷圖有沒有環
*/
if (topologicalSort()){
return;
}
/**
* 初始化ltv陣列
*/
finall=stack1.peek().getData();
ltv=new int[vexList.length];
for (int i=0;i<vexList.length;i++){
ltv[i]=etv[finall];
}
/**
* 已經獲得了拓撲排序的逆序stack2，所以對逆序求最晚發生時間
*/
while (!stack1.empty()){
p=stack1.pop();
if(p.getNext()!=null){
p1=p.getNext();
}
while (p1!=null){
if (ltv[p1.getAdjvex()]-p1.getInfo()<ltv[p.getData()]){
ltv[p.getData()]=ltv[p1.getAdjvex()]-p1.getInfo();
}
p1=p1.getNext();
}
}
for (int i=0;i<visited.length;i++){
visited[i]=1;
}
System.out.print("關鍵活動為：");
/**
* 求ee,el和關鍵路徑 count1表示關鍵活動的數量
*/
int count1=0;
for (int i=0;i<vexList.length;i++){
lineNode pn=new lineNode();
pn=vexList[i].getNext();
while (pn!=null){
ee=etv[i];
el=ltv[pn.getAdjvex()]-pn.getInfo();
if(ee==el){
count1++;
visited[vexList[i].getData()]= 0;
System.out.print(pn.getName()+",");
}
pn=pn.getNext();
}
}
System.out.println();
System.out.println("最大時間："+ltv[finall]);
System.out.println();
}
/**
* 為了輸出每條關鍵路徑用到DFS演算法
* @param k 起點再陣列中的下標
*/
public void DFS(int k){
visited[k]=1;
lineNode p=new lineNode();
p=vexList[k].getNext();
/**
* 終點永遠是關鍵節點
*/
visited[finall]=0;
/**
* 如果走到終點遍歷棧的元素
*/
if(k==finall) {
for (int i=0;i<stack2.size;i++) {
System.out.print(stack2.peekTravel(i).getName() + "->");
}
}
/**
* 遍歷節點後面的連結串列
*/
while (p!=null){
if(visited[p.getAdjvex()]!=1){
/**
* 是關鍵路徑就入棧
*/
stack2.push(p);
DFS(p.getAdjvex());
/**
* 遇見死路回退的時候出棧
*/
stack2.pop();
}
System.out.println();
p=p.getNext();
}
}
/**
* 活動節點
*/
class lineNode {
/**
* 儲存該頂點對應的下標
*/
private int adjvex;
/**
* 儲存權值
*/
private int info;
/**
* 指向下一個節點
*/
private lineNode next;
/**
* 活動的名字
*/
private String name;
public boolean isMark() {
return mark;
}
public void setMark(boolean mark) {
this.mark = mark;
}
/**
* 標識位：標識有沒有遍歷過
*/
private boolean mark;
/**
* 弧頭
*
*/
private int head;
public int getHead() {
return head;
}
public void setHead(int head) {
this.head = head;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public lineNode(int head,int adjvex, int info, lineNode next, String name,boolean mark) {
this.adjvex = adjvex;
this.info = info;
this.next = next;
this.name=name;
this.mark=mark;
this.head=head;
}
public lineNode() {
}
public int getAdjvex() {
return adjvex;
}
public void setAdjvex(int adjvex) {
this.adjvex = adjvex;
}
public int getInfo() {
return info;
}
public void setInfo(int info) {
this.info = info;
}
public lineNode getNext() {
return next;
}
public void setNext(lineNode next) {
this.next = next;
}
}
/**
* 事件節點
*/
class vertexNode {
/**
* 節點的名字
*/
private String name;
/**
* 入度
*/
private int in;
/**
* 儲存頂點陣列的下標
*/
private int data;
/**
* 邊的節點的頭指標
*/
private lineNode next;
public int getIn() {
return in;
}
public int getData() {
return data;
}
public lineNode getNext() {
return next;
}
public void setIn(int in) {
this.in = in;
}
public void setData(int data) {
this.data = data;
}
public void setNext(lineNode next) {
this.next = next;
}
public vertexNode( int data, lineNode next, String name) {
this.data = data;
this.next = next;
this.name = name;
}
public vertexNode() {
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
}
public static void main(String[] args) {
lessonWord a=new lessonWord();
a.craeteGraph();
//a.createGraph();
a.criticalPath();
a.DFS(0);
}
}
棧：
package dataproject.stack;
import dataproject.importanRoad.lessonWord;
import java.util.Arrays;
/**
* @author 李正陽17060208112
* @param <E> 泛型
*/
public class myArrayStack<E> {
private int DEFAULT_SIZE = 16;//定義棧的初始預設長度
private int capacity;//儲存順序棧的長度
public int size;//儲存順序棧中元素的個數
private Object[] elementData;//定義一個數組用於儲存順序棧中的元素
public myArrayStack() {
capacity = DEFAULT_SIZE;
elementData = new Object[capacity];
}
//以指定的大小來建立棧
public myArrayStack(int initSize){
capacity = 1;
while(capacity < initSize) {
capacity <<= 1;//將capacity設定成大於initSize的最小2次方
elementData = new Object[capacity];
}
}
//返回當前順序棧中元素的個數
public int length() {
return size;
}
public E pop() {
if(empty()) {
throw new IndexOutOfBoundsException("棧空，不能出棧");
}
E oldValue = (E)elementData[size - 1];
elementData[--size] = null;//讓垃圾回收器及時回收，避免記憶體洩露
return oldValue;
}
public void push(E element) {
ensureCapacity(size + 1);
elementData[size++] = element;
}
private void ensureCapacity(int minCapacity){
if(minCapacity > capacity){
while(capacity < minCapacity) {
capacity <<= 1;
elementData = Arrays.copyOf(elementData, capacity);
}
}
}
//獲取棧頂元素，不會將棧頂元素刪除
public E peek() {
if(size == 0) {
throw new ArrayIndexOutOfBoundsException("棧為空");
}
return (E)elementData[size - 1];
}
/**
* @param d 這個元素的位置
* @return 返回d所處的元素
*/
public E peekTravel(int d) {
if(size == 0) {
throw new ArrayIndexOutOfBoundsException("棧為空");
}
return (E)elementData[d];
}
public boolean empty() {
return size == 0;
}
public void clear() {
for(int i = 0; i < size; i++) {
elementData[i] = null;
}
size = 0;
}
public static void main(String[] args) {
}
}
流程圖：
