求两个任意顶点之间所有连接的图算法

小开

我最近解决了一个类似的问题，而不是所有的解决方案，我只对最短的感兴趣。

我使用了“广度优先”迭代搜索，它使用了状态队列，每个状态队列都包含一个记录，其中包含图表上的当前点和到达那里的路径。

您从队列中的一条记录开始，该记录具有起始节点和一个空路径。

通过代码的每次迭代都会将该条目从列表的头部移除，并检查它是否是一个解决方案(到达的节点是你想要的节点，如果是，我们就完成了) ，否则，它将构建一个新的队列条目，其中的节点连接到当前节点，并修改基于前一个节点路径的路径，最后附加新的跳转。

现在，您可以使用类似的方法，但是当您找到一个解决方案时，不要停止，而是将该解决方案添加到您的“已找到列表”中，然后继续。

您需要跟踪访问过的节点列表，这样您就永远不会回溯自己，否则您将陷入无限循环。

如果你想要更多的伪代码发表一个注释或东西，我会详细说明。

小开

Here's a thought off the top of my head:

找到一个连接(深度优先搜索可能是一个很好的算法，因为路径长度并不重要)
关闭最后一段。
尝试从先前禁用的连接之前的最后一个节点中找到另一个连接。
Goto 2 until there are no more connections.

小开

I think you should describe your real problem behind this. I say this because you ask for something time efficient, yet the answer set to the problem seems to grow exponentially!

因此，我认为最好的算法不会是指数型的。

我会回溯并浏览整个图表。为了避免循环，保存沿途访问的所有节点。当您返回时，取消标记节点。

使用递归:

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
}

难道这样不对吗？

edit: 哦，我忘了: 您应该利用该节点堆栈来消除递归调用

小开

最佳答案

这似乎可以通过图表的深度优先搜索来实现。The depth-first search will find all non-cyclical paths between two nodes.这个算法应该非常快，并且可以扩展到大型图形(图形数据结构是稀疏的，所以它只使用所需要的内存)。

I noticed that the graph you specified above has only one edge that is directional (B,E). Was this a typo or is it really a directed graph? This solution works regardless. Sorry I was unable to do it in C, I'm a bit weak in that area. I expect that you will be able to translate this Java code without too much trouble though.

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

小开

这是我想出来的伪代码。这不是任何特定的伪代码方言，但是应该足够简单易懂。

Anyone want to pick this apart.

[ 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

小开

据我所知，Ryan Fox (58343，Christian (58444)和你自己((A,C)0)给出的解决方案是最好的。我不认为广度优先遍历在这种情况下有帮助，因为您不会得到所有路径。例如，对于边 (A,B)、 (A,C)、 (B,C)、 (B,D)和 (C,D)，您将得到路径 ABD和 ACD，但是不能得到 ABCD。

小开

The National Institute of Standards and Technology (NIST) online Dictionary of Algorithms and Data Structures lists this problem as "all simple paths" and recommends a 深度优先搜索. CLRS supplies the relevant algorithms.

使用 Petri 网的一个聪明的技术是找到给你

小开

I found a way to enumerate all the paths including the infinite ones containing loops.

Http://blog.vjeux.com/2009/project/project-shortest-path.html

查找原子路径和循环

Definition

我们要做的是找到从 A 点到 B 点的所有可能路径。由于涉及到循环，您不能只是遍历并枚举它们。相反，您必须找到不循环的原子路径和最小可能的循环(您不希望您的循环重复自己)。

我对原子路径的第一个定义是不经过同一个节点两次的路径。然而，我发现那并不是采取所有的可能性。经过一番思考，我发现节点并不重要，但边却很重要！所以原子路径是一条不会经过同一条边两次的路径。

这个定义很方便，它也适用于循环: 点 A 的原子循环是从点 A 到点 A 的原子路径。

实施

Atomic Paths A -> B

为了得到从点 A 开始的所有路径，我们要从点 A 递归遍历图。当我们通过一个孩子的时候，我们要做一个链接子-> 父，以便知道我们已经越过的所有边缘。在转到该子级之前，必须遍历该链表，并确保指定的边没有被遍历。

When we arrive to the destination point, we can store the path we found.

Freeing the list

当您想释放链表时会发生问题。它基本上是一个以相反顺序链接的树。一个解决方案是双链接该列表，当找到所有原子路径时，从起始点释放树。

但是一个聪明的解决方案是使用引用计数(灵感来自垃圾收集)。每次添加到父级的链接时，都会在其引用计数中添加一个链接。然后，当你到达一条路径的终点时，你向后自由移动，而引用计数等于1。如果它高，你只需要删除一个和停止。

Atomic Cycle A

Looking for the atomic cycle of A is the same as looking for the atomic path from A to A. However there are several optimizations we can do. First, when we arrive at the destination point, we want to save the path only if the sum of the edges cost is negative: we only want to go through absorbing cycles.

如前所述，在寻找原子路径时，将遍历整个图。相反，我们可以将搜索范围限制在包含 a 的强连通分量上，要找到这些组件，只需利用 Tarjan 算法对图进行简单的遍历。

结合原子路径和循环

At this point, we have all the atomic paths that goes from A to B and all the atomic cycles of each node, left to us to organize everything to get the shortest path. From now on we are going to study how to find the best combination of atomic cycles in an atomic path.

小开

正如其他一些海报所描述的那样，简而言之，问题在于使用深度优先搜索算法递归地搜索图中通信端节点之间的所有路径组合。

The algorithm itself commences with the start node you give it, examines all its outgoing links and progresses by expanding the first child node of the search tree that appears, searching progressively deeper and deeper until a target node is found, or until it encounters a node that has no children.

然后搜索返回，返回到它尚未完成探索的最近节点。

关于这个话题，我最近在博客上发表了一个 C + + 实现的例子。

小开

与第二层相比，这里有一个逻辑上更好看的递归版本。

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

小开

Solution in C code. It is based on DFS which uses minimum memory.

#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);


}

小开

基本原则是你不必担心图表。这是被称为动态连通性问题的标准问题。可以通过以下方法实现节点的连接或不连接:

快速查找
快速联盟
改进算法(两者结合)

这是 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;
}

小开

这可能有点晚了，但是这里提供了相同的 C # 版本的 DFS 算法，从 Casey 开始使用栈遍历两个节点之间的所有路径。递归的可读性总是更好。

    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    |
//    ------------------

小开

由于这个答案中给出的现有非递归 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集，它始终包含当前节点和堆栈上的任何节点，以便有效地检查一个节点是否已经是当前路径的一部分。如果您的语言碰巧具有一个“有序集”数据结构，该结构提供类似于堆栈的高效推送/弹出操作还有高效成员查询，那么您可以将其用于节点堆栈，并去掉单独的 visited集。

或者，如果您正在为您的节点使用一个自定义的可变类/结构，您可以只在每个节点中存储一个布尔标志，以指示它是否作为当前搜索路径的一部分被访问过。当然，这种方法不允许您在同一个图上并行地运行两个搜索，如果您出于某种原因希望这样做的话。

Here's some test code demonstrating how the function given above works:

# 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)

Running this code on the given example graph produces the following output:

A -> B -> C -> D
A -> B -> D
A -> C -> B -> D
A -> C -> D

注意，虽然这个示例图是无向的(即它的所有边都是双向的) ，但是该算法也适用于任意有向图。例如，除去 C -> B边缘(通过从 C的邻居列表中除去 B) ，除了第三条路径(A -> C -> B -> D)外，产生相同的输出，这是不可能的。

P.很容易构造一些简单的搜索算法表现很差的图，比如这个(以及这个线程中给出的其他算法)。

例如，考虑在一个无向图上查找从 A 到 B 的所有路径，其中起始节点 A 有两个邻居: 目标节点 B (除了 A 没有其他邻居)和作为 N + 1节点的小团体的一部分的节点 C，如下所示:

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。

One can also construct DAGs with similar properties, e.g. by having the starting node A connect target node B and to two other nodes C₁ and C₂, both of which connect to the nodes D₁ and D₂, both of which connect to E₁ and E₂, and so on. For N layers of nodes arranged like this, a naïve search for all paths from A to B will end up wasting O(2^N) time examining all the possible dead ends before giving up.

当然，在目标节点 B 上添加一条来自圈子中的一个节点(C 节点除外)的边，或者来自 DAG 的最后一层，会创建了从 A 到 B 的大量指数级的可能路径，纯粹的局部搜索算法不能真正预先判断它是否会找到这样的边。因此，从某种意义上说，这种幼稚搜索中较差的输出灵敏度输出灵敏度是由于它们缺乏对图的全局结构的认识。

虽然有各种各样的预处理方法(如迭代消除叶节点，搜索单节点顶点分隔符，等等) ，可以用来避免这些“指数时间死胡同”，我不知道任何一般的预处理技巧，可以消除它们在所有的情况下。一个通用的解决方案是在搜索的每一个步骤中检查目标节点是否仍然可以到达(使用子搜索) ，如果不是 & mash，则尽早回溯; 但是，唉，这将显着减慢搜索(最坏的情况下，与图的大小成比例) ，许多图的不要包含这样的病态死胡同。

小开

为了补充 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(); } }

小开

Find _ path [ s，t，d，k ]

这个问题很老了，已经有答案了。然而，没有一种算法可以更灵活地完成同样的任务。所以我要参加比赛。

我个人认为 find_paths[s, t, d, k]形式的算法很有用，其中:

S 是起始节点

T 是目标节点

D 是搜索的最大深度

K 是要查找的路径数

Using your programming language's form of infinity for d and k will give you all paths§.

显然，如果你使用一个有向图，你想要 s和 t之间的所有 没有方向路径，你必须运行这两种方式:

find_paths[s, t, d, k] <join> find_paths[t, s, d, k]

助理职能

我个人喜欢递归，尽管有时候它会很困难，不管怎样，首先让我们定义我们的 helper 函数:

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()

主要功能

With that out of the way, the core function is trivial:

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由 参考文献传递。很明显，递归函数不返回任何东西。适当地处理这个问题。

here graph is assuming some form of hashed structure. There are a plethora of ways to implement a graph. Either way, graph[vertex] gets you a list of adjacent vertices in a 导演 graph - adjust accordingly.

this assumes you have pre-processed to remove "buckles" (self-loops), cycles and multi-edges