图算法查找两个任意顶点之间的所有连接
我正在尝试确定最佳的时间效率算法来完成下面描述的任务。
我有一套记录。对于这组记录，我具有连接数据，该数据指示该组记录中的记录对如何相互连接。这基本上表示一个无向图，其中记录是顶点，而连接数据是边。
集合中的所有记录都有连接信息(即不存在孤立记录；集合中的每个记录都连接到集合中的一个或者多个其他记录)。
我想从集合中选择任意两个记录，并能够显示所选记录之间的所有简单路径。 "简单路径"是指在路径中没有重复记录的路径(即仅有限路径)。
注意：两个选定的记录将始终是不同的(即开始和结束顶点永远不会相同；没有周期)。
例如：
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的简单路径。
All paths connecting B to E:
B->E
B->F->E
B->F->C->E
B->A->C->E
B->A->C->F->E
这是一个例子，实际上我可能有包含数十万条记录的集合。
解决方案
回答
我最近解决了与此类似的问题，而不是我只对最短的解决方案感兴趣的所有解决方案。
我使用了"先行先广"的迭代搜索，该搜索使用状态队列。每个迭代都保存一条记录，其中包含图形上的当前点以及到达该点的路径。
我们从队列中的一条记录开始，该记录具有起始节点和空路径。
通过代码进行的每次迭代都会使该项目脱离列表的开头，并检查它是否是一种解决方案(到达的节点是我们想要的节点，如果可以的话，我们已经完成了)，否则，它将构造一个新的节点。队列项，其中节点连接到当前节点，并且修改的路径基于上一个节点的路径，并在末尾添加新的跳转。
现在，我们可以使用类似的方法，但是当我们找到一个解决方案而不是停止时，请将该解决方案添加到"找到的列表"中并继续。
我们需要跟踪已访问的节点列表，这样就永远不会回溯自己，否则就会陷入无限循环。
如果我们想要更多的伪代码，请发表评论或者其他内容，我将进行详细说明。
回答
这是我脑海中浮现的一个念头：
- 查找一个连接。 (深度优先搜索可能是一种不错的算法，因为路径长度无关紧要。)
- 禁用最后一个段。
- 尝试从先前禁用的连接之前的最后一个节点查找另一个连接。
- 转到2，直到没有更多连接。
回答
我认为我们应该在此背后描述真正问题。我之所以这样说，是因为我们要求的是省时的方法，但问题的答案似乎成倍增长！
因此，我不希望有比指数更好的算法。
我会回溯并遍历整个图表。为了避免循环，请一路上保存所有访问的节点。当我们返回时，请取消标记该节点。
使用递归：
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
}
还是那是错的？
编辑：
哦，我忘了：
我们应该通过利用该节点堆栈来消除递归调用
回答
似乎可以通过对图形进行深度优先搜索来完成。深度优先搜索将找到两个节点之间的所有非循环路径。该算法应该非常快，并且可以扩展到大型图形(图形数据结构稀疏，因此仅使用所需的内存)。
我注意到我们在上面指定的图形只有一个方向(B，E)的边。这是错字还是真的有向图？此解决方案不管如何。抱歉，我无法在C语言中完成此操作，在该领域我有点虚弱。我希望我们能够翻译此Java代码，而不会遇到太多麻烦。
Graph.java：
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：
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();
}
}
程序输出：
B E B A C E B A C F E B F E B F C E
回答
这是我想出的伪代码。这不是任何特定的伪代码方言，但应足够简单以易于遵循。
任何人都想分开。
- [p]是代表当前路径的顶点列表。
- [x]是符合条件的路径列表
- [s]是源顶点
- [d]是目标顶点
- [c]是当前顶点(PathFind例程的参数)
假设有一种查找相邻顶点的有效方法(第6行)。
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
回答
据我所知，瑞安·福克斯(58343，克里斯蒂安(58444)和你自己(58461)给出的解决方案都差不多，我不相信广度优先遍历在这种情况下会有所帮助不能获取所有路径，例如，具有边线((A，B)，(A，C)，((B，C)，(B，D)和(C，D)将获得路径" ABD"和" ACD"，而不是" ABCD"。
回答
美国国家标准技术研究院(NIST)的在线算法和数据结构词典将该问题列为"所有简单路径"，并建议进行深度优先搜索。 CLRS提供了相关的算法。
使用Petri Nets的巧妙技巧可在此处找到
回答
我找到了一种枚举所有路径的方法，包括包含循环的无限路径。
http://blog.vjeux.com/2009/project/project-shortest-path.html
寻找原子路径和周期
Definition
我们要做的是找到从点A到点B的所有可能路径。由于涉及到循环，因此我们不能仅对所有循环进行遍历。相反，我们将必须找到不会循环的原子路径和尽可能小的循环(我们不希望循环重复自己)。
我对原子路径的第一个定义是不会两次通过同一节点的路径。但是，我发现这并没有抓住一切可能性。经过一番反思，我发现节点并不重要，但是边缘很重要！因此，原子路径是不会两次通过同一边的路径。
这个定义很方便，它也适用于循环：点A的原子循环是一条从点A到点A的原子路径。
执行
Atomic Paths A -> B
为了获得从点A开始的所有路径，我们将从点A递归地遍历该图。在通过子级时，我们将使子级->父级链接，以便知道我们所有的边已经越过。在转到那个孩子之前，我们必须遍历该链表，并确保尚未遍历指定的边。
当我们到达目的地点时，我们可以存储找到的路径。
Freeing the list
当我们要释放链接列表时，会出现问题。它基本上是一棵以相反顺序链接的树。一种解决方案是将该列表双重链接，并在找到所有原子路径后，从起点将树释放。
但是，一个聪明的解决方案是使用引用计数(由Garbage Collection启发)。每次我们添加到父项的链接时，都会在其引用计数中添加一个。然后，当我们到达路径的末尾时，当参考计数等于1时，我们将向后移动并释放。如果参考计数等于1，则只需移除一个并停止。
Atomic Cycle A
寻找A的原子循环与寻找从A到A的原子路径相同。但是，我们可以做几种优化。首先，当我们到达目的地点时，仅当边成本之和为负时，才想保存路径：我们只想经历吸收周期。
如我们先前所见，在寻找原子路径时会遍历整个图形。相反，我们可以将搜索区域限制为包含A的强连接组件。要找到这些组件，需要使用Tarjan算法对图进行简单遍历。
结合原子路径和循环
在这一点上，我们拥有了从A到B的所有原子路径以及每个节点的所有原子周期，这些都留给我们来组织一切以获得最短路径。从现在开始，我们将研究如何在原子路径中找到原子循环的最佳组合。
