小編給大家分享一下java如何查找圖中兩點(diǎn)之間所有路徑,相信大部分人都還不怎么了解,因此分享這篇文章給大家參考一下,希望大家閱讀完這篇文章后大有收獲,下面讓我們一起去了解一下吧!
創(chuàng)新互聯(lián)基于分布式IDC數(shù)據(jù)中心構(gòu)建的平臺(tái)為眾多戶提供成都服務(wù)器托管 四川大帶寬租用 成都機(jī)柜租用 成都服務(wù)器租用。
圖類:
package graph2; import java.util.LinkedList; import graph.Graph.edgeNode; public class Graph { class EdgeNode{ int adjvex; EdgeNode nextEdge; } class VexNode{ int data; EdgeNode firstEdge; boolean isVisted; public boolean isVisted() { return isVisted; } public void setVisted(boolean isVisted) { this.isVisted = isVisted; } } VexNode[] vexsarray ; int[] visited = new int[100]; boolean[] isVisited = new boolean[100]; public void linkLast(EdgeNode target,EdgeNode node) { while (target.nextEdge!=null) { target=target.nextEdge; } target.nextEdge=node; } public int getPosition(int data) { for(int i=0;i<vexsarray.length;i++) { if (data==vexsarray[i].data) { return i; } } return -1; } public void buildGraph(int[] vexs,int[][] edges ) { int vLen = vexs.length; int eLen = edges.length; vexsarray = new VexNode[vLen]; for(int i=0;i<vLen;i++) { vexsarray[i] = new VexNode(); vexsarray[i].data = vexs[i]; vexsarray[i].firstEdge = null; } for(int i=0;i<eLen;i++) { int a = edges[i][0]; int b = edges[i][1]; int start = getPosition(a); int end = getPosition(b); EdgeNode edgeNode = new EdgeNode(); edgeNode.adjvex = end; if (vexsarray[start].firstEdge == null) { vexsarray[start].firstEdge = edgeNode; } else { linkLast(vexsarray[start].firstEdge,edgeNode); } } } public void printGraph() { for(int i=0;i<vexsarray.length;i++) { System.out.printf("%d--",vexsarray[i].data); EdgeNode node = vexsarray[i].firstEdge; while (node!=null) { System.out.printf("%d(%d)--",node.adjvex,vexsarray[node.adjvex].data); node = node.nextEdge; } System.out.println("\n"); } }
算法:
package graph2; import java.util.HashMap; import java.util.Map; import java.util.Stack; import javax.swing.plaf.synth.SynthStyle; import graph2.Graph.EdgeNode; public class FindALlPath { //代表某節(jié)點(diǎn)是否在stack中,避免產(chǎn)生回路 public Map<Integer,Boolean> states=new HashMap(); //存放放入stack中的節(jié)點(diǎn) public Stack<Integer> stack=new Stack(); //打印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()); } //得到x的鄰接點(diǎn)為y的后一個(gè)鄰接點(diǎn)位置,為-1說明沒有找到 public int getNextNode(Graph graph,int x,int y){ int next_node=-1; EdgeNode edge=graph.vexsarray[x].firstEdge; if(null!=edge&&y==-1){ int n=edge.adjvex; //元素還不在stack中 if(!states.get(n)) return n; return -1; } while(null!=edge){ //節(jié)點(diǎn)未訪問 if(edge.adjvex==y){ if(null!=edge.nextEdge){ next_node=edge.nextEdge.adjvex; if(!states.get(next_node)) return next_node; } else return -1; } edge=edge.nextEdge; } return -1; } public void visit(Graph graph,int x,int y){ //初始化所有節(jié)點(diǎn)在stack中的情況 for(int i=0;i<graph.vexsarray.length;i++){ states.put(i,false); } //stack top元素 int top_node; //存放當(dāng)前top元素已經(jīng)訪問過的鄰接點(diǎn),若不存在則置-1,此時(shí)代表訪問該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(); //找到需要訪問的節(jié)點(diǎn) if(top_node==y){ //打印該路徑 printPath(); adjvex_node=stack.pop(); states.put(adjvex_node,false); } else{ //訪問top_node的第advex_node個(gè)鄰接點(diǎn) next_node=getNextNode(graph,top_node,adjvex_node); if(next_node!=-1){ stack.push(next_node); //置當(dāng)前節(jié)點(diǎn)訪問狀態(tài)為已在stack中 states.put(next_node,true); //臨接點(diǎn)重置 adjvex_node=-1; } //不存在臨接點(diǎn),將stack top元素退出 else{ //當(dāng)前已經(jīng)訪問過了top_node的第adjvex_node鄰接點(diǎn) adjvex_node=stack.pop(); //不在stack中 states.put(adjvex_node,false); } } } } }
測(cè)試類:
package graph2; import java.util.Iterator; import graph2.Graph.VexNode; public class Tset2 { public static void main(String[] args) { int[] vexs = {0,1,2,3,4}; int[][] edges = { {0,1}, {0,3}, {1,0}, {1,2}, {2,1}, {2,3}, {2,4}, {3,0}, {3,2}, {3,4}, {4,2}, {4,3}, }; Graph graph = new Graph(); graph.buildGraph(vexs, edges); graph.printGraph(); FindALlPath findALlPath = new FindALlPath(); findALlPath.visit(graph, 4, 0); } }
以上是“java如何查找圖中兩點(diǎn)之間所有路徑”這篇文章的所有內(nèi)容,感謝各位的閱讀!相信大家都有了一定的了解,希望分享的內(nèi)容對(duì)大家有所幫助,如果還想學(xué)習(xí)更多知識(shí),歡迎關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道!
當(dāng)前文章:java如何查找圖中兩點(diǎn)之間所有路徑
標(biāo)題來源:http://redsoil1982.com.cn/article46/ijsihg.html
成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián),為您提供營銷型網(wǎng)站建設(shè)、做網(wǎng)站、網(wǎng)站設(shè)計(jì)、服務(wù)器托管、建站公司、微信小程序
聲明:本網(wǎng)站發(fā)布的內(nèi)容(圖片、視頻和文字)以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主,如果涉及侵權(quán)請(qǐng)盡快告知,我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng),如需處理請(qǐng)聯(lián)系客服。電話:028-86922220;郵箱:631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載,或轉(zhuǎn)載時(shí)需注明來源: 創(chuàng)新互聯(lián)