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

I am trying to determine the best time efficient algorithm to accomplish the task described below.

我正在尝试确定最佳的时间效率算法来完成下面描述的任务。

I have a set of records. For this set of records I have connection data which indicates how pairs of records from this set connect to one another. This basically represents an undirected graph, with the records being the vertices and the connection data the edges.

我有一套记录。对于这组记录，我有连接数据，它指示如何从这个集合中对记录进行连接。这基本上表示一个无向图，记录是顶点和连接数据的边缘。

All of the records in the set have connection information (i.e. no orphan records are present; each record in the set connects to one or more other records in the set).

集合中的所有记录都有连接信息(即没有出现孤儿记录;集合中的每个记录连接到集合中的一个或多个其他记录。

I want to choose any two records from the set and be able to show all simple paths between the chosen records. By "simple paths" I mean the paths which do not have repeated records in the path (i.e. finite paths only).

我要从集合中选择任意两个记录，并能够显示所选记录之间的所有简单路径。通过“简单路径”，我指的是路径中没有重复记录的路径(即只有有限路径)。

Note: The two chosen records will always be different (i.e. start and end vertex will never be the same; no cycles).

注意:两个选择的记录总是不同的(即开始和结束顶点将不再相同;没有周期)。

For example:

例如:

    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]

If I chose B as my starting record and E as my ending record, I would want to find all simple paths through the record connections that would connect record B to record E.

如果我选择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

This is an example, in practice I may have sets containing hundreds of thousands of records.

这是一个例子，在实践中我可能有包含成千上万条记录的集合。

16 个解决方案

#1

It appears that this can be accomplished with a depth-first search of the graph. The depth-first search will find all non-cyclical paths between two nodes. This algorithm should be very fast and scale to large graphs (The graph data structure is sparse so it only uses as much memory as it needs to).

看起来，这可以通过深度优先搜索图来完成。深度优先搜索将发现两个节点之间的所有非循环路径。这个算法应该非常快，并且可以扩展到大型图(图数据结构是稀疏的，所以它只需要占用足够多的内存)。

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.

我注意到您上面指定的图形只有一个方向(B,E)。这是一个印刷错误还是一个有向图?这个解决方案工作。抱歉，我不能用C来做，我在这方面有点弱。我希望您能够在不太麻烦的情况下翻译此Java代码。

Graph.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:

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

Program Output:

项目输出:

B E 
B A C E 
B A C F E 
B F E 
B F C E 

#2

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 depth-first search. CLRS supplies the relevant algorithms.

美国国家标准与技术协会(NIST)的在线算法和数据结构词典将这个问题列为“所有简单的路径”，并建议进行深度优先搜索。CLRS提供相关的算法。

A clever technique using Petri Nets is found here

这里有一个使用Petri网的聪明的技术。

#3

Here is the pseudocode I came up with. This is not any particular pseudocode dialect, but should be simple enough to follow.

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

Anyone want to pick this apart.

每个人都想把它拆开。

• [p] is a list of vertices representing the current path.

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

• [x] is a list of paths where meet the criteria

  [x]是符合条件的路径列表。

• [s] is the source vertex

  [s]是源顶点。

• [d] is the destination vertex

  [d]是目标顶点。

• [c] is the current vertex (argument to the PathFind routine)

  [c]是当前顶点(对路径查找例程的参数)

Assume there is an efficient way to look up the adjacent vertices (line 6).

假设有一种有效的方法来查找相邻的顶点(第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

#4

Since the existing non-recursive DFS implementation given in this answer seems to be broken, let me provide one that actually works.

由于在这个答案中给出的非递归DFS实现似乎被打破了，让我提供一个实际可行的方法。

I've written this in Python, because I find it pretty readable and uncluttered by implementation details (and because it has the handy yield keyword for implementing generators), but it should be fairly easy to port to other languages.

我已经在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

This code maintains two parallel stacks: one containing the earlier nodes in the current path, and one containing the current neighbor index for each node in the node stack (so that we can resume iterating through the neighbors of a node when we pop it back off the stack). I could've equally well used a single stack of (node, index) pairs, but I figured the two-stack method would be more readable, and perhaps easier to implement for users of other languages.

该代码维护两个并行堆栈:一个包含当前路径中的早期节点，另一个包含节点堆栈中每个节点的当前邻居索引(这样我们可以在将节点从堆栈中取出时重新遍历节点的邻居)。我可以同样地使用一组(节点、索引)对，但是我认为两个堆栈方法更容易读，而且对于其他语言的用户来说可能更容易实现。

This code also uses a separate visited set, which always contains the current node and any nodes on the stack, to let me efficiently check whether a node is already part of the current path. If your language happens to have an "ordered set" data structure that provides both efficient stack-like push/pop operations and efficient membership queries, you can use that for the node stack and get rid of the separate visited set.

这段代码还使用了一个单独的访问集，它总是包含当前节点和堆栈上的任何节点，让我有效地检查节点是否已经是当前路径的一部分。如果您的语言恰好有一个“有序集”的数据结构，它提供了高效的栈式推送/pop操作和高效的成员查询，那么您可以使用它来处理节点堆栈，并删除单独访问的集合。

Alternatively, if you're using a custom mutable class / structure for your nodes, you can just store a boolean flag in each node to indicate whether it has been visited as part of the current search path. Of course, this method won't let you run two searches on the same graph in parallel, should you for some reason wish to do that.

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

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

Note that, while this example graph is undirected (i.e. all its edges go both ways), the algorithm also works for arbitrary directed graphs. For example, removing the C -> B edge (by removing B from the neighbor list of C) yields the same output except for the third path (A -> C -> B -> D), which is no longer possible.

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

---

Ps. It's easy to construct graphs for which simple search algorithms like this one (and the others given in this thread) perform very poorly.

简单的搜索算法，比如这一种(以及在这个线程中给出的其他算法)的表现非常糟糕。

For example, consider the task of find all paths from A to B on an undirected graph where the starting node A has two neighbors: the target node B (which has no other neighbors than A) and a node C that is part of a clique of n+1 nodes, like this:

例如,考虑寻找从A到B的所有路径的任务在一个无向图,其中节点有两个邻居:开始目标节点B(没有其他邻居比)和一个小团体的一部分节点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"),
}

It's easy to see that the only path between A and B is the direct one, but a naïve DFS started from node A will waste O(n!) time uselessly exploring paths within the clique, even though it's obvious (to a human) that none of those paths can possibly lead to B.

很容易看到,A和B之间的唯一途径是直接的,但一个天真的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ⁿ) time examining all the possible dead ends before giving up.

还可以构造具有相似属性的DAGs，例如，通过让起始节点A连接目标节点B和另外两个节点C1和C2，这两个节点连接到节点D1和D2，它们都连接到E1和E2，以此类推。对于像这样排列的n层节点，对于从a到B的所有路径的简单搜索最终会浪费O(2n)时间来检查所有可能的死点，然后再放弃。

Of course, adding an edge to the target node B from one of the nodes in the clique (other than C), or from the last layer of the DAG, would create an exponentially large number of possible paths from A to B, and a purely local search algorithm can't really tell in advance whether it will find such an edge or not. Thus, in a sense, the poor output sensitivity of such naïve searches is due to their lack of awareness of the global structure of the graph.

当然,添加一条边从一个节点到目标节点B集团(C),或从DAG的最后一层,将创建一个指数大量可能的路径从A到B,和纯粹的本地搜索算法不能提前告诉是否会发现这样一个优势。因此，从某种意义上说，这种幼稚搜索的输出灵敏度差是由于它们对图的全局结构缺乏认识。

While there are various preprocessing methods (such as iteratively eliminating leaf nodes, searching for single-node vertex separators, etc.) that could be used to avoid some of these "exponential-time dead ends", I don't know of any general preprocessing trick that could eliminate them in all cases. A general solution would be to check at every step of the search whether the target node is still reachable (using a sub-search), and backtrack early if it isn't — but alas, that would significantly slow down the search (at worst, proportionally to the size of the graph) for many graphs that don't contain such pathological dead ends.

虽然有各种各样的预处理方法(比如迭代删除叶子节点，搜索单节点顶点分隔符等等)，但这些方法可以用来避免某些“指数时间死期”，我不知道有什么通用的预处理技巧可以在所有情况下消除它们。一般的解决办法是检查每一步搜索目标节点是否仍可及(使用sub-search),和回溯早期如果不是,但是唉,这将大大降低搜索(在最坏的情况下,按比例的大小图)等许多图表,不含病理死角。

#5

Here is a logically better-looking recursive version as compared to the second floor.

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

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

Program Output

程序输出

B A C E 

B A C F E 

B E

B F C E

B F E 

#6

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

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

}

#7

I have solved a similar problem to this recently, instead of all solutions I was only interested in the shortest.

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

I used a 'breadth first' iterative search which used a queue of status' each of which held a record containing a current point on the graph and the path taken to get there.

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

you start with a single record in the queue, which has the starting node and an empty path.

您从队列中的单个记录开始，该记录具有启动节点和空路径。

Each iteration through the code takes the item off the head of the list, and checks to see if it is a solution (the node arrived at is the one you want, if it is, we are done), otherwise, it constructs a new queue item with the nodes connecting to the current node, and amended paths that are based on the path of the previous node, with the new jump attached at the end.

通过代码每次迭代需要项目负责人名单,并检查是否一个解决方案(节点到达是你想要的,如果是,我们做的),否则,它构造一个新的队列项与节点连接到当前节点,并修改路径是基于先前的路径节点,最后附上新的跳。

Now, you could use something similar, but when you find a solution, instead of stopping, add that solution to your 'found list' and continue.

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

You need to keep track of a visited nodes list, so that you never backtrack on yourself otherwise you have an infinite loop.

您需要跟踪访问的节点列表，这样您就不会对自己进行回溯，否则就会有一个无限循环。

if you want a bit more pseudocode post a comment or something, and I will elaborate.

如果您想要更多的伪代码，请发表评论或其他内容，我将详细说明。

#8

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!

我认为你应该描述一下你真正的问题。我之所以这么说，是因为你要求的是时间效率，而问题的答案似乎是指数级增长!

Therefore I wouldn't expect a better algorithm than something exponential.

因此我不会期望一个比指数更好的算法。

I'd do backtracking and going through the whole graph. In order to avoid cycles, save all visited nodes along the way. When you go back, unmark the node.

我会回溯到整个图表。为了避免循环，在途中保存所有访问过的节点。当您返回时，取消标记该节点。

Using recursion:

使用递归:

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
}

Or is that wrong?

或者是错误的吗?

edit: Oh, and I forgot: You should eliminate the recursive calls by utilizing that node stack

编辑:哦，我忘了:你应该使用那个节点堆栈来消除递归调用。

#9

The basic principle is you need not worry about graphs.This is standard problem known as Dynamic connectivity problem. There are following types of methods from which you can achieve nodes are connected or not:

基本原理是你不用担心图形。这就是所谓的动态连接问题的标准问题。有以下几种方法可以实现节点的连接:

1. Quick Find
2. 快速的找到
3. Quick Union
4. 快速的联盟
5. Improved Algorithm (Combination of both)
6. 改进算法(两者结合)

Here is The C Code That I've tried with minimum time complexity O(log*n) That means for 65536 list of edges, it requires 4 search and for 2^65536, it requires 5 search. I am sharing my implementation from the algorithm: Algorithm Course from Princeton university

这是C代码,我试着用最小的时间复杂度O(log * n)这意味着65536年的边缘,它需要4搜索和2 ^ 65536,它需要5搜索。我正在从这个算法中分享我的实现:从普林斯顿大学的算法课程。

TIP: You can find Java solution from link shared above with proper explanations.

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

#10

This may be late, but here's the same C# version of DFS algorithm in Java from Casey to traverse for all paths between two nodes using a stack. Readability is better with recursive as always.

这可能会很晚，但是这里有一个相同的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    |
    //    ------------------

#11

find_paths[s, t, d, k]

This question is old and answered already. However, none show perhaps a more flexible algorithm for accomplishing the same thing. So I'll throw my hat into the ring.

这个问题已经过时了。然而，没有一种方法能够显示出一种更灵活的算法来完成同样的事情。所以我要把我的帽子扔进戒指。

I personally find an algorithm of the form find_paths[s, t, d, k] useful, where:

我个人找到了一种算法，它是find_paths[s, t, d, k]的算法，其中:

• s is the starting node
• s是起始节点。
• t is the target node
• t是目标节点。
• d is the maximum depth to search
• d是搜索的最大深度。
• k is the number of paths to find
• k是找到的路径数。

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

使用编程语言的形式的无穷d和k§将给你所有的路径。

§ obviously if you are using a directed graph and you want all undirected paths between s and t you will have to run this both ways:

§显然如果你是你想要使用一个有向图和无向的路全s和t之间你要运行这两方面:

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

---

Helper Function

I personally like recursion, although it can difficult some times, anyway first lets define our helper function:

我个人喜欢递归，虽然有时会很困难，但首先我们要定义我们的助手函数:

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

Main Function

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)

---

First, lets notice a few thing:

首先，让我们注意一些事情:

• the above pseudo-code is a mash-up of languages - but most strongly resembling python (since I was just coding in it). A strict copy-paste will not work.
• 上面的伪代码是一种语言的混搭——但最像python(因为我只是在其中编写代码)。一个严格的复制粘贴不会起作用。
• [] is an uninitialized list, replace this with the equivalent for your programming language of choice
• []是一个未初始化的列表，将其替换为与您的编程语言相同的选项。
• paths_found is passed by reference. It is clear that the recursion function doesn't return anything. Handle this appropriately.
• 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 directed graph - adjust accordingly.
• 这里的图是假设某种形式的散列结构。有很多方法可以实现一个图形。无论哪种方式，图[顶点]都得到了一个有向图中相邻顶点的列表——相应地进行调整。
• this assumes you have pre-processed to remove "buckles" (self-loops), cycles and multi-edges
• 这假设您已经预先处理了删除“buckles”(自循环)、循环和多边。

#12

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

下面是我的想法:

1. Find one connection. (Depth-first search is probably a good algorithm for this, since the path length doesn't matter.)
2. 找到一个连接。(深度优先搜索可能是一个很好的算法，因为路径长度无关紧要。)
3. Disable the last segment.
4. 禁用最后一段。
5. Try to find another connection from the last node before the previously disabled connection.
6. 尝试在以前禁用的连接之前找到另一个连接。
7. Goto 2 until there are no more connections.
8. 直到没有更多的连接。

#13

As far as I can tell the solutions given by Ryan Fox (58343, Christian (58444), and yourself (58461) are about as good as it get. I do not believe that breadth-first traversal helps in this case, as you will not get all paths. For example, with edges (A,B), (A,C), (B,C), (B,D) and (C,D) you will get paths ABD and ACD, but not ABCD.

就我所知，瑞恩·福克斯(58343,Christian(58444)和你自己(58461)所给出的解决方案都差不多。我不相信在这种情况下宽度优先遍历是有帮助的，因为您不会得到所有路径。例如，边(A,B)， (A,C)， (B,C)， (B,D)和(C,D)你将得到ABD和ACD的路径，但不是ABCD。

#14

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

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

Finding Atomic Paths & Cycles

寻找原子路径和周期。

Definition

What we want to do is find all the possible paths going from point A to point B. Since there are cycles involved, you can't just go through and enumerate them all. Instead, you will have to find atomic path that doesn't loop and the smallest possible cycles (you don't want your cycle to repeat itself).

我们要做的是找到从A点到b点的所有可能路径，因为涉及到循环，你不能一一列举并一一列举。相反，您必须找到不循环的原子路径和最小的可能周期(您不希望您的循环重复自己)。

The first definition I took of an atomic path is a path that does not go through the same node twice. However, I found out that is was not taking all possibilities. After some reflexion, I figured out that nodes aren't important, however edges are! So an atomic path is a path that does not go through the same edge twice.

我所采用的原子路径的第一个定义是一条不经过相同节点两次的路径。然而，我发现并不是所有的可能性。在一些条件反射之后，我发现节点并不重要，但是边缘是!所以原子路径是一条不经过同一条边两次的路径。

This definition is handy, it also works for cycles: an atomic cycle of point A is an atomic path that goes from point A and ends to point A.

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

Implementation

实现

Atomic Paths A -> B

In order to get all the path starting from point A, we are going to traverse the graph recursively from the point A. While going through a child, we are going to make a link child -> parent in order to know all the edges we have already crossed. Before we go to that child, we must traverse that linked list and make sure the specified edge has not been already walked through.

为了得到从A点开始的所有路径，我们将从A点递归地遍历这个图。在通过一个孩子的过程中，我们将创建一个链接子->父类，以了解我们已经跨越的所有边缘。在我们去到那个孩子之前，我们必须遍历那个链表，并确保指定的边缘没有经过。

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

当我们到达目的地时，我们可以存储我们找到的路径。

Freeing the list

A problem occurs when you want to free the linked list. It is basically a tree chained in the reverse order. A solution would be to double-link that list and when all the atomic paths been found, free the tree from the starting point.

当您想要释放链表时，就会出现问题。它基本上是一棵用倒序排列的树。一个解决方案是将该列表和所有的原子路径都找到，从起点释放树。

But a clever solution is to use a reference counting (inspired from Garbage Collection). Each time you add a link to a parent you adds one to its reference count. Then, when you arrive at the end of a path, you go backward and free while the reference count equals to 1. If it is higher, you just remove one and stop.

但是一个聪明的解决方案是使用引用计数(受垃圾收集的启发)。每次向父节点添加一个链接时，都会向它的引用计数添加一个链接。然后，当您到达路径的末尾时，您将返回到后退和空闲，而引用计数等于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的原子周期与从A到A寻找原子路径是一样的，但是我们可以做一些优化。首先，当我们到达终点时，我们想要保存路径，如果边值的总和为负，我们只希望通过吸收周期。

As you have seen previously, the whole graph is being traversed when looking for an atomic path. Instead, we can limit the search area to the strongly connected component containing A. Finding these components requires a simple traverse of the graph with Tarjan's algorithm.

正如您前面所看到的，整个图是在寻找原子路径时被遍历的。相反，我们可以将搜索区域限制为包含a的强连接组件。找到这些组件需要使用Tarjan算法简单地遍历图表。

Combining Atomic Paths and Cycles

结合原子路径和周期。

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.

在这一点上，我们有从A到B的所有原子路径以及每个节点的所有原子周期，留给我们来组织一切以得到最短路径。从现在开始，我们将学习如何在原子路径中找到原子周期的最佳组合。

#15

As ably described by some of the other posters, the problem in a nutshell is that of using a depth-first search algorithm to recursively search the graph for all combinations of paths between the communicating end nodes.

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

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.

算法本身开始你给它的开始节点,检查所有的外部链接和进展通过扩大搜索树的第一个子节点出现,搜索逐渐越来越深,直到找到目标节点,或直到它遇到一个节点没有孩子。

The search then backtracks, returning to the most recent node it hasn’t yet finished exploring.

搜索然后回溯，返回到最近的节点，它还没有完成探索。

I blogged about this very topic quite recently, posting an example C++ implementation in the process.

我最近在博客中提到了这个话题，并在这个过程中发布了一个示例c++实现。

#16

Adding to Casey Watson's answer, here is another Java implementation,. Initializing the visited node with the start node.

添加到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();  
                }
            }