Graph Algorithm To Find All Connections Between Two Arbitrary Vertices
我试图确定最佳的时间效率算法来完成下面描述的任务。
我有一套记录。对于这组记录，我具有连接数据，该数据指示该组记录中的记录对如何相互连接。这基本上代表了一个无向图，记录是顶点，连接数据是边。
集合中的所有记录都具有连接信息(即不存在孤立记录；集合中的每个记录都连接到集合中的一个或多个其他记录)。
我想从集合中选择任意两个记录，并能够显示所选记录之间的所有简单路径。"简单路径"是指在路径中没有重复记录的路径(即仅有限路径)。
注意：两个选定的记录将始终是不同的(即开始和结束顶点永远不会相同；没有周期)。
例如：
1
2
3
4
5
6
7
8
| If I have the following records:
A, B, C, D, E
and the following represents the connections:
(A,B),(A,C),(B,A),(B,D),(B,E),(B,F),(C,A),(C,E),
(C,F),(D,B),(E,C),(E,F),(F,B),(F,C),(F,E)
[where (A,B) means record A connects to record B] |
如果我选择B作为我的开始记录，选择E作为我的结束记录，我将希望找到通过记录连接将记录B连接到记录E的所有简单路径。
1
2
3
4
5
6
| All paths connecting B to E:
B->E
B->F->E
B->F->C->E
B->A->C->E
B->A->C->F->E |
这是一个例子，实际上我可能有包含数十万条记录的集合。
似乎可以通过对图形进行深度优先搜索来完成。深度优先搜索将找到两个节点之间的所有非循环路径。该算法应该非常快，并且可以扩展到大型图形(图形数据结构稀疏，因此仅使用所需的内存)。
我注意到您在上面指定的图形只有一个方向(B，E)的边。这是错字还是真的有向图？此解决方案不管如何。抱歉，我无法使用C语言完成此操作，在该领域我有点虚弱。我希望您能够翻译此Java代码而不会遇到太多麻烦。
Graph.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
| import java.util.HashMap;
import java.util.LinkedHashSet;
import java.util.LinkedList;
import java.util.Map;
import java.util.Set;
public class Graph {
private Map<String, LinkedHashSet<String>> map = new HashMap();
public void addEdge(String node1, String node2) {
LinkedHashSet<String> adjacent = map.get(node1);
if(adjacent==null) {
adjacent = new LinkedHashSet();
map.put(node1, adjacent);
}
adjacent.add(node2);
}
public void addTwoWayVertex(String node1, String node2) {
addEdge(node1, node2);
addEdge(node2, node1);
}
public boolean isConnected(String node1, String node2) {
Set adjacent = map.get(node1);
if(adjacent==null) {
return false;
}
return adjacent.contains(node2);
}
public LinkedList<String> adjacentNodes(String last) {
LinkedHashSet<String> adjacent = map.get(last);
if(adjacent==null) {
return new LinkedList();
}
return new LinkedList<String>(adjacent);
}
} |
Search.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
| import java.util.LinkedList;
public class Search {
private static final String START ="B";
private static final String END ="E";
public static void main(String[] args) {
// this graph is directional
Graph graph = new Graph();
graph.addEdge("A","B");
graph.addEdge("A","C");
graph.addEdge("B","A");
graph.addEdge("B","D");
graph.addEdge("B","E"); // this is the only one-way connection
graph.addEdge("B","F");
graph.addEdge("C","A");
graph.addEdge("C","E");
graph.addEdge("C","F");
graph.addEdge("D","B");
graph.addEdge("E","C");
graph.addEdge("E","F");
graph.addEdge("F","B");
graph.addEdge("F","C");
graph.addEdge("F","E");
LinkedList<String> visited = new LinkedList();
visited.add(START);
new Search().depthFirst(graph, visited);
}
private void depthFirst(Graph graph, LinkedList<String> visited) {
LinkedList<String> nodes = graph.adjacentNodes(visited.getLast());
// examine adjacent nodes
for (String node : nodes) {
if (visited.contains(node)) {
continue;
}
if (node.equals(END)) {
visited.add(node);
printPath(visited);
visited.removeLast();
break;
}
}
for (String node : nodes) {
if (visited.contains(node) || node.equals(END)) {
continue;
}
visited.addLast(node);
depthFirst(graph, visited);
visited.removeLast();
}
}
private void printPath(LinkedList<String> visited) {
for (String node : visited) {
System.out.print(node);
System.out.print("");
}
System.out.println();
}
} |
程序输出：
1
2
3
4
5
| B E
B A C E
B A C F E
B F E
B F C E |
美国国家标准技术研究院(NIST)在线算法和数据结构词典将该问题列为"所有简单路径"，并建议进行深度优先搜索。 CLRS提供了相关的算法。
使用Petri Nets的巧妙技巧可在此处找到
这是我想出的伪代码。这不是任何特定的伪代码方言，但应足够简单以遵循。
任何人都想分开。
-
是代表当前路径的顶点列表。
-
[x]是符合条件的路径列表
-
▼显示是源顶点
-
[d]是目标顶点
-
是当前顶点(PathFind例程的参数)
假设有一种查找相邻顶点的有效方法(第6行)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| 1 PathList [p]
2 ListOfPathLists [x]
3 Vertex [s], [d]
4 PathFind ( Vertex [c] )
5 Add [c] to tail end of list [p]
6 For each Vertex [v] adjacent to [c]
7 If [v] is equal to [d] then
8 Save list [p] in [x]
9 Else If [v] is not in list [p]
10 PathFind([v])
11 Next For
12 Remove tail from [p]
13 Return |
由于此答案中给出的现有非递归DFS实现似乎已失效，因此让我提供一个实际可行的方法。
我已经用Python编写了此代码，因为我发现它非常易读并且不受实现细节的干扰(并且因为它具有用于实现生成器的便捷yield关键字)，但是移植到其他语言应该相当容易。
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
| # a generator function to find all simple paths between two nodes in a
# graph, represented as a dictionary that maps nodes to their neighbors
def find_simple_paths(graph, start, end):
visited = set()
visited.add(start)
nodestack = list()
indexstack = list()
current = start
i = 0
while True:
# get a list of the neighbors of the current node
neighbors = graph[current]
# find the next unvisited neighbor of this node, if any
while i < len(neighbors) and neighbors[i] in visited: i += 1
if i >= len(neighbors):
# we've reached the last neighbor of this node, backtrack
visited.remove(current)
if len(nodestack) < 1: break # can't backtrack, stop!
current = nodestack.pop()
i = indexstack.pop()
elif neighbors[i] == end:
# yay, we found the target node! let the caller process the path
yield nodestack + [current, end]
i += 1
else:
# push current node and index onto stacks, switch to neighbor
nodestack.append(current)
indexstack.append(i+1)
visited.add(neighbors[i])
current = neighbors[i]
i = 0 |
此代码维护两个并行堆栈：一个包含当前路径中的较早节点，一个包含该节点堆栈中每个节点的当前邻居索引(以便我们在弹出节点时可以继续遍历节点的邻居)堆栈)。我本来可以很好地使用(节点，索引)对的单个堆栈，但是我认为双堆栈方法更具可读性，并且对于其他语言的用户来说可能更易于实现。
该代码还使用了一个单独的visited集，该集始终包含当前节点和堆栈上的所有节点，以让我有效地检查节点是否已成为当前路径的一部分。如果您的语言碰巧有一个"有序集"数据结构，该结构既提供了有效的类似于堆栈的推/弹出操作，又提供了有效的成员资格查询，则可以将其用于节点堆栈，并摆脱单独的visited集。
或者，如果对节点使用自定义可变类/结构，则只需在每个节点中存储一个布尔值标志，以指示是否已将其作为当前搜索路径的一部分进行了访问。当然，如果您出于某种原因希望这样做，则该方法将不允许您在同一图形上并行运行两个搜索。
这是一些测试代码，展示了上面给出的功能如何工作：
1
2
3
4
5
6
7
8
9
10
11
12
13
| # test graph:
# ,---B---.
# A | D
# `---C---'
graph = {
"A": ("B","C"),
"B": ("A","C","D"),
"C": ("A","B","D"),
"D": ("B","C"),
}
# find paths from A to D
for path in find_simple_paths(graph,"A","D"): print" ->".join(path) |
在给定的示例图上运行此代码将产生以下输出：
1
2
3
4
| A -> B -> C -> D
A -> B -> D
A -> C -> B -> D
A -> C -> D |
请注意，尽管此示例图是无向的(即，其所有边沿都是双向的)，但该算法也适用于任意有向图。例如，删除C -> B边(通过从C的邻居列表中删除B)将产生相同的输出，但第三条路径(A -> C -> B -> D)不再可用。
PS。构造图很容易，对于这种图来说，像这样的简单搜索算法(以及该线程中给出的其他算法)的性能非常差。
例如，考虑在无向图上查找从A到B的所有路径的任务，其中起始节点A有两个邻居：目标节点B(除A之外没有其他邻居)和节点C(属于集团)的n + 1个节点，如下所示：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| graph = {
"A": ("B","C"),
"B": ("A"),
"C": ("A","D","E","F","G","H","I","J","K","L","M","N","O"),
"D": ("C","E","F","G","H","I","J","K","L","M","N","O"),
"E": ("C","D","F","G","H","I","J","K","L","M","N","O"),
"F": ("C","D","E","G","H","I","J","K","L","M","N","O"),
"G": ("C","D","E","F","H","I","J","K","L","M","N","O"),
"H": ("C","D","E","F","G","I","J","K","L","M","N","O"),
"I": ("C","D","E","F","G","H","J","K","L","M","N","O"),
"J": ("C","D","E","F","G","H","I","K","L","M","N","O"),
"K": ("C","D","E","F","G","H","I","J","L","M","N","O"),
"L": ("C","D","E","F","G","H","I","J","K","M","N","O"),
"M": ("C","D","E","F","G","H","I","J","K","L","N","O"),
"N": ("C","D","E","F","G","H","I","J","K","L","M","O"),
"O": ("C","D","E","F","G","H","I","J","K","L","M","N"),
} |
显而易见，A和B之间的唯一路径是直接路径，但是从节点A开始的简单DFS会浪费O(n！)时间，无益地探索集团内部的路径，即使这对人类来说是显而易见的)这些路径都不可能导致B。
也可以构建具有类似特性的DAG，例如通过使起始节点A连接目标节点B和两个其他节点C 1 和C 2 ，这两个节点都连接到节点D 1 和D 2 ，它们都连接到E 1 和E 2 ，依此类推。对于这样排列的n层节点，简单地搜索从A到B的所有路径将最终浪费O(2n)时间，在放弃之前检查所有可能的死角。
当然，从集团中的一个节点(不是C)或从DAG的最后一层向目标节点B添加一条边，将会创建从A到B的大量可能的路径，并且纯粹的本地搜索算法无法真正预先告知是否会找到这样的边缘。因此，从某种意义上说，这种简单搜索的输出敏感性差是由于它们对图形的全局结构缺乏了解。
尽管可以使用多种预处理方法(例如迭代地消除叶节点，搜索单节点顶点分隔符等)来避免这些"指数时间死胡同"，但是我不知道任何一般的方法可以在所有情况下消除它们的预处理技巧。通用的解决方案是在搜索的每个步骤中检查目标节点是否仍然可以访问(使用子搜索)，如果不是，请尽早回溯，否则会大大降低搜索速度(最糟糕的是，对于不包含此类病理性死角的许多图，则按比例与图的大小成比例。
好。
与第二层相比，这是一个逻辑上更好看的递归版本。
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
| public class Search {
private static final String START ="B";
private static final String END ="E";
public static void main(String[] args) {
// this graph is directional
Graph graph = new Graph();
graph.addEdge("A","B");
graph.addEdge("A","C");
graph.addEdge("B","A");
graph.addEdge("B","D");
graph.addEdge("B","E"); // this is the only one-way connection
graph.addEdge("B","F");
graph.addEdge("C","A");
graph.addEdge("C","E");
graph.addEdge("C","F");
graph.addEdge("D","B");
graph.addEdge("E","C");
graph.addEdge("E","F");
graph.addEdge("F","B");
graph.addEdge("F","C");
graph.addEdge("F","E");
List<ArrayList<String>> paths = new ArrayList<ArrayList<String>>();
String currentNode = START;
List<String> visited = new ArrayList<String>();
visited.add(START);
new Search().findAllPaths(graph, seen, paths, currentNode);
for(ArrayList<String> path : paths){
for (String node : path) {
System.out.print(node);
System.out.print("");
}
System.out.println();
}
}
private void findAllPaths(Graph graph, List<String> visited, List<ArrayList<String>> paths, String currentNode) {
if (currentNode.equals(END)) {
paths.add(new ArrayList(Arrays.asList(visited.toArray())));
return;
}
else {
LinkedList<String> nodes = graph.adjacentNodes(currentNode);
for (String node : nodes) {
if (visited.contains(node)) {
continue;
}
List<String> temp = new ArrayList<String>();
temp.addAll(visited);
temp.add(node);
findAllPaths(graph, temp, paths, node);
}
}
}
} |
节目输出
1
2
3
4
5
6
7
8
9
| B A C E
B A C F E
B E
B F C E
B F E |
用C代码解决。它基于使用最少内存的DFS。
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
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
| #include <stdio.h>
#include <stdbool.h>
#define maxN 20
struct nodeLink
{
char node1;
char node2;
};
struct stack
{
int sp;
char node[maxN];
};
void initStk(stk)
struct stack *stk;
{
int i;
for (i = 0; i < maxN; i++)
stk->node[i] = ' ';
stk->sp = -1;
}
void pushIn(stk, node)
struct stack *stk;
char node;
{
stk->sp++;
stk->node[stk->sp] = node;
}
void popOutAll(stk)
struct stack *stk;
{
char node;
int i, stkN = stk->sp;
for (i = 0; i <= stkN; i++)
{
node = stk->node[i];
if (i == 0)
printf("src node : %c", node);
else if (i == stkN)
printf(" => %c : dst node.
", node);
else
printf(" => %c", node);
}
}
/* Test whether the node already exists in the stack */
bool InStack(stk, InterN)
struct stack *stk;
char InterN;
{
int i, stkN = stk->sp; /* 0-based */
bool rtn = false;
for (i = 0; i <= stkN; i++)
{
if (stk->node[i] == InterN)
{
rtn = true;
break;
}
}
return rtn;
}
char otherNode(targetNode, lnkNode)
char targetNode;
struct nodeLink *lnkNode;
{
return (lnkNode->node1 == targetNode) ? lnkNode->node2 : lnkNode->node1;
}
int entries = 8;
struct nodeLink topo[maxN] =
{
{'b', 'a'},
{'b', 'e'},
{'b', 'd'},
{'f', 'b'},
{'a', 'c'},
{'c', 'f'},
{'c', 'e'},
{'f', 'e'},
};
char srcNode = 'b', dstN = 'e';
int reachTime;
void InterNode(interN, stk)
char interN;
struct stack *stk;
{
char otherInterN;
int i, numInterN = 0;
static int entryTime = 0;
entryTime++;
for (i = 0; i < entries; i++)
{
if (topo[i].node1 != interN && topo[i].node2 != interN)
{
continue;
}
otherInterN = otherNode(interN, &topo[i]);
numInterN++;
if (otherInterN == stk->node[stk->sp - 1])
{
continue;
}
/* Loop avoidance: abandon the route */
if (InStack(stk, otherInterN) == true)
{
continue;
}
pushIn(stk, otherInterN);
if (otherInterN == dstN)
{
popOutAll(stk);
reachTime++;
stk->sp --; /* back trace one node */
continue;
}
else
InterNode(otherInterN, stk);
}
stk->sp --;
}
int main()
{
struct stack stk;
initStk(&stk);
pushIn(&stk, srcNode);
reachTime = 0;
InterNode(srcNode, &stk);
printf("
Number of all possible and unique routes = %d
", reachTime);
} |
这可能要晚了，但是这是Java中从Casey到CFS的C＃版本的DFS算法，它使用堆栈遍历两个节点之间的所有路径。与往常一样，递归的可读性更好。
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
| void DepthFirstIterative(T start, T endNode)
{
var visited = new LinkedList< T >();
var stack = new Stack< T >();
stack.Push(start);
while (stack.Count != 0)
{
var current = stack.Pop();
if (visited.Contains(current))
continue;
visited.AddLast(current);
var neighbours = AdjacentNodes(current);
foreach (var neighbour in neighbours)
{
if (visited.Contains(neighbour))
continue;
if (neighbour.Equals(endNode))
{
visited.AddLast(neighbour);
printPath(visited));
visited.RemoveLast();
break;
}
}
bool isPushed = false;
foreach (var neighbour in neighbours.Reverse())
{
if (neighbour.Equals(endNode) || visited.Contains(neighbour) || stack.Contains(neighbour))
{
continue;
}
isPushed = true;
stack.Push(neighbour);
}
if (!isPushed)
visited.RemoveLast();
}
} |
1
2
3
4
5
6
7
8
| This is a sample graph to test:
// Sample graph. Numbers are edge ids
// 1 3
// A --- B --- C ----
// | | 2 |
// | 4 ----- D |
// ------------------ |
基本原理是您不必担心图形。这是标准问题，称为动态连接问题。您可以通过以下几种方法来实现是否连接节点：
快速查找
快速联盟
改进算法(两者结合)
这是我用最小时间复杂度O(log * n)尝试过的C代码，这意味着对于65536个边列表，它需要4个搜索，而对于2 ^ 65536，它需要5个搜索。我正在分享算法的实现：普林斯顿大学的算法课程
提示：您可以从上面共享的链接中找到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
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
| /* Checking Connection Between Two Edges */
#include<stdio.h>
#include<stdlib.h>
#define MAX 100
/*
Data structure used
vertex[] - used to Store The vertices
size - No. of vertices
sz[] - size of child's
*/
/*Function Declaration */
void initalize(int *vertex, int *sz, int size);
int root(int *vertex, int i);
void add(int *vertex, int *sz, int p, int q);
int connected(int *vertex, int p, int q);
int main() //Main Function
{
char filename[50], ch, ch1[MAX];
int temp = 0, *vertex, first = 0, node1, node2, size = 0, *sz;
FILE *fp;
printf("Enter the filename -"); //Accept File Name
scanf("%s", filename);
fp = fopen(filename,"r");
if (fp == NULL)
{
printf("File does not exist");
exit(1);
}
while (1)
{
if (first == 0) //getting no. of vertices
{
ch = getc(fp);
if (temp == 0)
{
fseek(fp, -1, 1);
fscanf(fp,"%s", &ch1);
fseek(fp, 1, 1);
temp = 1;
}
if (isdigit(ch))
{
size = atoi(ch1);
vertex = (int*) malloc(size * sizeof(int)); //dynamically allocate size
sz = (int*) malloc(size * sizeof(int));
initalize(vertex, sz, size); //initialization of vertex[] and sz[]
}
if (ch == '
')
{
first = 1;
temp = 0;
}
}
else
{
ch = fgetc(fp);
if (isdigit(ch))
temp = temp * 10 + (ch - 48); //calculating value from ch
else
{
/* Validating the file */
if (ch != ',' && ch != '
' && ch != EOF)
{
printf("
Unkwown Character Detected.. Exiting..!");
exit(1);
}
if (ch == ',')
node1 = temp;
else
{
node2 = temp;
printf("
%d\t%d", node1, node2);
if (node1 > node2)
{
temp = node1;
node1 = node2;
node2 = temp;
}
/* Adding the input nodes */
if (!connected(vertex, node1, node2))
add(vertex, sz, node1, node2);
}
temp = 0;
}
if (ch == EOF)
{
fclose(fp);
break;
}
}
}
do
{
printf("
==== check if connected ===");
printf("
Enter First Vertex:");
scanf("%d", &node1);
printf("
Enter Second Vertex:");
scanf("%d", &node2);
/* Validating The Input */
if( node1 > size || node2 > size )
{
printf("
Invalid Node Value..");
break;
}
/* Checking the connectivity of nodes */
if (connected(vertex, node1, node2))
printf("Vertex %d and %d are Connected..!", node1, node2);
else
printf("Vertex %d and %d are Not Connected..!", node1, node2);
printf("
0/1: ");
scanf("%d", &temp);
} while (temp != 0);
free((void*) vertex);
free((void*) sz);
return 0;
}
void initalize(int *vertex, int *sz, int size) //Initialization of graph
{
int i;
for (i = 0; i < size; i++)
{
vertex[i] = i;
sz[i] = 0;
}
}
int root(int *vertex, int i) //obtaining the root
{
while (i != vertex[i])
{
vertex[i] = vertex[vertex[i]];
i = vertex[i];
}
return i;
}
/* Time Complexity for Add --> logn */
void add(int *vertex, int *sz, int p, int q) //Adding of node
{
int i, j;
i = root(vertex, p);
j = root(vertex, q);
/* Adding small subtree in large subtree */
if (sz[i] < sz[j])
{
vertex[i] = j;
sz[j] += sz[i];
}
else
{
vertex[j] = i;
sz[i] += sz[j];
}
}
/* Time Complexity for Search -->lg* n */
int connected(int *vertex, int p, int q) //Checking of connectivity of nodes
{
/* Checking if root is same */
if (root(vertex, p) == root(vertex, q))
return 1;
return 0;
} |
find_paths ▼显示
这个问题已经老了，已经回答了。但是，没有人显示出完成同一件事的更灵活的算法。所以我将帽子戴上戒指。
我个人发现find_paths▼显示形式的算法很有用，其中：
-
s是起始节点
-
t是目标节点
-
d是要搜索的最大深度
-
k是要查找的路径数
对d和k使用编程语言的无穷大形式将为您提供所有路径。
§显然，如果您使用的是有向图，并且想要s和t之间的所有无向路径，则必须同时运行以下两种方法：
1
| find_paths[s, t, d, k] <join> find_paths[t, s, d, k] |
辅助功能
我个人喜欢递归，尽管有时可能会很困难，但无论如何首先要定义我们的辅助函数：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| def find_paths_recursion(graph, current, goal, current_depth, max_depth, num_paths, current_path, paths_found)
current_path.append(current)
if current_depth > max_depth:
return
if current == goal:
if len(paths_found) <= number_of_paths_to_find:
paths_found.append(copy(current_path))
current_path.pop()
return
else:
for successor in graph[current]:
self.find_paths_recursion(graph, successor, goal, current_depth + 1, max_depth, num_paths, current_path, paths_found)
current_path.pop() |
主功能
这样一来，核心功能就变得微不足道了：
1
2
3
| def find_paths[s, t, d, k]:
paths_found = [] # PASSING THIS BY REFERENCE
find_paths_recursion(s, t, 0, d, k, [], paths_found) |
首先，让我们注意几件事：
-
上面的伪代码是多种语言的混搭-但与python最相似(因为我只是在其中编码)。严格的复制粘贴将不起作用。
-
[]是未初始化的列表，将其替换为您选择的编程语言的等效列表
-
paths_found通过引用传递。显然，递归函数不会返回任何内容。适当处理。
-
在这里，graph假定某种形式的hashed结构。有多种实现图形的方法。无论哪种方式，graph[vertex]都会为您提供有向图中相邻顶点的列表-进行相应调整。
-
这假定您已进行了预处理以去除"带扣"(自环)，循环和多边缘
我认为您应该在此背后描述您的真正问题。我之所以这样说，是因为您要求的是省时的方法，但是问题的答案似乎成倍增长！
因此，我不希望有比指数更好的算法。
我会回溯并遍历整个图表。为了避免循环，请一路上保存所有访问的节点。当您返回时，请取消标记该节点。
使用递归：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| static bool[] visited;//all false
Stack<int> currentway; initialize empty
function findnodes(int nextnode)
{
if (nextnode==destnode)
{
print currentway
return;
}
visited[nextnode]=true;
Push nextnode to the end of currentway.
for each node n accesible from nextnode:
findnodes(n);
visited[nextnode]=false;
pop from currenteay
} |
还是错了？
编辑：
哦，我忘了：
您应该通过利用该节点堆栈来消除递归调用
我最近解决了与此类似的问题，而不是我只对最短的解决方案感兴趣的所有解决方案。
我使用了"先行先广"的迭代搜索，该搜索使用状态队列。每个迭代都保存一条记录，其中包含图形上的当前点以及到达该点的路径。
您从队列中的一条记录开始，该记录具有起始节点和空路径。
通过代码进行的每次迭代都会使该项目脱离列表的顶部，并检查它是否是一种解决方案(到达的节点是您想要的节点，如果可以的话，就是完成了)，否则，它将构造一个新的节点。队列项，其中节点连接到当前节点，并且修改的路径基于上一个节点的路径，并在末尾附加新的跳转。
现在，您可以使用类似的方法，但是当找到解决方案时，不要停止，而是将该解决方案添加到"找到的列表"中并继续。
您需要跟踪已访问的节点列表，以便您永远不会回溯自己，否则会出现无限循环。
如果您想要更多的伪代码发表评论或其他内容，我会详细说明。
这是我脑海中浮现的一个念头：
查找一个连接。 (由于路径长度无关紧要，因此深度优先搜索可能是一种不错的算法。)
禁用最后一个段。
尝试从先前禁用的连接之前的最后一个节点查找另一个连接。
转到2，直到没有更多连接。
据我所知，瑞安·福克斯(58343，克里斯蒂安(58444)和你自己(58461)给出的解决方案都差不多，我不相信广度优先遍历在这种情况下会有所帮助例如，如果边缘为(A,B)，(A,C)，(B,C)，(B,D)和(C,D)，您将获得路径ABD和ACD，但不是ABCD。
正如其他一些张贴者所恰当描述的那样，总的来说，问题在于使用深度优先搜索算法来递归地搜索图形以查找通信端节点之间路径的所有组合。
该算法本身从您提供的起始节点开始，检查其所有传出链接，并通过扩展出现的搜索树的第一个子节点，进行越来越深的搜索，直到找到目标节点或遇到一个节点为止，进行搜索那没有孩子。
搜索然后回溯，返回到它尚未完成探索的最新节点。
我最近在这个话题上写了博客，在此过程中发布了一个示例C ++实现。
除了Casey Watson的答案之外，这是另一个Java实现。
用起始节点初始化访问节点。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| private void getPaths(Graph graph, LinkedList<String> visitedNodes) {
LinkedList<String> adjacent = graph.getAdjacent(visitedNodes.getLast());
for(String node : adjacent){
if(visitedNodes.contains(node)){
continue;
}
if(node.equals(END)){
visitedNodes.add(node);
printPath(visitedNodes);
visitedNodes.removeLast();
}
visitedNodes.add(node);
getPaths(graph, visitedNodes);
visitedNodes.removeLast();
}
} |
我找到了一种枚举所有路径的方法，包括包含循环的无限路径。
Project – Shortest Path
寻找原子路径和周期
我们要做的是找到从点A到点B的所有可能路径。由于涉及到循环，因此您不能仅对所有循环进行遍历。相反，您将必须找到不会循环的原子路径和尽可能小的循环(您不希望循环重复自己)。
我对原子路径的第一个定义是不会两次通过同一节点的路径。但是，我发现并没有采取所有可能。经过一番反思，我发现节点并不重要，但是边缘很重要！因此，原子路径是不会两次通过同一边的路径。
这个定义很方便，它也适用于循环：点A的原子循环是一条从点A到点A的原子路径。
履行
为了获得从点A开始的所有路径，我们将从点A递归遍历该图。在通过一个子节点时，我们将使一个子节点->父节点链接，以便了解我们所有的边已经越过。在转到那个孩子之前，我们必须遍历该链表，并确保尚未遍历指定的边。
当我们到达目的地点时，我们可以存储找到的路径。
当您要释放链接列表时，会出现问题。它基本上是一棵以相反顺序链接的树。一种解决方案是将该列表双链接，找到所有原子路径后，从起点处释放树。
但是，一个聪明的解决方案是使用引用计数(由Garbage Collection启发)。每次您添加到父项的链接时，都会在其引用计数中添加一个。然后，当您到达路径的末尾时，您将向后移动并释放，而引用计数等于1。如果引用计数更高，则只需删除一个并停止。
寻找A的原子循环与寻找从A到A的原子路径相同。但是，我们可以做一些优化。首先，当我们到达目的地点时，仅当边成本之和为负时，才想保存路径：我们只想经历吸收周期。
如您先前所见，在寻找原子路径时会遍历整个图形。取而代之的是，我们可以将搜索区域限制为包含A的强连接组件。要找到这些组件，需要使用Tarjan算法对图进行简单遍历。
结合原子路径和循环
在这一点上，我们拥有了从A到B的所有原子路径以及每个节点的所有原子循环，这些原子路径留给我们来组织一切以获得最短路径。从现在开始，我们将研究如何在原子路径中找到原子循环的最佳组合。
|
