查找两个任意顶点之间的所有连接的图算法
https://stackoverflow.com/questions/58306
-
09-06-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian题
我正在尝试确定完成下述任务的最佳时间效率算法。
我有一组记录。对于这组记录，我有连接数据，它指示该组中的记录对如何相互连接。这基本上表示一个无向图，记录是顶点，连接数据是边。
该集中的所有记录都有连接信息（即没有孤儿记录；集合中的每条记录都连接到集合中的一个或多个其他记录）。
我想从集合中选择任意两条记录，并能够显示所选记录之间的所有简单路径。“简单路径”是指路径中没有重复记录的路径（即仅有限路径）。
笔记：两个选择的记录总是不同的（即起始和结束顶点永远不会相同；无循环）。
例如：
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
这是一个例子，在实践中我可能有包含数十万条记录的集合。
解决方案
看来这可以通过图的深度优先搜索来完成。 深度优先搜索将找到两个节点之间的所有非循环路径。 该算法应该非常快并且可以扩展到大型图（图数据结构是稀疏的，因此它只使用所需的内存）。
我注意到您上面指定的图只有一个有方向的边（B，E）。这是一个错字还是它真的是一个有向图？无论如何，这个解决方案都有效。抱歉，我无法用 C 语言做到这一点，我在这方面有点弱。我希望您能够轻松翻译这段 Java 代码。
图.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);
}
}
搜索.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
由于现有的非递归 DFS 实现中给出 这个答案 似乎坏了，让我提供一个真正有效的。
我用 Python 编写了这个，因为我发现它非常可读并且实现细节整洁（而且因为它有方便的 yield 实施关键字 发电机），但移植到其他语言应该相当容易。
# 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 set，它始终包含当前节点和堆栈上的任何节点，让我有效地检查节点是否已经是当前路径的一部分。如果您的语言碰巧有一个“有序集”数据结构，它提供了高效的类似堆栈的推送/弹出操作 和 高效的成员资格查询，您可以将其用于节点堆栈并摆脱单独的 visited 放。
或者，如果您为节点使用自定义可变类/结构，则可以在每个节点中存储一个布尔标志，以指示它是否已作为当前搜索路径的一部分被访问。当然，如果您出于某种原因希望这样做，则此方法不会让您在同一个图上并行运行两个搜索。
下面是一些测试代码，演示了上面给出的函数如何工作：
# 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)
在给定的示例图上运行此代码会产生以下输出：
A -> B -> C -> D A -> B -> D A -> C -> B -> D A -> C -> D
请注意，虽然此示例图是无向的（即它的所有边都是双向的），该算法也适用于任意有向图。例如，删除 C -> B 边缘（通过删除 B 从邻居列表中 C）产生相同的输出，除了第三条路径（A -> C -> B -> D），这已经不可能了。
诗。 构建图很容易，但像这样的简单搜索算法（以及本线程中给出的其他算法）的性能却非常差。
例如，考虑在无向图上查找从 A 到 B 的所有路径的任务，其中起始节点 A 有两个邻居：目标节点 B（除了 A 之外没有其他邻居）和属于 a 的节点 C 集团 的 n+1 节点，如下所示：
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。
还可以构建 有向无环图 具有相似的属性，例如让起始节点 A 连接目标节点 B 并连接到其他两个节点 C1 和C2, ，两者都连接到节点 D1 和D2, ，两者都连接到E1 和E2, ， 等等。为了 n 像这样排列的节点层，天真的搜索从 A 到 B 的所有路径最终会浪费 O(2n）在放弃之前花时间检查所有可能的死胡同。
当然，从 clique 中的一个节点（C 除外）或从 DAG 的最后一层向目标节点 B 添加一条边， 会 创建从 A 到 B 的指数级数量的可能路径，而纯粹的局部搜索算法无法真正提前判断是否会找到这样的边缘。因此，从某种意义上说，穷人 输出灵敏度 这种幼稚的搜索是由于他们缺乏对图的全局结构的认识。
虽然有各种预处理方法（例如迭代消除叶节点、搜索单节点顶点分隔符等）可用于避免其中一些“指数时间死胡同”，但我不知道有任何通用方法可以消除它们的预处理技巧 全部 案例。一个通用的解决方案是在搜索的每一步检查目标节点是否仍然可达（使用子搜索），如果不是，则尽早回溯 - 但可惜，这会显着减慢搜索速度（最坏的情况是） ，与图的大小成比例）对于许多图来说 不 包含这种病态的死胡同。
与二楼相比，这是一个逻辑上更好看的递归版本。
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);
}
}
}
}
程序输出
B A C E
B A C F E
B E
B F C E
B F E
C 代码解决方案。它基于使用最少内存的 DFS。
#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.\n", 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("\nNumber of all possible and unique routes = %d\n", reachTime);
}
我最近解决了与此类似的问题，而不是所有解决方案，我只对最短的解决方案感兴趣。
我使用了“广度优先”迭代搜索，该搜索使用了“状态队列”，每个状态队列都包含一条记录，其中包含图表上的当前点以及到达该点所采取的路径。
您从队列中的单个记录开始，该记录具有起始节点和空路径。
代码的每次迭代都会从列表的头部取出该项目，并检查它是否是一个解决方案（到达的节点是您想要的节点，如果是，我们就完成了），否则，它构造一个新的队列项包含连接到当前节点的节点，以及基于前一个节点的路径修改的路径，并在末尾附加新的跳转。
现在，您可以使用类似的东西，但是当您找到解决方案时，不要停止，而是将该解决方案添加到“找到的列表”中并继续。
您需要跟踪访问过的节点列表，这样您就不会自行回溯，否则就会陷入无限循环。
如果您想要更多伪代码，请发表评论或其他内容，我会详细说明。
我认为你应该描述一下这背后的真正问题。我这样说是因为你要求一些时间效率高的东西，但问题的答案似乎呈指数级增长！
因此，我不期望有比指数算法更好的算法。
我会回溯并浏览整个图表。为了避免循环，保存沿途所有访问过的节点。返回时，取消标记该节点。
使用递归：
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
}
或者说这是错误的？
编辑：哦，我忘了：您应该通过利用该节点堆栈来消除递归调用
基本原则是您不必担心图。这是称为动态连接问题的标准问题。有以下几种方法可以实现节点的连通与否：
- 快速查找
- 快联
- 改进算法（两者的结合）
这是我尝试过的 C 代码，时间复杂度为 O(log*n)，这意味着对于 65536 个边列表，它需要 4 次搜索，对于 2^65536，它需要 5 次搜索。我正在分享我的算法实现： 普林斯顿大学算法课程
提示：您可以从上面共享的链接找到 Java 解决方案以及正确的解释。
/* 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 == '\n')
{
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 != '\n' && ch != EOF)
{
printf("\n\nUnkwown Character Detected.. Exiting..!");
exit(1);
}
if (ch == ',')
node1 = temp;
else
{
node2 = temp;
printf("\n\n%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("\n\n==== check if connected ===");
printf("\nEnter First Vertex:");
scanf("%d", &node1);
printf("\nEnter Second Vertex:");
scanf("%d", &node2);
/* Validating The Input */
if( node1 > size || node2 > size )
{
printf("\n\n 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("\n 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;
}
这可能晚了，但这里有来自 Casey 的 Java 中 DFS 算法的相同 C# 版本，用于使用堆栈遍历两个节点之间的所有路径。一如既往，递归的可读性更好。
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();
}
}
This is a sample graph to test:
// Sample graph. Numbers are edge ids
// 1 3
// A --- B --- C ----
// | | 2 |
// | 4 ----- D |
// ------------------
find_paths[s, t, d, k]
这个问题很老了，已经回答了。然而，没有人展示出更灵活的算法来完成同样的事情。所以我会把我的帽子扔进擂台。
我个人找到了一种以下形式的算法 find_paths[s, t, d, k] 有用，其中：
- s 是起始节点
- t 是目标节点
- d 是搜索的最大深度
- k 是要查找的路径数
使用编程语言的无穷形式 d 和 k 会给你所有的路径§。
§ 显然，如果您使用有向图并且您想要所有 无向的 之间的路径 s 和 t 你必须以两种方式运行：
find_paths[s, t, d, k] <join> find_paths[t, s, d, k]
辅助功能
我个人喜欢递归，尽管有时可能很困难，无论如何首先让我们定义我们的辅助函数：
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()
主功能
排除了这一点，核心功能就变得微不足道了：
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]获取 a 中相邻顶点的列表 指导的 图表 - 相应调整。 - 这假设您已进行预处理以删除“带扣”（自环）、循环和多边
这是我脑海中浮现的一个想法：
- 找到一个连接。（深度优先搜索可能是一个很好的算法，因为路径长度并不重要。）
- 禁用最后一段。
- 尝试从先前禁用的连接之前的最后一个节点查找另一个连接。
- 转到 2，直到不再有连接。
我找到了一种枚举所有路径的方法，包括包含循环的无限路径。
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
当您想要释放链接列表时，就会出现问题。它基本上是一棵以相反顺序链接的树。解决方案是双重链接该列表，当找到所有原子路径时，将树从起点释放。
但一个聪明的解决方案是使用引用计数（受垃圾收集启发）。每次添加指向父级的链接时，都会为其引用计数添加 1。然后，当您到达路径的末端时，您将向后并自由，同时引用计数等于 1。如果它更高，您只需删除一个即可停止。
Atomic Cycle A
寻找 A 的原子周期与寻找从 A 到 A 的原子路径相同。然而，我们可以做一些优化。首先，当我们到达目的地时，只有当边成本之和为负时，我们才想保存路径：我们只想经历吸收的循环。
正如您之前所看到的，在寻找原子路径时会遍历整个图。相反，我们可以将搜索区域限制为包含 A 的强连通分量。找到这些组件需要使用 Tarjan 算法对图进行简单的遍历。
结合原子路径和循环
至此，我们有了从 A 到 B 的所有原子路径以及每个节点的所有原子循环，剩下的就留给我们组织一切以获得最短路径。从现在开始，我们将研究如何在原子路径中找到原子循环的最佳组合。
正如其他一些发帖者巧妙地描述的那样，简而言之，问题是使用深度优先搜索算法递归地搜索图形以查找通信端节点之间的路径的所有组合。
该算法本身从您给它的起始节点开始，检查其所有传出链接，并通过扩展出现的搜索树的第一个子节点来进行，逐渐越来越深入地搜索，直到找到目标节点，或者直到遇到一个节点没有孩子。
然后搜索回溯，返回到尚未完成探索的最新节点。
我 写博客 最近关于这个主题，在此过程中发布了一个 C++ 实现示例。
添加到 Casey Watson 的答案中，这是另一个 Java 实现。使用起始节点初始化访问节点。
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();
}
}
