我正在嘗試計算兩個節點之間的所有簡單路徑。我試過DFS，它似乎DFS將無法正常工作。查找具有循環圖的兩點之間的所有簡單路徑

下圖讓我的目標更清晰。

兩個節點 'A' 和 'F'，並給出了必須要找到它們之間的路徑。對於上面的例子中，有兩個簡單路徑：

甲 - >乙 - >Ç - >電子 - >˚F

甲 - >乙 - > d - >電子 - >˚F

我檢查了一些帖子，但他們似乎不處理週期（沒有循環我的DFS作品）。

該圖是無向的並且有循環。我相信這是一個解決方案。任何人都可以指出我一個可靠的算法？如果這樣的算法帶有僞代碼，那將是很好的。

在預先感謝最佳，

來源

2016-01-22 arslan

事實上，你可能只是做遞歸的DFS，但總是給作爲參數的訪問節點，並確保你沒有深入瞭解你在當前已訪問過的節點DFS路徑（從而避免週期）。請注意，這與全局訪問列表不同，因爲它不會允許您多次訪問同一個節點。 –

哦，作爲一個加號，你進行的訪問列表，正是你找到最終節點時所需要的路徑。 –

我不好意思，我應該提及的是我嘗試了非遞歸DFS。但問題是在上圖{a - > b - > c - > e - > f}中找到一條簡單路徑時，則會查找第二條路徑，但'e'已被訪問，因此無法繼續。遞歸DFS解決了這個問題嗎？ – arslan

這裏是使用加權ADJ矩陣和避免循環一個Ruby溶液。這有點凌亂，但它接縫工作。我試圖用連接循環（如環）中的節點a，b，c，d，e，f但具有兩個額外連接（b <→f和c <→f）生成循環測試算法。

# Generate all paths from A to E 
@grapascii = 
' 
    C-----D 
/\ | 
B---F---E 
    \/ 
    A 
' 

@nodes = %w{A B C D E F} 
n = -1 # represents no connection 

#weighted adj matrix 
@adjmat = [ 
    #a b c d e f 
    [n, 1, n, n, n, 1], # a 
    [1, n, 3, n, n, 1], # b 
    [n, 4, n, 2, n, 1], # c 
    [n, n, 4, n, 1, n], # d 
    [n, n, n, 1, n, 1], # e 
    [1, 6, 1, n, 2, n] # f 
] 

# generate a neighbors hash for easy and fast future acccess 
def gen_neighbors(nodes, adjmat) 
    len = nodes.length 
    neighbors = {} 
    for i in 0..(len - 1) 
     for j in 0..(len - 1) 
      if adjmat[i][j] >= 0 && i != j 
       neighbors[nodes[i]] ||= [] 
       neighbors[nodes[i]] << {:node => nodes[j], :cost => adjmat[i][j]} 
      end 
     end 
    end 
    return neighbors 
end 

@neighbors = gen_neighbors(@nodes, @adjmat) 

def all_paths(currpath, destnode, currcost, paths) 
    #the current node is always tha last one on the current evaluated path 
    currnode = currpath.last 
    # just the neighbors that is nor on the current evaluated path, to avoid cycles 
    current_neighbors = @neighbors[currnode].select{|n| !currpath.include?(n[:node])} 

    #each neighbor is a hash with :node and :cost 
    current_neighbors.each do |neighbor| 
     # yes. we have to duplicate that. maybe there is a better solution... 
     new_path = currpath + [neighbor[:node]] 
     cost = currcost + neighbor[:cost] 

     if neighbor[:node] == destnode 
      #FOUND PATH 
      paths << {:path => new_path, :cost => cost} 
     else 
      all_paths(new_path, destnode, cost, paths) 
     end 
    end 
end 

puts @grapascii 

puts "NEIGHBORS HASH:" 
@neighbors.each do |node, neighbors| 
    neighbors_and_cost = neighbors.map{|n| "#{n[:node]}(#{n[:cost]})"} 
    puts "#{node} => #{neighbors_and_cost.join(', ')}" 
end 


# start path with the start node 
startpath = ['A'] 
# paths variable will hold all possible paths without cycles 
paths = [] 
all_paths(startpath, 'E', 0, paths) 

puts "PATHS:" 
# sort paths by total cost(optional) 
paths.sort!{|a, b| a[:cost] <=> b[:cost]} 
paths.each do |path| 
    puts "#{path[:path]} => #{path[:cost]}" 
end

輸出：

C-----D 
/\ | 
B---F---E 
    \/ 
    A 
NEIGHBORS HASH: 
A => B(1), F(1) 
B => A(1), C(3), F(1) 
C => B(4), D(2), F(1) 
D => C(4), E(1) 
E => D(1), F(1) 
F => A(1), B(6), C(1), E(2) 
PATHS: 
["A", "F", "E"] => 3 
["A", "B", "F", "E"] => 4 
["A", "F", "C", "D", "E"] => 5 
["A", "B", "F", "C", "D", "E"] => 6 
["A", "B", "C", "D", "E"] => 7 
["A", "B", "C", "F", "E"] => 7 
["A", "F", "B", "C", "D", "E"] => 13

來源

2016-10-13 05:28:02

查找具有循環圖的兩點之間的所有簡單路徑

回答

輸出：

相關問題