Finding paths in a Undirected Graph Finding paths in a Undirected Graph php php

Finding paths in a Undirected Graph


In general, you can do a depth-first search or a breadth-first search, although neither one is superior to the other (since it's easy to come up with examples for which one is superior to the other).

Edit: Upon rereading the question and thinking a bit, since you want all paths from C to A, a DFS starting at C would probably make the most sense. Along the way, you'd have to store sequences of edges and throw sequences away if they don't end up at A.


$stdin = fopen('php://stdin','r'); $stdin = fopen('php://stdin','w');

fscanf(STDIN,"%d\n",$n);fscanf(STDIN,"%d\n",$e);$graph = array();for ($i = 0;$i<$n; $i++){    $graph[$i] = array();}for ($i = 0;$i<$e; $i++){    fscanf(STDIN,"%s%s",$x,$y);    $row = ord($x[0]) - ord('A');    $row = ord($y[0]) - ord('A');    echo $row." ".$col;    $graph[$row][$col] = 1;    $graph[$col][$row] = 1;}for ($i = 0;$i <$n; $i++){    for ($j= 0;$j<$n ;$j++)    {      if ($graph[$i][$j]==1)      {          echo"1 ";      }      else{        echo"0 ";       }      echo "\n";    }}