Algorithmus zur Überprüfung eines Graphen(azyklisch) |
| 21.06.2005, 09:58 | Bonkers | Auf diesen Beitrag antworten » |
| Algorithmus zur Überprüfung eines Graphen(azyklisch) ich habe ein Problem mit dieser Aufgabe und hoffe hier eine Hilfestellung zu bekommen. Eine Lösung erwarte ich nicht, wenn mir jemand nur einen Hinweis geben könnte wäre ich schon froh: Gegeben sei ein ungerichteter Graph mit n Ecken: a) Skizzieren Sie einen Algorithmus mit einer Komplexität von O(n) (im „Worst Case“), der den Graphen daraufhin testet, ob er azyklisch ist, also keine Kreise besitzt (Antwort: „ja“ oder „nein“). Nehmen sie dabei an, dass der Graph durch Nachbarschaftslisten repräsentiert ist. Meine Überlegung war bisher, ich muss folgendes Nachweisen: Ein geschlossener Weg (also ein geschlossener Kantenzug, der keine Ecke mehrmals enthält) wird als Kreis bezeichnet. Also erste Kante gleich letzte Kante (geschlossener Weg - wie das bei einem ungerichteten Graphen?) und keine Ecke kommt mehrmals vor. Dazu habe ich mir schon einen Algorithmus überlegt, der überprüft ob keine Ecke mehr als 2 Verbindungen/Kanten zu anderen Ecken hat. Ideen 
?Vielen Dank und Gruß Bonkers |
||
|
|
Verwandte Themen
| Die Beliebtesten » |
|
| Die Größten » |
|
| Die Neuesten » |
|
