本文实例为大家分享了java查找图中两点之间所有路径的具体代码，基于邻接表，供大家参考，具体内容如下
图类：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 |
package graph1;
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" ); } } |
算法：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 |
package graph1;
import java.util.hashmap; import java.util.map; import java.util.stack;
import javax.swing.plaf.synth.synthstyle;
import graph1.graph.edgenode;
public class findallpath {
//代表某节点是否在stack中,避免产生回路 public map<integer, boolean > states= new hashmap();
//存放放入stack中的节点 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的邻接点为y的后一个邻接点位置,为-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){ //节点未访问 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){ //初始化所有节点在stack中的情况 for ( int i= 0 ;i<graph.vexsarray.length;i++){ states.put(i, false ); } //stack top元素 int top_node; //存放当前top元素已经访问过的邻接点,若不存在则置-1,此时代表访问该top元素的第一个邻接点 int adjvex_node=- 1 ; int next_node; stack.add(x); states.put(x, true );
while (!stack.isempty()){ top_node=stack.peek(); //找到需要访问的节点 if (top_node==y){ //打印该路径 printpath(); adjvex_node=stack.pop(); states.put(adjvex_node, false ); } else { //访问top_node的第advex_node个邻接点 next_node=getnextnode(graph,top_node,adjvex_node); if (next_node!=- 1 ){ stack.push(next_node); //置当前节点访问状态为已在stack中 states.put(next_node, true ); //临接点重置 adjvex_node=- 1 ; } //不存在临接点，将stack top元素退出 else { //当前已经访问过了top_node的第adjvex_node邻接点 adjvex_node=stack.pop(); //不在stack中 states.put(adjvex_node, false ); } } } }
} |
测试类：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 |
package graph1;
import java.util.iterator;
import graph1.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 );
}
} |
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持。
原文链接：https://blog.csdn.net/Coder_py/article/details/72542898
查看更多关于java查找图中两点之间所有路径的详细内容...