求任意两个顶点之间所有联系的图算法

Question

求任意两个顶点之间所有联系的图算法我试图确定完成以下任务的最佳时间效率算法。我有一套记录。对于这组记录，我有连接数据，它指示来自这个集合的记录对如何彼此连接。这基本上代表了一个无向图，记录是顶点，连接数据是边。集合中的所有记录都有连接信息(即不存在孤立记录；集合中的每个记录连接到集合中的一个或多个其他记录)。我希望从集合中选择任意两个记录，并且能够显示所选记录之间的所有简单路径。所谓“简单路径”是指路径中没有重复记录的路径(即仅有限路径)。注意：两个选择的记录总是不同的(即起始点和结束顶点永远不会相同；没有循环)。例如：    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这是一个例子，在实践中，我可能有包含数十万条记录的集合。

Answer 1

美国国家标准和技术研究所(NIST)的“算法和数据结构在线词典”将这一问题列为“所有简单路径“并建议深度优先搜索..CLRS给出了相应的算法。

发现了一种利用Petri网的巧妙方法。这里

Answer 2

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

任何人都想把它拆开。

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

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

• [s]是源顶点。

• [d]是目标顶点。

• [C]是当前顶点(路径查找例程的参数)。

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