Tilman
48 lines
2.1 KiB
PHP
48 lines
2.1 KiB
PHP
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">
|
|
<html>
|
|
<head>
|
|
<meta http-equiv="content-type" content="text/html; charset=ISO-8859-1">
|
|
<link rel="stylesheet" type="text/css" media="all" href="stylesheet.css">
|
|
<title>Tiefensuche und Breitensuche</title>
|
|
</head>
|
|
<body>
|
|
<span id="menu"><a href="index.php">zurück zur Liste</a></span>
|
|
|
|
<div id="buttons">
|
|
<form action="edit.php" method="POST">
|
|
<input type="hidden" name="filename" value="<?php echo $_SERVER['SCRIPT_FILENAME']?>">
|
|
<p>
|
|
<input type="submit" value="Seite bearbeiten">
|
|
</p>
|
|
</form>
|
|
</div>
|
|
|
|
<h1>Tiefen- und Breitensuche</h1>
|
|
|
|
Tiefen- und Breitensuche sind Verfahren zum Traversieren von Graphen. Als Ergebnis eines zusammenhängenden Graphen erhält man einen aufspannenden Baum.<br><br>
|
|
|
|
<h3>Breitensuche</h3>
|
|
Die <b>Breitensuche (BFS - breadth-first-search)</b> ist ein Algorithmenmuster, das die Knoten eines Graphen nach der Entfernung von einem Startknoten geordnet durchläuft.<br>
|
|
Zuerst werden alle von diesem Startknoten direkt durch eine Kante erreichbaren Knoten bearbeitet, danach die mit zwei Kanten Entfernung, dann die mit drei usw.<br><br>
|
|
|
|
<h3>Tiefensuche</h3>
|
|
Mit der <b>Tiefensuche (DFS - depth-first-search)</b> geht man so weit wie möglich einen gewählten Pfad entlang. Wenn man am Ende eines Zweiges angekommen ist, geht man schrittweise zurück, bis man in einen bislang unbesuchten Teilbaum absteigen kann. Ist man wieder am Startknoten angelangt und es gibt keine unbesuchten Knoten, die mit dem Startknoten durch eine Kante verbunden sind, dann ist man fertig.<br>
|
|
Dieseas Verfahren nennt man <b>Backtracking</b>: Man geht solange man kann, wenn man nicht mehr weiter kommt, geht man zurück bis man einen anderen Weg findet.<br><br><br>
|
|
|
|
|
|
<b>Beispiel:</b><br>
|
|
<table>
|
|
<tr>
|
|
<td>Beispielgraph</td>
|
|
<td>Breitensuche</td>
|
|
<td>Tiefensuche</td>
|
|
</tr>
|
|
<tr>
|
|
<td><img src="tubsuche.gif"></td>
|
|
<td><img src="breitensuche.gif"></td>
|
|
<td><img src="tiefensuche.gif"></td>
|
|
</tr>
|
|
</table>
|
|
|
|
</body>
|
|
</html> |