本文實(shí)例為大家分享了java計(jì)算圖兩點(diǎn)之間的所有路徑的具體代碼，供大家參考，具體內(nèi)容如下
1.給定圖如下:
2.求0到3之間可達(dá)的所有路徑
這里問題就是關(guān)于搜索遍歷的問題,但其中需要注意到不能產(chǎn)生回路或環(huán).
算法描述如下:
top_node:當(dāng)前棧頂元素
adjvex_node;當(dāng)前top_node已經(jīng)訪問的鄰接點(diǎn)
next_node:即將訪問的元素（top_node的第adjvex_node個(gè)鄰接點(diǎn)所對應(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è)還沒有訪問)做入棧標(biāo)記。否則代表沒有后續(xù)節(jié)點(diǎn)了,此時(shí)必須出棧棧頂元素,并置adjvex_node為該棧頂元素,并做出棧標(biāo)記。
④為避免回路，已入棧元素要記錄，選取新入棧頂點(diǎn)時(shí)應(yīng)跳過已入棧的頂點(diǎn),當(dāng)棧為空時(shí)，遍歷完成
3.java代碼實(shí)現(xiàn)
1)圖結(jié)構(gòu)
點(diǎn)表
|
1
2
3
4
5
6
|
public class vertex {//存放點(diǎn)信息public int data;//與該點(diǎn)鄰接的第一個(gè)邊節(jié)點(diǎn)public edge firstedge;} |
邊表(代表與點(diǎn)相連的點(diǎn)的集合)
|
1
2
3
4
5
6
7
8
9
10
|
//邊節(jié)點(diǎn)public class edge {//對應(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)
|
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
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
|
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; }}//針對x節(jié)點(diǎn)添加邊節(jié)點(diǎn)ypublic 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說明沒有找到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)未訪問 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)訪問過的鄰接點(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(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); } } }} //打印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
以上就是本文的全部內(nèi)容，希望對大家的學(xué)習(xí)有所幫助，也希望大家多多支持服務(wù)器之家。
原文鏈接：https://blog.csdn.net/xqhadoop/article/details/66476728
