traversieren eines Graphes => Rekursion&OOP

[Michael Keller]

Hallo!

Ich bin selbst kein Fan von Postings mit lange Quelltext und der Frage "wo ist der Fehler", aber es fällt mir wirklich nichts anderes mehr ein.. also wer Lust und zeit hat.
Es geht darum einen Graphen der als Matrix gegeben ist zu durchlaufen... was nicht funktioniert ist das markieren eines Nodes als "visited".. deshalb werden Nodes mehrfach ausgegeben.

unten der Code...

Gruss Michael

<?php
class Node {
var $visited;
var $edges;
var $name;

function Node($name) {
  $this->name = $name;
}

function addEdge($addEdge) {
  $this->edges[]=$addEdge;
}

function depthFirst() {
  if ($this->visited) {
   echo "Das wird nie ausgegeben..";
   return;
  }
  echo $this->name.",";
  $this->visited=true;
  for ($i=0; $i<count($this->edges); $i++) {
   $edge = $this->edges[$i];
   $edge->to->depthFirst();
  }
}
}

class Edge {
var $weight;
var $to;
function Edge($weight, $to) {
  $this->weight = $weight;
  $this->to= $to;
}
}

class Graph {
var $nodes;

function addNode($nodeToAdd) {
  $this->nodes[]=$nodeToAdd;
}

function depthFirst() {
  for ($i=0; $i<count($this->nodes); $i++) {
   $node = $this->nodes[$i];
   if (!$node->visited) {
    $node->depthFirst();
   }
  }
}
}

// Matrix:
$admat[0] = array(0,1,0,0,0,0,0,0,0);
$admat[1] = array(1,0,1,1,0,0,0,0,0);
$admat[2] = array(0,1,0,0,1,0,0,0,0);
$admat[3] = array(0,1,0,0,0,0,0,0,0);
$admat[4] = array(0,0,1,0,0,1,1,1,0);
$admat[5] = array(0,0,0,0,1,0,0,0,1);
$admat[6] = array(0,0,0,0,1,0,0,1,0);
$admat[7] = array(0,0,0,0,1,0,1,0,1);
$admat[8] = array(0,0,0,0,0,1,0,1,0);

$graph = new Graph();
$n=0;
while (count($admat[$n])>0) {
$tempNode = new Node($n);
$graph->addNode($tempNode);
$n++;
}

$n=0;
while (count($admat[$n])>0) {
$m=0;
while (count($admat[$n])>$m) {
  if ($admat[$n][$m]) {
   $edge = new Edge(1,$graph->nodes[$m]);
   $graph->nodes[$n]->edges[]=$edge;
  }
  $m++;
}
$n++;
}

echo $graph->depthFirst();

?>