使用DFS查找兩個節點之間的所有路徑

過去幾天，我一直在試圖找到一種方法來計算兩個節點之間的所有非循環路徑。我一直在進行廣度優先搜索和深度優先搜索。我相當確定要麼完成這項任務。然而，我一直在努力如何適應下面的DFS代碼來找到兩個節點之間的所有可能的路徑。我嘗試了一些不同的東西（記住數組中的節點，遞歸），但是我沒有正確實現它們，並且無法輸出可能的路徑。使用DFS查找兩個節點之間的所有路徑

最終，我想返回一個包含兩個選定節點之間所有可能路徑的數組數組。有什麼簡單的修改，我可以做到這一點？下面的代碼是我目前正在使用的。

function init(&$visited, &$graph){ 
    foreach ($graph as $key => $vertex) { 
    $visited[$key] = 0; 
    } 
} 

/* DFS args 
$graph = Node x Node sociomatrix 
$start = starting node 
$end = target node (currently not used) 
$visited = list of visited nodes 
$list = hold keys' corresponding node values, for printing path; 
*/ 

function depth_first(&$graph, $start, $end, $visited, $list){ 

    // create an empty stack 
    $s = array(); 

    // put the starting node on the stack 
    array_push($s, $start); 

    // note that we visited the start node 
    $visited[$start] = 1; 

    // do the following while there are items on the stack 
    while (count($s)) { 

    // remove the last item from the stack 
    $t = array_pop($s); 

    // move through all connections 
    foreach ($graph[$t] as $key => $vertex) { 

     // if node hasn't been visited and there's a connection 
     if (!$visited[$key] && $vertex == 1) { 

     // note that we visited this node 
     $visited[$key] = 1; 

     // push key onto stack 
     array_push($s, $key); 

     // print the node we're at    
     echo $list[$key];     
     }    
    }   
    } 
} 

// example usage 
$visited = array(); 
$visited = init($visited, $sym_sociomatrix); 
breadth_first($sym_sociomatrix, 1, 3, $visited, $list);

來源

2012-12-31 user1114864

假設你有一個框架/庫來創建一個圖形數據結構和遍歷它，你可以做一個提前返還回溯深度優先搜索，如果你得到一個週期。如果您從起始節點存儲路徑，則循環檢測很容易。在C風格的僞代碼（對不起，不知道PHP，或者如果它能夠遞歸）：

void DFS(Vertex current, Vertex goal, List<Vertex> path) { 
    // avoid cycles 
    if (contains(path, current) 
    return; 

    // got it! 
    if (current == goal)) { 
    print(path); 
    return; 
    } 

    // keep looking 
    children = successors(current); // optionally sorted from low to high cost 
    for(child: children)   
     DFS(child, add_path(path, child));  
}

，然後你可以把它作爲DFS(start, goal, List<Vertex>(empty))

來源

2013-01-24 21:58:52 TemplateRex

使用DFS查找兩個節點之間的所有路徑

回答

相關問題