1

ここ数日間、私は 2 つのノード間のすべての非循環パスをカウントする方法を見つけようと試みてきました。私は幅優先検索と深さ優先検索を使用してきました。どちらかがこのタスクを達成できると確信しています。ただし、以下の DFS コードを適応させて、2 つのノード間のすべての可能なパスを見つける方法に苦労しています。いくつかの異なることを試しました (配列内のノードの記憶、再帰) が、それらを正しく実装しておらず、可能なパスを出力できませんでした。

最終的に、選択した 2 つのノード間のすべての可能なパスを含む配列の配列を返したいと思います。これを達成するために私ができる簡単な変更はありますか? 以下のコードは、私が現在取り組んでいるものです。

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

1 に答える 1

0

グラフのデータ構造を作成し、それをトラバースするためのフレームワーク/ライブラリがあると仮定すると、サイクルが発生した場合、早期リターンでバックトラッキングの深さ優先検索を実行できます。開始ノードからのパスを保存すると、サイクル検出が容易になります。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-24T21:58:52.247 に答える