之前就這個問題發(fā)帖求教過，過了幾天沒看到回復(fù)就沒再關(guān)心。后來自己設(shè)計了一個算法，在公司的項目中實踐了一下，效果還可以，貼出來供大家參考。
算法要求：
1. 在一個無向連通圖中求出兩個給定點之間的所有路徑；
2. 在所得路徑上不能含有環(huán)路或重復(fù)的點；
算法思想描述：
1. 整理節(jié)點間的關(guān)系，為每個節(jié)點建立一個集合，該集合中保存所有與該節(jié)點直接相連的節(jié)點（不包括該節(jié)點自身）；
2. 定義兩點一個為起始節(jié)點，另一個為終點，求解兩者之間的所有路徑的問題可以被分解為如下所述的子問題：對每一個與起始節(jié)點直接相連的節(jié)點，求解它到終點的所有路徑（路徑上不包括起始節(jié)點）得到一個路徑集合，將這些路徑集合相加就可以得到起始節(jié)點到終點的所有路徑；依次類推就可以應(yīng)用遞歸的思想，層層遞歸直到終點，若發(fā)現(xiàn)希望得到的一條路徑，則轉(zhuǎn)儲并打印輸出；若發(fā)現(xiàn)環(huán)路，或發(fā)現(xiàn)死路，則停止尋路并返回；
3. 用棧保存當(dāng)前已經(jīng)尋到的路徑（不是完整路徑）上的節(jié)點，在每一次尋到完整路徑時彈出棧頂節(jié)點；而在遇到從棧頂節(jié)點無法繼續(xù)向下尋路時也彈出該棧頂節(jié)點，從而實現(xiàn)回溯。
算法偽碼(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
|
public stack stack = new stack();/*臨時保存路徑節(jié)點的棧*/public arraylist sers = new arraylist();/*存儲路徑的集合*/public class node/*表示一個節(jié)點以及和這個節(jié)點相連的所有節(jié)點*/ { public string name = null; public arraylist relationnodes = new arraylist(); public string getname() { return name; } public void setname(string name) { this.name = name; } public arraylist getrelationnodes() { return relationnodes; } public void setrelationnodes(arraylist relationnodes) { this.relationnodes = relationnodes; } }public boolean isnodeinstack(node node)/*判斷節(jié)點是否在棧中*/ { iterator it = stack.iterator(); while(it.hasnext()) { node node1 = (node)it.next(); if(node == node1) return true; } return false; }public void showandsavepath ()/*此時棧中的節(jié)點組成一條所求路徑，轉(zhuǎn)儲并打印輸出*/ { object[] o = stack.toarray(); for(int i = 0;i<o.length;i++) { system.out.print(o[i]); } sers.add(o); /*轉(zhuǎn)儲*/ system.out.println("\n"); }/*尋找路徑的方法*/public boolean getpaths(node cnode, node pnode, node snode, node enode)/*cnode表示當(dāng)前的起始節(jié)點currentnode，pnode表示當(dāng)前起始節(jié)點的上一節(jié)點previousnode，snode表示最初的起始節(jié)點startnode，enode表示終點endnode*/ { node nnode = null; if(cnode != null && pnode != null && cnode == pnode) return false;/*如果符合條件判斷說明出現(xiàn)環(huán)路，不能再順著該路徑繼續(xù)尋路，返回false*/ if(cnode != null) { int i = 0; stack.push(cnode);/*起始節(jié)點入棧*/ if(cnode == enode)/*如果該起始節(jié)點就是終點，說明找到一條路徑*/ { showandsavepath();/*轉(zhuǎn)儲并打印輸出該路徑，返回true*/ return true; } else/*如果不是,繼續(xù)尋路*/ { nnode = cnode.getrelationnodes().get(i);/*從與當(dāng)前起始節(jié)點cnode有連接關(guān)系的節(jié)點集中按順序遍歷得到一個節(jié)點作為下一次遞歸尋路時的起始節(jié)點*/ while(nnode != null) { if(pnode != null && (nnode == snode || nnode == pnode || isnodeinstack(nnode)))/*如果nnode是最初的起始節(jié)點或者nnode就是cnode的上一節(jié)點或者nnode已經(jīng)在棧中，說明產(chǎn)生環(huán)路，應(yīng)重新在與當(dāng)前起始節(jié)點有連接關(guān)系的節(jié)點集中尋找nnode*/ { i++; if(i>=cnode.getrelationnodes().size()) nnode = null; else nnode = cnode.getrelationnodes().get(i); continue; }/*以nnode為新的起始節(jié)點，當(dāng)前起始節(jié)點cnode為上一節(jié)點，遞歸調(diào)用尋路方法*/ if(getpaths(nnode, cnode, snode, enode))/*遞歸調(diào)用*/ { stack.pop();/*如果找到一條路徑，則彈出棧頂節(jié)點*/ } i++;/*繼續(xù)在與cnode有連接關(guān)系的節(jié)點集中測試nnode*/ if(i>=cnode.getrelationnodes().size()) nnode = null; else nnode = cnode.getrelationnodes().get(i); } stack.pop();/*當(dāng)遍歷完所有與cnode有連接關(guān)系的節(jié)點后，說明在以cnode為起始節(jié)點到終點的路徑已經(jīng)全部找到*/ return false; } } else return false;} |
以上就是本文的全部內(nèi)容，希望對大家的學(xué)習(xí)有所幫助，也希望大家多多支持服務(wù)器之家。
