Durchläufe durch Graphen WS13-14
Inhaltsverzeichnis |
Einleitung
Für einen Graphendurchlauf bzw. das Durchsuchen eines Graphen gibt es viele Verfahren und Darstellungsmethoden, die vor allem die Basis für Graphenalgorithmen bilden. Beim Durchsuchen werden systematisch alle Kanten eines Graphen verfolgt und die Knoten aufgesucht. Wird ein Durchsuchungsalgorithmus auf einen Graphen angewandt, kann dieser Aufschluss über die Struktur dessen geben. Einfach weiterentwickelte Durchsuchungsalgorithmen werden als Graphenalgorithmen bezeichnet. Beispiele sind die Tiefen- und Breitensuche, die in der Vorlesung zur Systematischen Suche schon kurz behandelt wurden.
Breitensuche
Tiefensuche
Topologisches Sortieren
Starke Zusammenhangskomponenten
Übungen
Literaturverzeichnis
- Cormen, Thomas; Leiserson, Charles; Rivest, Ronald; Stein, Clifford: Algorithmen, eine Einführung; Oldenbourg Verlag, 2007
- Güting, Ralf Hartmut: Datenstrukturen und Algorithmen; B.G. Teubner Stuttgart, 1992
http://wwwiti.cs.uni-magdeburg.de/iti_db/lehre/algds0506/handout2-9.pdf http://www.stormware-computer.de/script/kapitel_4_1.pdf http://whz-cms-10.zw.fh-zwickau.de/sibsc/lehre/ss10/ad/v13.pdf