从给定的开始获取所有可能的 DFS 访问

Question

假设我有以下无向图：

V = {v1,v2,v3,v4}
E = {{v1,v2}, {v1,v3}, {v2,v4}, {v3,v4}}

如果我运行一个从v1开始没有目的地的DFS，只是为了访问图中的每个点，有两种可能：v1->v2->v4->v3或v1->v3 ->v4->v2.

我写了一个简短的 python 程序来执行 DFS 的一个路径：

def custom_dfs(path, graph, current):    
    if(current in path):
        return None
    
    path.append(current)
    
    for possibility in graph[current]:
        custom_dfs(path, graph, possibility)

现在我的问题是，如何扩展它以便我可以考虑所有可能性，换句话说，运行每个连接节点上的 DFS？

Answer 1

这是寻找生成树的算法

add start node to span
while nodes outside span
   loop n1 over nodes in span
       loop n2 over nodes not in span
           if n1-n2 link present
               add n2 to span

像这样修改应该（我还没有测试过）枚举所有可能的跨度

add start node to span
push partial span to stack
while stack not empty
   pop partial span from stack
   new_span_found = false
   while nodes outside span
       loop n1 over nodes in span
           loop n2 over nodes not in span
               if n1-n2 link present
                    add n2 to span 
                    push partial span to stack
                    new_span_found = true
   
   if new_span_found
        add span to output

从给定的开始获取所有可能的 DFS 访问

Get all possible DFS visits from a given start

python

graph-theory

permutation