枚舉無向/無權圖的節點集

Question

在無向和無權圖上，如何列舉長度爲1,2，...，n的所有連接節點組（n是用戶定義的值）？

此問題與此one類似;有這樣的差別：n = 3時爲 ;我還需要找到路徑：A-B-C和C-E-F。

如果n爲4，則路徑應還包括：

A-B-C-d

A-B-C-E

A-B-C-F

A-C-E-F

我想這是類似的問題; 「所有對 - 所有路徑」，其中每個路徑最多可包含n個節點。 您是否也請告訴方法計算複雜性？

我的想法是，我需要同時使用DFS和BFS，但我不確定這是否有效？

Answer 1

你基本上可以使用DFS和一個在length遞歸下傳遞的額外變量，這個變量在每次迭代時都會減少。停止條件將是當該額外的變量沿的線達到0

東西：

DFS(source,length,path): 
    print path //this is always done, because we want all paths up to n 
    if (length == 0): //stop clause 
     return 
    for each (source,u) is an edge: 
     path.append(u) 
     DFS(u,length-1,path) 
     path.removeLast() //clean up environment 

另一個（效率較低，但可能是更優雅）是做一個Iterative Deepening DFS，具有長度= 1， 2，...，n（並將打印放在停止子句中）