DFS가있는 두 노드 간의 모든 경로 찾기

Question

지난 며칠 동안 두 노드 사이의 모든 비주기 경로를 계산하는 방법을 찾으려고했습니다. 폭 넓은 우선 검색과 깊이 우선 검색으로 작업 해 왔습니다. 나는이 작업을 수행 할 수 있다고 확신한다. 그러나, 나는 두 노드 사이에 가능한 모든 경로를 찾기 위해 아래의 DFS 코드를 적용하는 방법에 어려움을 겪고있다. 나는 몇 가지 다른 것들 (array, recursion의 노드 기억)을 시도했지만, 올바르게 구현하지 않았고 가능한 경로를 출력 할 수 없었다.

궁극적으로 두 개의 선택된 노드 사이에 가능한 모든 경로를 포함하는 배열 배열을 반환하고 싶습니다. 이 작업을 수행 할 수있는 간단한 수정이 있습니까? 아래 코드는 현재 내가 작업하고있는 코드입니다. 당신을 가정

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); 

Answer 1

그래프 데이터 구조를 생성하고주기를받을 경우를 통과하기 위해, 당신은 초기 수익으로 되돌아 깊이 우선 탐색을 할 수있는 프레임 워크/라이브러리를 가지고있다. 시작 노드에서 경로를 저장하면주기 감지가 쉽습니다. 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))

로 호출 할 수 있습니다