參考 java查找無(wú)向連通圖中兩點(diǎn)間所有路徑的算法，對(duì)代碼進(jìn)行了部分修改，并編寫(xiě)了測(cè)試用例。
算法要求：
1. 在一個(gè)無(wú)向連通圖中求出兩個(gè)給定點(diǎn)之間的所有路徑；
2. 在所得路徑上不能含有環(huán)路或重復(fù)的點(diǎn)；
算法思想描述：
1. 整理節(jié)點(diǎn)間的關(guān)系，為每個(gè)節(jié)點(diǎn)建立一個(gè)集合，該集合中保存所有與該節(jié)點(diǎn)直接相連的節(jié)點(diǎn)（不包括該節(jié)點(diǎn)自身）；
2. 定義兩點(diǎn)一個(gè)為起始節(jié)點(diǎn)，另一個(gè)為終點(diǎn)，求解兩者之間的所有路徑的問(wèn)題可以被分解為如下所述的子問(wèn)題：對(duì)每一 個(gè)與起始節(jié)點(diǎn)直接相連的節(jié)點(diǎn)，求解它到終點(diǎn)的所有路徑（路徑上不包括起始節(jié)點(diǎn)）得到一個(gè)路徑集合，將這些路徑集合相加就可以得到起始節(jié)點(diǎn)到終點(diǎn)的所有路徑；依次類(lèi)推就可以應(yīng)用遞歸的思想，層層遞歸直到終點(diǎn)，若發(fā)現(xiàn)希望得到的一條路徑，則轉(zhuǎn)儲(chǔ)并打印輸出；若發(fā)現(xiàn)環(huán)路，或發(fā)現(xiàn)死路，則停止尋路并返回；
3. 用棧保存當(dāng)前已經(jīng)尋到的路徑（不是完整路徑）上的節(jié)點(diǎn)，在每一次尋到完整路徑時(shí)彈出棧頂節(jié)點(diǎn)；而在遇到從棧頂節(jié)點(diǎn)無(wú)法繼續(xù)向下尋路時(shí)也彈出該棧頂節(jié)點(diǎn)，從而實(shí)現(xiàn)回溯。
實(shí)現(xiàn)代碼
1.node.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
|
import java.util.arraylist; /* 表示一個(gè)節(jié)點(diǎn)以及和這個(gè)節(jié)點(diǎn)相連的所有節(jié)點(diǎn) */public class node{ public string name = null; public arraylist<node> relationnodes = new arraylist<node>(); public string getname() { return name; } public void setname(string name) { this.name = name; } public arraylist<node> getrelationnodes() { return relationnodes; } public void setrelationnodes(arraylist<node> relationnodes) { this.relationnodes = relationnodes; }} |
2.test.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
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
144
145
146
147
|
import java.util.arraylist;import java.util.iterator;import java.util.stack; public class test { /* 臨時(shí)保存路徑節(jié)點(diǎn)的棧 */ public static stack<node> stack = new stack<node>(); /* 存儲(chǔ)路徑的集合 */ public static arraylist<object[]> sers = new arraylist<object[]>(); /* 判斷節(jié)點(diǎn)是否在棧中 */ public static boolean isnodeinstack(node node) { iterator<node> it = stack.iterator(); while (it.hasnext()) { node node1 = (node) it.next(); if (node == node1) return true; } return false; } /* 此時(shí)棧中的節(jié)點(diǎn)組成一條所求路徑，轉(zhuǎn)儲(chǔ)并打印輸出 */ public static void showandsavepath() { object[] o = stack.toarray(); for (int i = 0; i < o.length; i++) { node nnode = (node) o[i]; if(i < (o.length - 1)) system.out.print(nnode.getname() + "->"); else system.out.print(nnode.getname()); } sers.add(o); /* 轉(zhuǎn)儲(chǔ) */ system.out.println("\n"); } /* * 尋找路徑的方法 * cnode: 當(dāng)前的起始節(jié)點(diǎn)currentnode * pnode: 當(dāng)前起始節(jié)點(diǎn)的上一節(jié)點(diǎn)previousnode * snode: 最初的起始節(jié)點(diǎn)startnode * enode: 終點(diǎn)endnode */ public static boolean getpaths(node cnode, node pnode, node snode, node enode) { node nnode = null; /* 如果符合條件判斷說(shuō)明出現(xiàn)環(huán)路，不能再順著該路徑繼續(xù)尋路，返回false */ if (cnode != null && pnode != null && cnode == pnode) return false; if (cnode != null) { int i = 0; /* 起始節(jié)點(diǎn)入棧 */ stack.push(cnode); /* 如果該起始節(jié)點(diǎn)就是終點(diǎn)，說(shuō)明找到一條路徑 */ if (cnode == enode) { /* 轉(zhuǎn)儲(chǔ)并打印輸出該路徑，返回true */ showandsavepath(); return true; } /* 如果不是,繼續(xù)尋路 */ else { /* * 從與當(dāng)前起始節(jié)點(diǎn)cnode有連接關(guān)系的節(jié)點(diǎn)集中按順序遍歷得到一個(gè)節(jié)點(diǎn) * 作為下一次遞歸尋路時(shí)的起始節(jié)點(diǎn) */ nnode = cnode.getrelationnodes().get(i); while (nnode != null) { /* * 如果nnode是最初的起始節(jié)點(diǎn)或者nnode就是cnode的上一節(jié)點(diǎn)或者nnode已經(jīng)在棧中 ， * 說(shuō)明產(chǎn)生環(huán)路 ，應(yīng)重新在與當(dāng)前起始節(jié)點(diǎn)有連接關(guān)系的節(jié)點(diǎn)集中尋找nnode */ if (pnode != null && (nnode == snode || nnode == pnode || isnodeinstack(nnode))) { i++; if (i >= cnode.getrelationnodes().size()) nnode = null; else nnode = cnode.getrelationnodes().get(i); continue; } /* 以nnode為新的起始節(jié)點(diǎn)，當(dāng)前起始節(jié)點(diǎn)cnode為上一節(jié)點(diǎn)，遞歸調(diào)用尋路方法 */ if (getpaths(nnode, cnode, snode, enode))/* 遞歸調(diào)用 */ { /* 如果找到一條路徑，則彈出棧頂節(jié)點(diǎn) */ stack.pop(); } /* 繼續(xù)在與cnode有連接關(guān)系的節(jié)點(diǎn)集中測(cè)試nnode */ i++; if (i >= cnode.getrelationnodes().size()) nnode = null; else nnode = cnode.getrelationnodes().get(i); } /* * 當(dāng)遍歷完所有與cnode有連接關(guān)系的節(jié)點(diǎn)后， * 說(shuō)明在以cnode為起始節(jié)點(diǎn)到終點(diǎn)的路徑已經(jīng)全部找到 */ stack.pop(); return false; } } else return false; } public static void main(string[] args) { /* 定義節(jié)點(diǎn)關(guān)系 */ int noderalation[][] = { {1}, //0 {0,5,2,3},//1 {1,4}, //2 {1,4}, //3 {2,3,5}, //4 {1,4} //5 }; /* 定義節(jié)點(diǎn)數(shù)組 */ node[] node = new node[noderalation.length]; for(int i=0;i<noderalation.length;i++) { node[i] = new node(); node[i].setname("node" + i); } /* 定義與節(jié)點(diǎn)相關(guān)聯(lián)的節(jié)點(diǎn)集合 */ for(int i=0;i<noderalation.length;i++) { arraylist<node> list = new arraylist<node>(); for(int j=0;j<noderalation[i].length;j++) { list.add(node[noderalation[i][j]]); } node[i].setrelationnodes(list); list = null; //釋放內(nèi)存 } /* 開(kāi)始搜索所有路徑 */ getpaths(node[0], null, node[0], node[4]); }} |
輸出：
node0->node1->node5->node4
node0->node1->node2->node4
node0->node1->node3->node4
以上就是本文的全部?jī)?nèi)容，希望對(duì)大家的學(xué)習(xí)有所幫助，也希望大家多多支持服務(wù)器之家。
原文鏈接：https://blog.csdn.net/hcx25909/article/details/8043107
