Haskell-Forum
Gepostet: |
Eulerwege berechnen | ||||||||||
| Hab noch ne andere Frage. Es geht darum Eulerwege zu berechnen. Hierbei handelt es sich auch um ungerichtete Graphen. Soll heißen ich gebe beispielsweise eulerweg [(0,1)] und erhalte [0,1,0] also in der Form eulerweg [(Int,Int)] -> [[Int]] nun hab ich leider keine Ahnung wie ich das genau umsetzten soll |
|||||||||||
| Zum Seitenanfang | |||||||||||
Gepostet: |
|||||||||||
Machst dir heute wohl nen gemütlichen Haskell-Sonntag, was!?  Also angenommen dein Graph hat garantiert einen Eulerweg, der den gesamten Graphen genau abdeckt, und es ist egal, in welcher Reihenfolger der Weg "bereist" werden soll, dann sollte folgendes Verfahren funktionieren: Erstmal sortierst du dir alle Kanten so, dass bei zwei benachbarten Kanten e und e' immer snd e == fst e' gilt. [(1,2), (3,2), (2,1), (2,3)] würde z.B. zu [(1,2),(2,3),(3,2),(2,1)] sortiert werden. Die fertige Liste ist dann praktisch schon ein Eulerweg, wo du nur noch der Reihe nach die besuchten Knoten in eine Liste schreiben brauchst. Das Problem beim Sortieren der Liste ist, du kannst unter Umständen in eine Sackgasse geraten, z.B. darf in meinem Beispiel die zweite Kante nicht (2,1) sein, weil du von dem Knoten 1 dann nicht mehr wegkommst. Beim Auswählen eines Knoten musst du also immer prüfen, ob die restliche Kantenliste und der aktuelle Knoten noch zusammenhängend sind, d.h. über Kanten verbunden sind. |
|||||||||||
| Zum Seitenanfang | |||||||||||
