Graphentheorie

• Knoten (meist Zahlen)
• Kanten: Paare von Knoten (orientiert oder nicht)
• Weg: Folge von Knoten, die durch Kanten verbunden sind.
• Zusammenhängender Graph: Zwischen jedem Paar von Knoten existiert ein Weg
• Zyklus: Weg mit identischem Start- und Endknoten

• Zusammenhängender Graph ohne Zyklus.

Für Bäume beweisen Sie:

• Es gibt exakt einen Weg zwischen zwei beliebigen Knoten
• Ein Baum mit $n$ Knoten hat $n-1$ Kanten.

• Im einfachsten Fall ein Baum (keine Zyklen, garantierter Weg).
• Grundstuktur: Raster, Knoten sind ganzzahlige Koordinatenpunkte, Kanten achsenparallel, Länge 1.

Input Graph mit Knotenmenge $V$ und Kantenmengen $E$, Startknoten $s$, Zielknoten $z$.

Output Weg von $s$ nach $z$

1. Markiere alle Knoten mit None.
2. Setze Todo-Liste $t=(s)$
3. Solange $z$ mit None markiert ist, wiederhole:
   1. entferne einen Knoten $v$ aus $t$
   2. für alle Nachbarn $u$ von $v$, die noch mit None markiert sind:
      1. markiere $u$ mit $v$ (als Vorgäger)
      2. füge $u$ der Liste $t$ hinzu.
   3. Wenn $t$ leer ist, return “Kein Weg von $s$ zu $z$
4. Weg $w$ = $(z)$
5. Setze $v=z$
6. Solange $v \neq s$, wiederhole:
   1. Setze $v$ = Markierung von $v$
   2. Füge $v$ vorne zum Weg $w$ hinzu
7. return Weg $w$

Je nachdem, wie die Todo-Liste gehandhabt wird, erhält an verschiedene Algorithmen:

• Wird immer der zuletzt eingefügte Knoten entfernt, erhält man die Tiefensuche (Depthfirst search). D.h. man geht erst soweit in die Tiefe wie möglich.
• Werden die Knoten in der Reihenfolge entfernt, in der sie eingefügt wurden, erhält man die Breitensuche (Breadhfirst search). D.h. man besucht die Knoten in der Reihenfolge ihrer Entfernung vom Startknoten aus (gemessen in Anzahl Kanten).
• Die Knoten nach einem Kriterium ausgewählt. Wählt man z.B. den nächsten Knoten bezüglich seiner Distanz zum Startknoten aus, erhält man Dijkstras Algorithmus zur Bestimmung des kürzesten Weges (Voraussetzung sind positive Kantenlängen). Addiert man dazu zusätzlich eine unterschätzende Distanz zum Zielknoten, erhält man den $A^\star$-Algorithmus.

Diese Algorithmen werden z.B. auch von Webcrawlern verwendet und finden (in massiv effizienteren Formen) in Navigationsgeräten anwendung.

Wird kein Zielknoten festegelegt, erzeugt obiger Algorithmus exakt einen Weg vom Startknoten zu jedem anderen Knoten, d.h. ein Baum. Wird der nächste Knoten “zufällig” aus der Todo-Liste ausgewählt, entsteht ein “zufälliger” Baum und damit ein zufälliges Labyrinth.

Damit ansprechende Labyrinthe entstehen, darf nicht jeder Knoten sofort vollständig abgearbeitet werden, sondern nur ein Weg. Danach wird der Knoten wieder in die Todo-Liste eingefügt.

Der Zufall kann so gesteuert werden, dass “ansprechende” Labyrinthe entstehen.

1. Start mit $n$ Knoten, keine Kanten.
2. Wiederhole $n-1$ mal:
   1. Man wählt zwei Knoten $u$, $v$ aus, die nicht in der gleichen zusammenhängenden Komponente sind.
   2. Man verbindet $u$, $v$ mit einer Kante

laby.py

import random
 
class Laby:
    # directions, trigonometric
    VECS=[[1,0], [0,1], [-1,0], [0,-1]];
    def __init__(self, width, height):
        self.width = width
        self.height = height
        # Gibt für jede Koordinate an, ob nach links und nach unten gegangen werden kann.
        # Z.B. self.canGo[3,4,0] ist True, wenn von 3,4 auf 4,4 gegangen werden kann
        # self.canGo[3,4,1] ist False, wenn nicht von 3,4 auf 3,5 gegangen werden kann.
        self.canGo = [[[False, False] for y in range(self.height)] for x in range(self.width)]
 
        # Mark enthaelt ein String der Laenge 1, der bei der Ausgabe mit ausgegeben wird.
        self.mark = [[" " for y in range(self.height)] for x in range(self.width)]
 
 
 
    def clearMarks(self):
        for y in range(self.height):
            for x in range(self.width):
                self.mark[x][y]=" "
 
    # c ist ein Koordinatenpaar        
    def onBoard(self,c):
        return c[0]>=0 and c[0]<self.width and c[1]>=0 and c[1]<self.height
 
 
    def move(self, c,d):
        return (c[0]+Laby.VECS[d][0], c[1]+Laby.VECS[d][1])
 
    # c ist ein Koordinatenpaar, 
    # gibt True zurueck, wenn von c in Richtung d gegangen werden kann.
    def edge(self, c, d):
        if self.onBoard(c) and self.onBoard(self.move(c,d)):
            if d>1:
                c = self.move(c,d)
                d-=2
            return self.canGo[c[0]][c[1]][d]
        return False
 
 
    def setEdge(self, c,d, value=True):
         if self.onBoard(c) and self.onBoard(self.move(c,d)):
            if d>1:
                c = self.move(c,d)
                d-=2
            self.canGo[c[0]][c[1]][d] = value
 
    def __str__(self):
        res = "+" + ("---+"*self.width)+"\n"
        for y in range(self.height):
            line1 = "|"
            line2 = "+"
            for x in range(self.width):
                line1 += " "+self.mark[x][y]+" "
                line1 += " " if self.edge((x,y),0) else "|"
                line2 += "   +" if self.edge((x,y),1) else "---+"
            res+=line1+"\n"+line2+"\n"
        return res
 
 
 
 
# Nur wenn Datei dekt ausgefuehrt wird:    
if __name__== "__main__":
    l = Laby(12,12);
    print(l)