Graphtraversierungen – Akademischer Tag 4

Nachdem wir im letzten Artikel geklärt haben, was Graphen sind und wie man sie im Computer darstellen kann, geht es heute darum, wie man Graphen traversieren kann, d.h. es geht darum, jeden Knoten des Graphen zu besuchen. Hierfür gibt es zwei fundamentale Strategien: Die Breitensuche und die Tiefensuche.

Der Einfachheit halber werde ich Breiten- und Tiefensuche nur auf folgenden Graphen anwenden:

Beispielgraph

Es handelt sich dabei um einen ungerichteten und zusammenhängenden Graphen. Die Verwendung eines ungerichteten Graphen macht dabei keinen wesentlichen Unterschied, da die gesamte Argumentation sehr leicht auf gerichtete Graphen übertragen werden kann. Für einen ungerichteten Graphen G = (V,E) bedeutet der Begriff „zusammenhängend“ nichts anderes, als dass für je zwei Knoten v, w ∈ V (mindestens) einen Pfad von v nach w bzw. von w nach v existiert. Der Vollständigkeit halber sollte noch eine Definition für einen Pfad angegeben werden: Ein Pfad ist ein Tupel (v₁, v₂, …, v_n) mit {{v₁,v₂}, {v₂,v₃}, …, {v_n-1, v_n}} ⊆ E und v_i ≠ v_j für i ≠ j. Anschaulich: Ein Pfad ist eine Folge von unterschiedlichen Knoten, bei dem für alle benachbarten Knoten gilt, dass sie miteinander verbunden sind. Da Breiten- und Tiefensuche in PHP implementiert werden, bietet es sich an, den Beispielgraphen als Adjazenzliste in PHP-Code darzustellen:

$adj = array(
	'A' => array('B','C','D'),
	'B' => array('A','E','H'),
	'C' => array('A','D','F','G'),
	'D' => array('A','C','E','G','H','I'),
	'E' => array('B','D','H'),
	'F' => array('C','G','I'),
	'G' => array('C','D','F','I'),
	'H' => array('B','D','E','I'),
	'I' => array('D','F','G','H')
);

Traversiert man einen Graphen, so erhält man eine Traversierungsreihenfolge und einen Traversierungsbaum. Zwar ist der Begriff eines Baums geläufig, aber dennoch möchte ich ihn präzise definieren: Ein ungerichteter Baum ist ein Graph, bei dem es zwischen je zwei Knoten x und y genau einen Pfad von x nach y bzw. von y nach x gibt. Diese Definition lässt sich leicht auf gerichtete Graphen übertragen: Ein gerichteter Baum, dessen Kantenrichtung zu den Blättern zeigt, ist ein Graph, bei dem es für jeden Knoten x genau einen Pfad von der Wurzel zu x gibt. Blätter sind hierbei die Knoten, die keine ausgehende Kanten haben, und die Wurzel ist der (einzige) Knoten, der keine eingehende Kante hat.

Nachdem alle für das Verständnis notwendigen Begriffe erläutert wurden, können wir mit der Breitensuche (engl. Breadth First Search) beginnen, die im vorangegangen Artikel bereits erwähnt wurde. Der Einfachheit halber wird die BFS-Prozedur, die ich vorstelle, lediglich die Reihenfolge der Knoten darstellen, in der sie besucht wurden – also das Aufstellen der Traversierungsreihenfolge.

Das Herz der BFS-Prozedur ist die Verwendung einer Warteschlange (SplQueue), die nach dem FIFO-Prinzip arbeitet, d.h. für je zwei Knoten, die in die Warteschlange eingefügt wurden, gilt, dass derjenige, der vorher eingefügt wurde, auch vor dem anderen Knoten entnommen wird. Dadurch entsteht das Verhalten, das man als Breitensuche charakterisiert: Wird ein Knoten bearbeitet, so werden alle seine benachbarten (und noch nicht besuchten) Knoten der Breite nach in die Warteschlange eingefügt und sie werden später in derselben Reihenfolge entnommen.

Natürlich benötigt die BFS-Prozedur nicht nur einen Graphen, auf dem sie ausgeführt werden soll, sondern auch einen Startknoten, der mit $start bezeichnet wird.

function bfs ($adj, $start) {
	$const = function($val) { return function($x) use ($val) { return $val; };};
	$base = array_flip(array_keys($adj));
	$result = array_map($const(0), $base);
	$visited = array_map($const(false), $base);

	$queue = new SplQueue();
	$queue->enqueue($start);
	$visited[$start] = true;
	$number = 1;

	foreach($queue as $item) {
		$result[$item] = $number++;

		foreach($adj[$item] as $next) {
			if(!$visited[$next]) {
				$queue->enqueue($next);
				$visited[$next] = true;
			}
		}
	}

	return $result;
}

bfs($adj, ‚A‘) ergibt array(‚A‘ => 1, ‚B‘ => 2, ‚C‘ => 3, ‚D‘ => 4, ‚E‘ => 5, ‚F‘ => 7, ‚G‘ => 8, ‚H‘ => 6, ‚I‘ => 9). Aber nicht nur die BFS-Nummerierung, sondern auch der sog. Traversierungsbaum ist interessant. Die Kantenrelation dieses Baums lässt sich folgendermaßen beschreiben: Eine gerichtete Kante (x,y) existiert genau dann, wenn y beim Bearbeiten von x in die Warteschlange eingefügt wurde. Dass es sich dabei um einen Baum handelt, lässt sich leicht mit der oben angegebenen Definition erklären. Da jeder Knoten genau einmal eingefügt wird, hat jeder Knoten (mit Ausnahme der Wurzel) maximal eine eingehende Kante. Dadurch kann es von der Wurzel zu jedem Knoten maximal einen Weg geben und die Existenz eines solchen Wegs ist bei einem zusammenhängenden Graphen trivialerweise erfüllt. Folglich gibt es für jeden Knoten x genau einen Weg von der Wurzel zu x.

Traversierungsbaum

Der Anschaulichkeit halber erhält jeder Knoten eine neue Bezeichnung, die sich aus seiner alten Bezeichnung und BFS-Nummerierung zusammensetzt. Auffällig ist dabei, dass die Zahlenfolge in jeder Ebene von links nach rechts aufsteigend ist. Diese Eigenschaft lässt sich verallgemeinern: Sei (w,1) die Wurzel und seien (x,n) und (y,m) zwei beliebige Knoten im Traversierungsbaum, so gilt, wenn  n < m, dann gibt es keinen Weg von w nach y, der kürzer ist als der Weg von w nach x. Weshalb gilt diese Eigenschaft? Das lässt sich aus der FIFO-Eigenschaft folgern: Beginnend mit Startknoten werden alle Knoten, die direkt mit dem Startknoten verbunden sind, in die Warteschlange eingefügt. D.h. alle Knoten in der Warteschlange haben eine Entfernung, also die Anzahl der Kanten zwischen zwei Knoten, von 1, da sie direkt mit dem Startknoten verbunden sind. Werden diese Knoten abgearbeitet, werden ans Ende der Warteschlange alle Knoten eingefügt, die eine Entfernung von 2 zum Startknoten haben. Dieses Verfahren wird solange fortgesetzt wie es Knoten in der Warteschlange gibt. Anhand dieser Eigenschaft lässt sich auch erklären, weshalb die Breitensuche das Kürzester-Weg-Problem auf ungewichteten Graphen löst. Das Kürzester-Weg-Problem lässt sich auf gewichteten Graphen übrigens sehr ähnlich lösen: Statt einer Warteschlange wird eine Prioritätswarteschlange verwendet, in der die Knoten nach der Entfernung (anhand der Kantengewichte) sortiert sind. Eine Einschränkung muss hierbei allerdings gemacht werden: Negative Kantengewichte funktionieren mit obigen Ansatz im Allgemeinen nicht. In der englischen Wikipedia finden sich weitere Anwendungen für Breitensuche.

Im Gegensatz zur Breitensuche verwendet die Tiefensuche (engl. Depth First Search) einen Stapel (SplStack) oder wird rekursiv implementiert, woraus das LIFO-Prinzip folgt. Konkret bedeutet das, dass man alle benachbarten Knoten auf einem Stapel speichert und das Element auf dem Stapel als nächsten Knoten wählt. Durch die Verwendung des Stapels liegt immer ein Knoten oben, der möglichst tief liegt. Um dabei nicht zu sehr an die Vorstellungskraft zu appellieren: Ein Knoten x liegt genau dann tiefer als y, wenn der Pfad, der zu x geführt hat, länger ist als derjenige, der zu y geführt hat. D.h. man geht solange in die Tiefe bis es nicht mehr möglich ist. Von diesem Knoten aus geht man wieder zurück, bis man zu einem Knoten gelangt, an dem man die Tiefensuche fortsetzen kann. Das lässt sich sehr schön an der DFS-Nummerierung zeigen: dfs($adj, ‚A‘) gibt array(‚A‘ => 1, ‚B‘ => 2, ‚C‘ => 5, ‚D‘ => 4, ‚E‘ => 3, ‚F‘ => 6, ‚G‘ => 7, ‚H‘ => 9, ‚I‘ => 8 ) zurück. Beim Nachvollziehen anhand des Beispielgraphen fällt einem noch ein anderer Sachverhalt auf: Es gibt einen Pfad, mit dem man alle Knoten erreichen kann, was im Allgemeinen nicht der Fall ist. Beispielsweise gibt es für Bäume einen ähnlichen Traversierungsbaum wie er bei der Breitensuche entstanden ist. Eine konkrete Implementierung der DFS-Prozedur könnte folgendermaßen aussehen:

function dfs ($adj, $start) {
	$const = function($val) { return function($x) use ($val) { return $val; };};
	$base = array_flip(array_keys($adj));
	$result = array_map($const(0), $base);
	$visited = array_map($const(false), $base);

	$stack = new SplStack();
	$stack->push($start);
	$number = 1;

	while(!$stack->isEmpty()) {
		$item = $stack->pop();

		if(!$visited[$item]) {
			$result[$item] = $number++;
			$visited[$item] = true;

			foreach(array_reverse($adj[$item]) as $next) {
				$stack->push($next);
			}
		}
	}

	return $result;
}

Diese Implementierung benutzt einen Stapel, um den Gegensatz zur Breitensuche bzw. der Warteschlange zu verdeutlichen. Außerdem spart man durch das Verwenden eines Stapels entweder eine weitere Funktion oder überflüssige Überprüfungen der übergebenen Werte. Weitere Unterschiede zur Breitensuche sind zum einen der Zeitpunkt der Unterscheidung, ob ein Knoten bereits besucht wurde, und zum anderen die Reihenfolge, in der die Knoten auf den Stapel gelegt werden. Die umgekehrte Reihenfolge ist zwar nicht notwendig, aber sorgt dafür, dass – analog zur Breitensuche – immer der Knoten, der in der Adjazenzliste am weitesten links steht, zuerst besucht wird. Hingegen ist der Zeitpunkt der Überprüfung essentiell für die Tiefensuche. In der Breitensuche wird ein Knoten genau dann in die Warteschlange eingefügt, wenn er noch nicht in der Warteschlange ist. Bei der Tiefensuche hingegen möchte man dieses Verhalten nicht: Befinden wir uns gerade bei der Bearbeitung von Knoten y und existiert ein (unbesuchter) Knoten x, der von y aus erreichbar ist, bereits auf dem Stapel, so bedeutet es, dass es einen Knoten z gibt, von dem x aus erreichbar ist, der aber höher als y liegt. Würde man x in diesem Fall nicht (erneut) auf den Stapel legen, würde es dem Prinzip Tiefensuche widersprechen, da man die Knoten in der Tiefe sucht. Anschaulich  könnte x = D, y = E und z = A im Beispielgraphen gelten. Nach dem ersten Schritt, also beim Knoten A, werden B, C, D auf den Stapel gelegt und bei B wird in der Tiefe gesucht. Nach einem weiteren Schritt und weiteren Knoten auf dem Stapel tritt obiges Verhalten auf, d.h. D soll beim Besuch von E auf den Stapel gelegt werden. Würde D also nicht von E aus besucht werden, würde das nicht der Tiefensuche entsprechen.

Unter den möglichen Anwendungen für die Tiefensuche möchte ich besonders den Backtracking-Algorithmus hervorheben, der sich sehr gut zum Problemlösen eignet. Zwar wird Backtracking meist nicht explizit auf einem Graphen ausgeführt, aber er arbeitet nach dem Prinzip der Tiefensuche, da er bei der Suche nach einer Lösung möglichst viele Schritte in die Tiefe geht und bei einem Fehler zur letzten Verzweigung zurückkehrt um von dort aus wieder in die Tiefe zu gehen.

Anmerkung: Der PHP-Code funktioniert aufgrund der Nutzung von Closures mit PHP 5.3 und höher. Außerdem funktionieren die Algorithmen derzeit nur auf zusammenhänden Graphen. Bei nicht zusammenhängen Graphen muss man eine weitere Schleife hinzufügen, sodass alle Knoten erfasst werden. Dabei entsteht natürlich kein Traversierungsbaum mehr, sondern ein sog. Traversierungswald – also ein Graph dessen Zusammenhangskomponenten Bäume darstellen.