PHP Array Weg durchlaufen

[DadyCool]

Ich habe einen Array, der z.B so aussehen kann.

Array
(
    [x1] => x2
    [x2] => x4
    [x3] => x4
    [x4] => x5
    [x5] => x3
    [x6] => x7
    [x7] => x8
)

Der Array gibt an von welchen Key man über den Value zum nächsten Key kommen kann. Nun möchte ich alle Keys herrausfinden, die über einen Weg z.B. zu dem Key x4 führen können, also in dem Fall wären dass:

[x1], [x2] -> x4
[x3] -> x4
[x5], [x3] -> x4

Was ich bisher habe ist:

$Id = 'x4';
$raus = array();
$tmp = $verlauf;

while(in_array($Id, $tmp))
{
	$Key = array_search($Id, $tmp);
	array_push($raus, $Key);
	unset($tmp[$key]);
	foreach (array_reverse($tmp) as $keys => $value) {
		if ($value == $Key ) {
			$Key = array_search($Key, $tmp);
			array_push($raus, $Key);
			unset($tmp[$Key]);
		}
	}
}
array_push($raus, $Id);

damit finde ich schon den Weg raus:

x1, x2

leider erkennt er nicht, dass er auch von

x3 und x5

zu x4 kommen kann

jemand eine Idee?

Danke schonmal

DadyCool

 

[Darklord]

Die Kanten einfach "rückwärts" betrachten.

In dem man x4 als Wurzel deklariert und eine Tiefensuche oder Breitensuche anwendet.

 

[tobomator]

jo eine rückwärtsuche wäre hier das bessere.
Oder du müsstest sukzessive durchgehen...
für jeden eintrag in array als $key=>$value paar nachschauen:
ist $value === gessucht
ja ? dann füge $key in lösungsarray ein
nein ? dann füge $value in tmpvar ein und mache folgendes:
gibt es ein wert gesucht im array (array_key_exists) wenn ja, dann prüfe deren value und so weiter
nein, füge value an tmpvar hinten an mit , # so entsteht eine kleine liste - der weg zum gesucht
wenn nichts gefunden wird, dann wird tmpvar gelöscht und zurück in die foreach schleife