参考 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
