java中怎么計(jì)算圖兩點(diǎn)之間的所有路徑

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

1.給定圖如下:

2.求0到3之間可達(dá)的所有路徑

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

算法描述如下:

top_node:當(dāng)前棧頂元素

adjvex_node;當(dāng)前top_node已經(jīng)訪問(wèn)的鄰接點(diǎn)

next_node:即將訪問(wèn)的元素（top_node的第adjvex_node個(gè)鄰接點(diǎn)所對(duì)應(yīng)的元素）

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

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

①源點(diǎn)先入棧，并進(jìn)行標(biāo)記

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

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

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

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

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

點(diǎn)表

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

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

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

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

import java.util.HashMap;
import java.util.Map;
import java.util.Stack;
public class graph {
public Vertex[] vertexList; //存放點(diǎn)的集合
public graph(int vertexNum){
 this.vertexNum=vertexNum;
 vertexList=new Vertex[vertexNum];
}
//點(diǎn)個(gè)數(shù)
public int vertexNum;
//邊個(gè)數(shù)
public int edgeLength;
public void initVertext(int datas[]){
 for(int i=0;i<vertexNum;i++){
 Vertex vertext=new Vertex();
 vertext.data=datas[i];
 vertext.firstEdge=null;
 vertexList[i]=vertext;
 //System.out.println("i"+vertexList[i]);
 }
 isVisited=new boolean[vertexNum];
 for(int i=0;i<isVisited.length;i++){
 isVisited[i]=false;
 }
}
//針對(duì)x節(jié)點(diǎn)添加邊節(jié)點(diǎn)y
public void addEdge(int x,int y,int weight){
 Edge edge=new Edge();
 edge.setVertexId(y);
 edge.setWeight(weight);
 //第一個(gè)邊節(jié)點(diǎn)
 System.out.println(vertexList.length);
 if(null==vertexList[x].firstEdge){
 vertexList[x].firstEdge=edge;
 edge.setNext(null);
 }
 //不是第一個(gè)邊節(jié)點(diǎn),則采用頭插法
 else{
 edge.next=vertexList[x].firstEdge;
 vertexList[x].firstEdge=edge;
 }
}
//得到x的鄰接點(diǎn)為y的后一個(gè)鄰接點(diǎn)位置,為-1說(shuō)明沒(méi)有找到
public int getNextNode(int x,int y){
 int next_node=-1;
 Edge edge=vertexList[x].firstEdge;
 if(null!=edge&&y==-1){
 int n=edge.vertexId;
 //元素還不在stack中
 if(!states.get(n))
  return n;
 return -1;
 }
 
 while(null!=edge){
 //節(jié)點(diǎn)未訪問(wèn)
 if(edge.vertexId==y){
  if(null!=edge.next){
   next_node=edge.next.vertexId;
  if(!states.get(next_node))
  return next_node;
  }
  else
  return -1;
 }
 edge=edge.next;
 }
 return -1;
}
//代表某節(jié)點(diǎn)是否在stack中,避免產(chǎn)生回路
public Map<Integer,Boolean> states=new HashMap();
 
//存放放入stack中的節(jié)點(diǎn)
public Stack<Integer> stack=new Stack();
 
//輸出2個(gè)節(jié)點(diǎn)之間的輸出路徑
public void visit(int x,int y){
    //初始化所有節(jié)點(diǎn)在stack中的情況
    for(int i=0;i<vertexNum;i++){
 states.put(i,false);
 }
    //stack top元素
    int top_node;
 //存放當(dāng)前top元素已經(jīng)訪問(wèn)過(guò)的鄰接點(diǎn),若不存在則置-1,此時(shí)代表訪問(wèn)該top元素的第一個(gè)鄰接點(diǎn)
    int adjvex_node=-1;
 int next_node;
 stack.add(x);
 states.put(x,true);
 while(!stack.isEmpty()){
 top_node=stack.peek();
 //找到需要訪問(wèn)的節(jié)點(diǎn)
        if(top_node==y){
  //打印該路徑
  printPath();
  adjvex_node=stack.pop();
  states.put(adjvex_node,false);
 }
 else{
  //訪問(wèn)top_node的第advex_node個(gè)鄰接點(diǎn)
            next_node=getNextNode(top_node,adjvex_node);
  if(next_node!=-1){
  stack.push(next_node);
  //置當(dāng)前節(jié)點(diǎn)訪問(wèn)狀態(tài)為已在stack中
                states.put(next_node,true);
  //臨接點(diǎn)重置
                adjvex_node=-1;
  }
            //不存在臨接點(diǎn)，將stack top元素退出 
            else{
  //當(dāng)前已經(jīng)訪問(wèn)過(guò)了top_node的第adjvex_node鄰接點(diǎn)
                adjvex_node=stack.pop();
  //不在stack中
  states.put(adjvex_node,false);
  }
 }
 }
}
 
//打印stack中信息,即路徑信息
 public void printPath(){
 StringBuilder sb=new StringBuilder();
 for(Integer i :stack){
 sb.append(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中怎么計(jì)算圖兩點(diǎn)之間的所有路徑問(wèn)題的解答就分享到這里了，希望以上內(nèi)容可以對(duì)大家有一定的幫助，如果你還有很多疑惑沒(méi)有解開(kāi)，可以關(guān)注億速云行業(yè)資訊頻道了解更多相關(guān)知識(shí)。