✔ Sortieren mit voneinander abhängigen Werten

[NTDY]

Ich habe das folgende Array:

<?php
	$array = array(	
		'Start' => 	'',
		'A' => 			array('Start'),
		'B' => 			array('Start'),
		'C' => 			array('A','Start'),
		'D' => 			array('B','Start'),
		'E' => 			array('C','A'),
		'F' => 			array('Start','B','C'),										
	);
?>

Nun soll dieses Array hintereinanderweg sortiert werden. Dabei soll es folgende Abhängigkeit geben: "Ist ein Wert A von anderen Werten B...Z abhängig, so soll Wert A aufgezählt werden, nachdem die abhängigen Werte vorher aufgezählt wurden.
Die Reihe soll hintereinanderweg aufgebaut werden und es kann mehere Möglichkeiten geben. Eine Variante wäre besipielsweise:

Start
|
A (da abhaengig von Start)
|
B (da abhaengig von Start)
|
C (da abhaengig von Start und A)
|
D (da abhaengig von Start und B)
|
E (da abhaengig von A und C)
|
F (da abhaengig von Start, B und C)

Wie heißt so ein Sortieralgorithmus oder hat jemand schon so etwas einmal implementiert und kann ein Beispiel hier posten?

 

[Yaslaw]

Wenn du in C etc. den Start weglässt und nur den direkten Parent speicherst heisst das 'Adjacency Tree'

Falls du die Daten aus einer DB hast:
MySQL Hierarchie Baum (Adjacency Tree) auslesen

 

[NTDY]

Okay. Ich dachte, dass Adjacency Tree beruht immer auf nur einem abhängigen Wert. Ich habe ja manchmal 1, 2 oder vielleicht maximal 5. Gilt es dann immer noch?

Ich glaube, dass es nicht als Adjanzenzbaum / -liste aufgebaut werden kann, da ich spätestens bei "F" einen Kreis habe.

      Start
      /   \
     A   / B
     |  F  |
     C-/   D
     |
     E

Lösung gefunden. Es handelt sich um die topologische Sortierung. Hier ist sogar ein lauffähiges Beispielskript: https://www.calcatraz.com/blog/php-topological-sort-function-384