本文實例為大家分享了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
