这似乎可以通过对图形进行深度优先搜索来实现。 深度优先搜索将查找两个节点之间的所有非循环路径。

我注意到上面指定的图只有一条边是方向的(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 

美国国家标准与技术研究所(NIST)算法和数据结构在线词典将该问题列为“ all simple paths" depth-first search . CLRS提供了相关的算法。

发现了一种使用Petri网的巧妙方法 here

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

任何人都想把它拆开。

• [p] 是表示当前路径的顶点列表。

• [x] 是满足条件的路径列表

• [s] 是源顶点

• [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实现 this answer 似乎是坏的,让我提供一个实际工作。

我用Python编写了这篇文章,因为我发现它可读性很强,实现细节也很整洁(而且它有方便的 yield 用于实现的关键字 generators ),但移植到其他语言应该相当容易。

# 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 设置,它总是包含当前节点和堆栈上的任何节点,以便让我有效地检查节点是否已经是当前路径的一部分。如果您的语言碰巧有一个“有序集”数据结构,它提供了高效的堆栈式推/弹出操作 和 高效的成员资格查询,您可以将其用于节点堆栈,并消除单独的 拜访 设置

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

下面是一些测试代码,演示了上述函数的工作原理:

# 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)和节点C是A的一部分。 clique 属于 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( !) 时间无用地探索集团内部的路径,即使(对人类而言)这些路径都不可能通向B。

也可以构造 DAGs _1. 和C _{2. 1.} 和D ,两者都连接到E _{1. 2.} 像这样排列的节点层,中堂搜索从a到B的所有路径将最终浪费O(2 ^N )在放弃之前,花时间检查所有可能的死胡同。

当然,从团中的一个节点(C除外)或DAG的最后一层向目标节点B添加边, 将 output sensitivity 这种中堂搜索的主要原因是他们对图形的全局结构缺乏认识。

虽然有各种各样的预处理方法(如迭代消除叶节点、搜索单节点顶点分隔符等)可以用来避免这些“指数时间死角”,但我不知道有任何通用的预处理技巧可以在任何情况下消除它们 全部的 案例。一个通用的解决方案是在搜索的每一步检查目标节点是否仍然可以到达(使用子搜索),如果不能到达,则尽早回溯——但遗憾的是,这将大大降低搜索速度(最坏的情况下,与图的大小成比例),因为许多图 不要 包含这种病态的死胡同。

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 

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

}

这可能已经晚了,但这里是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    |
    //    ------------------

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

我使用了一个“宽度优先”的迭代搜索,它使用了一个“状态”队列,每个队列都保存了一条记录,其中包含图形上的当前点和到达该点的路径。

通过代码的每次迭代都会将该项从列表的开头移除,并检查它是否是一个解决方案(到达的节点是您想要的,如果是,我们就完成了),否则,它会构造一个新的队列项,其中节点连接到当前节点,并根据前一个节点的路径修改路径,在末端附加新的跳跃。

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

您需要跟踪已访问的节点列表,这样您就永远不会回溯自己,否则您将有一个无限循环。

如果你想要更多的伪代码,发表评论或其他东西,我会详细说明。

我认为你应该描述一下这背后的真正问题。我这样说是因为你要求一些时间效率高的东西,但问题的答案似乎呈指数增长!

因此,我不希望有比指数算法更好的算法。

使用递归:

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
}

还是错了?

编辑: 哦,我忘了: 应该通过利用该节点堆栈消除递归调用

1. 快速查找
2. 快速接头
3. 改进算法(两者结合)

下面是我用最小时间复杂度O(log*n)尝试的C代码,这意味着对于65536边列表,它需要4次搜索,对于2^65536,它需要5次搜索。我正在分享我的算法实现: Algorithm Course from Princeton university

提示:您可以从上面共享的链接中找到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;
}

查找路径[s、t、d、k]

这个问题由来已久,已经有了答案。然而,没有一种算法能更灵活地完成同样的任务。所以我要把我的帽子扔进拳击场。

我个人发现了一种形式的算法 find_paths[s, t, d, k] 有用,其中:

• s是起始节点
• t是目标节点
• d是要搜索的最大深度

使用编程语言的无穷形式 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] 获取图形中相邻顶点的列表 指导 图形-相应地调整。
• 这假设您已预处理以删除“扣”(自循环)、循环和多条边

我脑子里有一个想法:

1. 找到一个连接。(深度优先搜索可能是一个很好的算法,因为路径长度无关紧要。)
2. 禁用最后一段。
3. 尝试从先前禁用的连接之前的最后一个节点中查找另一个连接。
4. 转到2,直到没有更多连接。

据我所知,Ryan Fox给出的解决方案( 58343 58444 ),还有你自己( 58461 (A,B) , (A,C) , (B,C) , (B,D) 和 (C,D) ABD 和 ACD ,但不是 ABCD .

我找到了一种方法来枚举所有路径,包括包含循环的无限路径。

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时,你返回并释放。如果它更高,您只需删除一个并停止。

Atomic Cycle A

查找A的原子循环与查找从A到A的原子路径是一样的。但是,我们可以进行一些优化。首先,当我们到达目的地时,我们只想在边成本之和为负时保存路径:我们只想经历吸收循环。

如前所述,在查找原子路径时,将遍历整个图形。相反,我们可以将搜索区域限制为包含A的强连通组件。查找这些组件需要使用Tarjan算法对图进行简单遍历。

结合原子路径和循环

正如其他一些海报所巧妙地描述的,简言之,问题在于使用深度优先搜索算法递归地搜索图形以查找通信端节点之间的所有路径组合。

该算法本身从您给它的开始节点开始,通过展开出现的搜索树的第一个子节点来检查其所有传出链接,并不断深入搜索,直到找到目标节点,或者直到遇到没有子节点的节点。

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

我 blogged 关于这个话题最近,在这个过程中发布了一个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();  
                }
            }