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