java中怎么計算圖兩點之間的所有路徑？針對這個問題，這篇文章詳細介紹了相對應(yīng)的分析和解答，希望可以幫助更多想解決這個問題的小伙伴找到更簡單易行的方法。

興安網(wǎng)站制作公司哪家好，找創(chuàng)新互聯(lián)！從網(wǎng)頁設(shè)計、網(wǎng)站建設(shè)、微信開發(fā)、APP開發(fā)、響應(yīng)式網(wǎng)站開發(fā)等網(wǎng)站項目制作，到程序開發(fā)，運營維護。創(chuàng)新互聯(lián)成立于2013年到現(xiàn)在10年的時間，我們擁有了豐富的建站經(jīng)驗和運維經(jīng)驗，來保證我們的工作的順利進行。專注于網(wǎng)站建設(shè)就選創(chuàng)新互聯(lián)。

1.給定圖如下:

2.求0到3之間可達的所有路徑

這里問題就是關(guān)于搜索遍歷的問題,但其中需要注意到不能產(chǎn)生回路或環(huán).

算法描述如下:

top_node:當前棧頂元素

adjvex_node;當前top_node已經(jīng)訪問的鄰接點

next_node:即將訪問的元素（top_node的第adjvex_node個鄰接點所對應(yīng)的元素）

找出所有路徑采用的是遍歷的方法，以“深度優(yōu)先”算法為基礎(chǔ)。從源點出發(fā)，先到源點的第一個鄰接點N00，再到N00的第一個鄰接點N10，再到N10的第一個鄰接點N20...當遍歷到目標點時表明找到一條路徑。

上述代碼的核心數(shù)據(jù)結(jié)構(gòu)為一個棧，主要步驟：

①源點先入棧，并進行標記

②獲取棧頂元素top_node，如果棧頂為終點時，即找到一條路徑,棧頂元素top_node出棧，此時adjvex_node=top_node,新的棧頂元素為top_node，否則執(zhí)行③

③從top_node的所有鄰接點中，從adjvex_node為起點，選取下一個鄰接點next_node；如果該元素非空,則入棧,使得adjvex_node=-1,(adjvex_node=-1代表top_node的鄰接點一個還沒有訪問)做入棧標記。否則代表沒有后續(xù)節(jié)點了,此時必須出棧棧頂元素,并置adjvex_node為該棧頂元素,并做出棧標記。

④為避免回路，已入棧元素要記錄，選取新入棧頂點時應(yīng)跳過已入棧的頂點,當棧為空時，遍歷完成

3.java代碼實現(xiàn)

1)圖結(jié)構(gòu)

點表

public class Vertex {
//存放點信息
public int data;
//與該點鄰接的第一個邊節(jié)點
public Edge firstEdge;
}

邊表(代表與點相連的點的集合)

//邊節(jié)點
public class Edge {
//對應(yīng)的點下表
public int vertexId;
//邊的權(quán)重
public int weight;
//下一個邊節(jié)點
public Edge next;
//getter and setter自行補充
}

2).算法實現(xiàn)

import java.util.HashMap;
import java.util.Map;
import java.util.Stack;
public class graph {
public Vertex[] vertexList; //存放點的集合
public graph(int vertexNum){
 this.vertexNum=vertexNum;
 vertexList=new Vertex[vertexNum];
}
//點個數(shù)
public int vertexNum;
//邊個數(shù)
public int edgeLength;
public void initVertext(int datas[]){
 for(int i=0;i states=new HashMap();
 
//存放放入stack中的節(jié)點
public Stack stack=new Stack();
 
//輸出2個節(jié)點之間的輸出路徑
public void visit(int x,int y){
    //初始化所有節(jié)點在stack中的情況
    for(int i=0;i");
 }
 sb.delete(sb.length()-2,sb.length());
 System.out.println(sb.toString());
}
 
public static void main(String[]args){
 graph g=new graph(5);
 g.initVertext(new int[]{1,2,3,4,4});
 //System.out.println(g.vertexList[0]);
 g.addEdge(0,1,1);
 g.addEdge(0,2,3);
 g.addEdge(0,3,4);
 g.addEdge(1,2,1);
 g.addEdge(2,0,1);
 g.addEdge(2,3,1);
 g.addEdge(1,3,2);
 g.visit(0,3);
}
}

執(zhí)行結(jié)果如下:

0->3
0->2->3
0->1->2->3 

關(guān)于java中怎么計算圖兩點之間的所有路徑問題的解答就分享到這里了，希望以上內(nèi)容可以對大家有一定的幫助，如果你還有很多疑惑沒有解開，可以關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道了解更多相關(guān)知識。