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

?>

[Michael Keller]

hab das Ganze auf ein übersichtlicheres Problem gekürzt:

dies sollte 5,6,11 ausgeben... das $testn2->visited bleibt aber false (0) obwohl die Ausgabe für die zweite Node (6) gemacht wird und folglich auch $this->visited=true; für Node 6 aufgerufen wird...

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 "halt";
   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;
}
}

$testn = new Node("5");
$testn2 = new Node("6");
$tedge = new Edge(1,$testn2);
$testn->edges[]=$tedge;
echo $testn->depthFirst();
echo $testn->visited;
echo $testn2->visited;

[dedlfix]

echo $begrüßung;

dies sollte 5,6,11 ausgeben...

In PHP5 erfolgt die Ausgabe wie gewünscht.

das $testn2->visited bleibt aber false (0)

In PHP4 gibt es jedoch das von dir geschilderte Problem.

Der Unterschied zwischen beiden Versionen, den ich hier verdächtige, ist die Art und Weise der Übergabe von Parametern beim Funktionsaufruf.

Während bei PHP4 alles als Kopie übergeben wird, übergibt PHP5 bei Objekten eine Referenz. Du arbeitest also, wenn du PHP4 verwendest, in den Funktionen mit Kopien, statt mit Originalen.

Lass dir Referenzen übergeben, dann sollte alles klappen.

echo "$verabschiedung $name";

[Michael Keller]

Guten Tag

vielen Dank für den Tipp!!
PHP5 hats gebracht!

Gruss Michael