AuK/Durchläufe durch Graphen SS12
Aus ProgrammingWiki
Wiki-Quelltext dieser Seite.
<language>Java</language>
Der '''Graphendurchlauf''' (engl. ''graph traversal'') bildet die Grundlage vieler Graphenalgorithmen. Die Idee besteht darin, alle Knoten bzw. Kanten in einem Graphen systematisch zu besuchen, um beispielsweise Informationen über dessen Struktur zu sammeln.
[[Bild:Croxeldyffic_Labyrinth02.png|thumb|200px|right|Ein Labyrinth mit Startpunkt (grün) und Ziel (rot)]]
Als Motivation für die Lösung dieses Problems soll folgendes Beispiel dienen: Eine Person befindet sich in einem Labyrinth, und sucht einen Ausgang, indem sie alle möglichen Kreuzungen von Gängen in Augenschein nimmt. Übertragen auf die Graphentheorie, existieren hierfür zwei bekannte algorithmische Lösungsverfahren, die Hauptgegenstand dieser Vorlesung sind. In unserem Beispiel sind die Gänge des Labyrinths die Kanten und alle Kreuzugen die Knoten des Graphen.
Stellen wir uns vor, die eingeschlossene Person folgt einem bestimmten Gang solange, bis sie in eine Sackgasse gerät, zur letzten Kreuzung zurückkehrt und einem anderen Weg auf die gleiche Art verfolgt. Dieses systematische Vordringen in die "Tiefe" nennen wir '''Tiefensuche'''.
Sucht jedoch eine Gruppe von Leuten den Ausgang, so ist es wahrscheinlicher, dass sie gemeinsam vom Startpunkt ausschwärmen in die "Breite" vordringen. Analog dazu sprechen wir von einer '''Breitensuche'''.
Am Ende des Kapitels wird es uns möglich sein, das Labyrinth-Problem mithilfe der beiden Algorithmen zu lösen.
<pre>
<b>Note:</b> Durchlauf (traversal) $\neq$ Suche (search)!
Achso, und laby etwas einfacher, vllt #6, zu demo-zwecken...
Applets:
//note to self2: applet: http://www.cosc.canterbury.ac.nz/mukundan/dsal/GraphAppl.html meh~
//note to self2.1: dfs-applet: http://www.lupinho.net/lupinho.de/gishur/html/DFSApplet.html
//note to self2.2: bfs-applet: http://www.lupinho.net/lupinho.de/gishur/html/BFSApplet.html
//w00t~
//note to self3: eu/hm-applets zum knobeln: http://www.cut-the-knot.org/Curriculum/Combinatorics/GraphPractice.shtml
//note to self4: laby-applet: http://www.swisseduc.ch/informatik/diskrete_mathematik/tiefensuche_labyrinth/applet.html
</pre>
<popup title="Info">
<p style="padding-left:100px; padding-right:100px" align="justify">
Traversal simply means moving from one node to the next. Generally one searches by traversing the list, comparing each node's data with a given datum, either to return a pointer to a single matching node, or to return a list of matching nodes (copied from the list being searched), or simply to collect data about the matching nodes (such as a count of all the matching nodes).
</p>
</popup>
= Wiederholung =
Zum Verständnis der später vorgestellten Graphenalgorithmen sind grundlegende Kenntnisse über Graphen und spezielle Datenstrukturen notwendig, die jedoch bereits Themen in vorigen Veranstaltungen waren und im Folgenden nur aufgefrischt werden sollen.
== Graphrepräsentation ==
<div style="background-color:#EEE">
$\rightarrow$ siehe Vorlesung [http://programmingwiki.de/AuK/Graphrepr%C3%A4sentationen_SS12 Graphrepräsentation]
</div>
'''Kontrollfragen:'''
<ol>
<li> <b>Was ist der Unterschied zwischen <i>gerichteten</i> und <i>ungerichteten</i> Graphen?</b>
<popup title="Lösung">
<ol>
<div align="center">
<gallery widths="300px" heights="300px">
Bild:Croxeldyffic_G01.PNG|Ein ungerichteter Graph
Bild:Croxeldyffic_G01_1.PNG|Ein gerichteter Graph
</gallery>
</div>
In einem <i>ungerichteten</i> Graphen kann eine Kante $(u,v)$ in beliebiger Richtung überquert werden, während in einem <i>gerichteten</i> Graphen die zulässige Durchlaufrichtung durch einen Pfeil gekennzeichnet ist (ähnlich einer Einbahnstraße).
Will man einen ungerichteten Graphen gerichtet darstellen, so verdoppelt sich die Kantenmenge, d.h. enthält die Kantenmenge $K$ des ungerichteten Graphen die Kante $(u,v)$, muss die Kantenmenge $K$ des gerichteten Graphen die Kanten $(u,v)$ und $(v,u)$ enthalten.
</ol>
</popup>
</li>
<li><b>Welche Darstellungsformen für Graphen gibt es?</b>
<ol style="list-style-type:lower-alpha">
<li> Wie können diese im Computer realisiert werden? </li>
<li> Welche ist am besten? </li>
</ol>
<popup title="Lösung">
<ol style="list-style-type:lower-alpha">
<li>
<ul>
<li><b>Feld:</b> Ein Adjazenzfeld ist eine sehr einfache Darstellungsform, in der alle Zielknoten in einem Array geordnet nach Startknoten gespeichert werden.</li>
<li><b>Liste:</b> Eine Adjazenzliste ist eine verkettete Liste mit Nachfolgern bzw. Nachbar eines Knotens. </li>
<li><b>Matrix:</b> Eine Adjazenzmatrix ist ein mehrdimensionales ($V \times V$ mit $V$ als Knotenanzahl) Array mit booleschen Variablen, in der $a[u,v]$ auf 1 oder true gesetzt wird, wenn eine Kante $(u,v)$ existiert. Analog dazu gibt eine Inzidenzmatrix ($V \times E$-großes Array) die Inzidenzbeziehungen zwischen Knoten und Kanten in einem Graphen an.</li>
</ul>
</li>
<li> Wir vergleichen die drei bzw. vier Darstellungsformen miteinander:
<table border="1" cellpadding="1" cellspacing="3">
<tr style="background-color:#EEE">
<td> </td>
<td>Adjazenzfeld</td>
<td>Adjazenzliste</td>
<td>Adjazenzmatrix</td>
<td>Inzidenzmatrix</td>
</tr>
<tr>
<td style="background-color:#EEE">Speicheraufwand</td>
<td>$\mathcal{O}\: (|V| + |E|)$</td>
<td>$\mathcal{O}\: (|V| + |E|)$</td>
<td>$\mathcal{O}\: (|V|^2)$</td>
<td>$\mathcal{O}\: (|V| \cdot |E|)$</td>
</tr>
<tr>
<td style="background-color:#EEE">Nachbarabfrage</td>
<td>$\mathcal{O}\: (d)^*$ <br> <font size="-2">* $d$ = max. Ausgangsgrad</font> </td>
<td>$\mathcal{O}\: (d)^*$ <br> <font size="-2">* $d$ = max. Ausgangsgrad</font></td>
<td>$\mathcal{O}\: (1)$</td>
<td>$\mathcal{O}\: (|E|)$</td>
</tr>
<tr>
<td style="background-color:#EEE">Vorteile</td>
<td>+ kompakte Darstellung</td>
<td>+ kompakte Darstellung<br>+ effizient für dynamische Graphen</td>
<td>+ schneller Zugriff<br>+ effizient bei dichten Graphen<br>+ schnelles Löschen von Kanten</td>
<td>+ besser bei lichten Graphen</td>
</tr>
<tr>
<td style="background-color:#EEE">Nachteile</td>
<td>- nur für statische Graphen</td>
<td>- ineffizient für dichte Graphen</td>
<td>- hoher Speicheraufwand<br>- ineffizient bei lichten Graphen</td>
<td>- hoher Speicheraufwand bei dichten Graphen<br>- langsames Löschen von Kanten</td>
</tr>
</table>
<b>Fazit:</b> Die Anzahl der Kanten ist bei den meisten Graphen höher als die Knotenanzahl, daher ist aufgrund der schnellen Zugriffszeit die Adjazenzmatrix als Darstellungsform empfohlen.
</li>
</ol>
</popup>
</li>
</ol>
== Bäume und Preorder-Traversierung ==
<div style="background-color:#EEE">
$\rightarrow$ siehe Vorlesung [http://programmingwiki.de/AuK/Sortierte_Folgen_SS12 Sortierte Folgen]
</div>
== Datenstrukturen Stack und Queue ==
<div style="background-color:#EEE">
$\rightarrow$ siehe Vorlesung [http://programmingwiki.de/AuK/Priorit%C3%A4tswarteschlangen_SS12 Prioritätswarteschlangen]
</div>
'''Kontrollfragen:'''
<ol>
<li><b>Nach welchem Prinzip arbeitet eine Warteschlange?</b>
<popup title="Lösung">
<p>Eine Warteschlange (engl. <i>queue</i>) arbeitet nach dem FIFO-Prinzip, d.h. das Element, das zuerst in die Warteschlange abgelegt wurde, wird zuerst bearbeitet (ähnlich einer Schlange im Supermarkt).<br>
Folgende Operationen sind notwendig:
<ul>
<li>Element hinzufügen (enqueue): Das Element wird nach dem letzten Element eingefügt.</li>
<li>erstes Element anzeigen (peek): Das zuerst hinzugefügte Element wird ausgegeben.</li>
<li>Element löschen (dequeue): Das zuerst hinzugefügte Element wird ausgegeben und aus der Schlange entfernt.</li>
<li>Prüfung, ob Schlange leer ist (isEmpty)</li>
</ul></p>
'''Implementierung:'''
<code id="4f9d33b72b119">
public Object Queue()
{
int[] elemente = new int[0];
int top;
int groesse = elemente.length;
public boolean istLeer()
{
groesse = elemente.length;
return groesse == 0;
}
public int peek()
{
top = elemente[0];
return top;
}
public void enqueue(int element)
{
groesse = elemente.length;
int[] neu = new int[groesse +1];
for (int i=0; i<=groesse-1; i++)
neu[i] = elemente[i];
neu[groesse] = element;
elemente = neu;
top = elemente[0];
}
public int dequeue()
{
top = elemente[0];
groesse = elemente.length;
int[] neu = new int[groesse-1];
for(int i = 0; i < groesse-1; i++)
neu[i] = elemente[i+1];
elemente = neu;
return top;
}
return this;
}
</code>
</popup>
<run id="4fad7665d2435">
queuey01 = Queue();
queuey01.istLeer();
// queuey01.enqueue(1);
// queuey01.enqueue(2);
// queuey01.enqueue(3);
// queuey01.istLeer();
// queuey01.peek();
// queuey01.dequeue();
// queuey01.dequeue();
// queuey01.peek();
// queuey01.dequeue();
// queuey01.istLeer();
</run>
</li>
<li><b>Nach welchem Prinzip arbeitet ein Stack?</b></li>
<popup title="Lösung">
<p>Im Gegensatz zur Warteschlange arbeitet ein Stack nach dem LIFO-Prinzip, d.h. das Element, das zuletzt auf den Stack abgelegt wurde, wird zuerst bearbeitet (ähnlich einem Stapel Bücher etc.).<br>
Folgende Operationen sind notwendig:
<ul>
<li>Element hinzufügen (push): Das Element wird an erster Stelle eingefügt.</li>
<li>erstes Element anzeigen (peek): Das zuletzt hinzugefügte Element wird ausgegeben.</li>
<li>Element löschen (pop): Das zuletzt hinzugefügte Element wird ausgegeben und aus dem Stack entfernt.</li>
<li>Prüfung, ob Stack leer ist (isEmpty)</li>
</ul></p>
'''Implementierung:'''
<code id="4f986cf808f9a">
public Object Stack()
{
int groesse = 20;
int[] elemente = new int[groesse];
int top = -1;
public void push(int j)
{elemente[++top] = j;}
public int pop()
{return elemente[top--];}
public int peek()
{return elemente[top];}
public boolean istLeer()
{return (top == -1);}
return this;
}
</code>
</popup>
<run id="4fad7665d24cb">
stacky01 = Stack();
stacky01.istLeer();
// stacky01.push(1);
// stacky01.push(2);
// stacky01.push(3);
// stacky01.istLeer();
// stacky01.peek();
// stacky01.pop();
// stacky01.pop();
// stacky01.peek();
// stacky01.pop();
// stacky01.istLeer();
</run>
</li>
</ol>
= Grundlagen zum Graphendurchlauf =
== Allgemeiner Durchlauf-Algorithmus ==
'''Unsere zentrale Frage lautet: <i>Wie können wir die Knoten eines Graphen durchlaufen, sodass jeder Knoten mindestens einmal besucht wird?</i>'''
Um am Ende eine vernünftige Durchlaufordnung angeben zu können, überlegen wir uns folgendes Verfahren:
<ul>
<li> <b>Eingaben: </b>
<ol>
<li> Graph $G$ als Adjazenzlisten- oder -matrixdarstellung</li>
<li> eine Menge von Knoten $v \in V$ mit den Zuständen $unbesucht$ und $besucht$</li>
<li> eine Arbeitsliste $L$, die besuchte aber noch nicht abgearbeitete Knoten beinhaltet.</li>
</ol>
</li>
<li> <b>Algorithmus:</b>
<ol>
<li>Initialisierung: nur der Startknoten $v$ ist mit $besucht$ markiert und befindet sich in der Arbeitsliste $L$</li>
<li>solange $L$ nicht leer ist:
<ol>
<li> wähle einen Knoten $v$ aus $L$</li>
<li> wähle und markiere einen unbesuchten Nachbarn $u$ von $v$ als besucht und speichere $u$ in die Arbeitsliste $L$</li>
<li> falls $v$ keine unbesuchten Nachbarn besitzt, entferne $v$ aus $L$<br><br></li>
</ol>
</ol>
<div style="background-color:#EEE">
'''Algorithmus:''' ''Graphendurchlauf_allgemein (Graph G, Knoten v $\in$ V(G), Arbeitsliste L)'' <br>
<math>
\begin{array}{l|l}
1 & v \leftarrow besucht\\
2 & L \leftarrow L \oplus v\\
3 & \mathbf{while}\; (L \neq\: \emptyset)\; \mathbf{do} \\
4 &\;\;\;\;\; \text{\small waehle Knoten } v \in L \\
5 &\;\;\;\;\;\; \mathbf{if}\; (\!\text{\small es gibt } u \in V(G) \text{\small mit } u=Nachbar\; von\; v \text{\small und } u=unbesucht)\; \mathbf{then} \\
6 &\;\;\;\;\;\;\;\;\;\;\;\; u \leftarrow besucht\\
7 &\;\;\;\;\;\;\;\;\;\;\;\; L \leftarrow L \oplus u\\
8 &\;\;\;\;\;\; \mathbf{else}\; L \leftarrow L \ominus u \\
\end{array}
</math><br>
'''end''' ''Graphendurchlauf_allgemein''
</div></li>
</ul>
== Die Arbeitsliste $L$ ==
Die Art und Weise wie die einzelnen besuchten Knoten in die Arbeitsliste $L$ eingefügt werden sollen, ist beim Graphendurchlauf von großer Bedeutung. Hierfür gibt es zwei Möglichkeiten.
=== Die Arbeitsliste als Stack ===
=== Die Arbeitsliste als Queue ===
== Unsere interne Graphenrepräsentation ==
* definitionen von graph, vertex, edge und was sonst nicht alles
* kleine demonstrationen
= Tiefensuche =
*allgemeines
== Iterativ mit Stack ==
== Rekursiver Tiefen-Durchlauf-Algorithmus ==
Um alle Knoten in einem Graphen durchlaufen und am Ende eine vernünftige Durchlaufordnung angeben zu können, überlegen wir uns folgendes Verfahren:
<ul> <li> Eingaben:
<ol>
<li> Graph $G$ als Adjazenzlisten- oder -matrixdarstellung</li>
<li> Eine Menge von Knoten mit den Zuständen:</li>
<ol>
<li> $farbe=weiss$ für unbesuchte Knoten
<li> $farbe=grau$ für besuchte Knoten</li>
<li> $farbe=schwarz$ für abgeschlossene Knoten<br><br></li>
<li> $pi=nil$ (der Vorgänger)</li>
<li> $d[u]=0$ (die Zeit der Entdeckung)</li>
<li> $f[u]=0$ (die Zeit des Abschließens) </li>
</ol>
</ol>
<li> Algorithmus:
<ol>
<li>Initialisierung: ''alle'' Knoten $V(G)$ werden mit $weiss$ und $nil$ belegt, $zeit=0$</li>
<li>solange $L$ nicht leer ist:
<ol>
<li> wähle einen Knoten $v$ aus $L$</li>
<li> wähle und markiere einen unbesuchten Nachbarn $u$ von $v$ als besucht und speichere $u$ in die Arbeitsliste $L$</li>
<li> besitzt $v$ keine unbesuchte Nachbarn, entferne $v$ aus $L$<br><br></li>
</ol>
</ol>
<div style="background-color:#EEE">
'''Algorithmus:''' ''Graphendurchlauf_allgemein (Graph G, Knoten v $\in$ V(G), Arbeitsliste L)'' <br>
<math>
\begin{array}{l|l}
1 & v \leftarrow besucht\\
2 & L \leftarrow L \oplus v\\
3 & \mathbf{while}\; (L \neq\: \emptyset)\; \mathbf{do} \\
4 &\;\;\;\;\; \text{\small waehle Knoten } v \in L \\
5 &\;\;\;\;\;\; \mathbf{if}\; (\!\text{\small es gibt } u \in V(G) \text{\small mit } u=Nachbar\; von\; v \text{\small und } u=unbesucht)\; \mathbf{then} \\
6 &\;\;\;\;\;\;\;\;\;\;\;\; u \leftarrow besucht\\
7 &\;\;\;\;\;\;\;\;\;\;\;\; L \leftarrow L \oplus u\\
8 &\;\;\;\;\;\; \mathbf{else}\; L \leftarrow L \ominus u \\
\end{array}
</math><br>
'''end''' ''Graphendurchlauf_allgemein''
</div></li>
</ul>
= Breitendurchlauf/ -suche =
= Iterative Tiefensuche (Kombination) =
= Anwendung/ weiterführende Themen =
== Topologisches Sortieren ==
== Euler und Hamilton ==
== Starke Zusammenhangskomponenten ==
== TSP und CPP ==
= Java-Test =
<code id="4f9875926c8ee">
public Object Vertex (char label)
{
char label = label;
boolean bereitsBesucht = false;
String farbe = "weiss";
int gefunden = -1;
int abgearbeitet = -1;
char vorgaenger = '#';
return this;
}
</code>
<code id="4fad535c9c64b">
public Object Edge (int s, int t)
{
int start=s;
int target=t;
String kantenart = "leer";
boolean traversed = false;
return this;
}
</code>
<code id="4f987d51e2b3c">
public Object Graph(int max, String a)
{
int knotenanzahl = max;
Object[] knotenliste = new Object[knotenanzahl];
int kantenanzahl = ((max+1)*(max+1));
Object[] kantenliste = new Object[kantenanzahl];
int kantengesamt=0;
int kanten = 0;
int knoten = 0;
int[][] adjazenzMatrix = new int[knotenanzahl+1][knotenanzahl+1];
String art = a;
int zeit = 0;
Object stacky = Stack();
Object queuey = Queue();
Object topologie = Stack();
for(int i =0; i<=knotenanzahl; i++)
for(int j=0; j<=knotenanzahl; j++)
adjazenzMatrix[i][j] = 0;
public void addEdge(int start, int end)
{
if(this.art == "ungerichtet"){
adjazenzMatrix[start-1][end-1] = 1;
adjazenzMatrix[end-1][start-1] = 1;
//if(start != end)
// {
// kantenliste[kanten++] = Edge(start, end);
// kantenliste[kanten++] = Edge(end, start);
// }
}
if(this.art == "gerichtet")
adjazenzMatrix[start-1][end-1] = 1;
//kantenliste[kanten++] = Edge(start, end);
}
public void addVertex(char lab)
{
knotenliste[knoten++] = Vertex(lab);
}
public void displayVertex(int v)
{
System.out.print(knotenliste[v].label);
}
public void displayVertexEX(int v)
{
System.out.print("Label: " + knotenliste[v].label + " ");
System.out.print("Farbe: " + knotenliste[v].farbe + " ");
System.out.print("Voriges Element: " + knotenliste[v].vorgaenger + " ");
System.out.print("Wann entdeckt: " + knotenliste[v].gefunden + " ");
System.out.print("Wann geschlossen: " + knotenliste[v].abgearbeitet + " ");
}
public void dfs()
{
System.out.print("\n\nDFS-Durchlaufordnung: ");
knotenliste[0].bereitsBesucht=true;
displayVertex(0);
stacky.push(0);
while (!stacky.istLeer())
{
int v = getAdjUnvisitedVertex(stacky.peek());
if(v == -1) stacky.pop();
else
{
knotenliste[v].bereitsBesucht = true;
displayVertex(v);
stacky.push(v);
}
}
for(int j=0; j<knoten; j++)
knotenliste[j].bereitsBesucht = false;
}
public void dfsrek(int start) //indizierung gleich natuerlicher stelle bei eingabe
{ start=start-1;
System.out.println("\n\nDFS-Durchlaufordnung(rekursiv):\n\n");
for(int j=0; j<knoten; j++) //anfang leer init
{
knotenliste[j].farbe="weiss";
knotenliste[j].vorgaenger='#';
}
zeit = 0; //ende leer init
for(int j=start; j<knoten; j++)
{
if (knotenliste[j].farbe=="weiss")
{
dfsvisit(j);
}
}
if (start!=0)
for(int j=0; j<start; j++)
{
if (knotenliste[j].farbe=="weiss")
{
dfsvisit(j);
}
};
for(int j=0; j<knoten; j++) //ausgabe endzustand
{
displayVertexEX(j);
System.out.println();
};
System.out.println("\n\n");
}
public void dfsvisit(int u)
{
knotenliste[u].farbe="grau";
zeit++;
knotenliste[u].gefunden=zeit;
for(int j=0; j<knoten; j++)
if(adjazenzMatrix[u][j] == 1 && knotenliste[j].farbe=="weiss")
{
knotenliste[j].vorgaenger=knotenliste[u].label;
dfsvisit(j);
};
knotenliste[u].farbe="schwarz";
zeit++;
knotenliste[u].abgearbeitet=zeit;
topologie.push(u+1);
}
public void displayKantenart(int z) //z ist Kante in der liste, 0 fuer alle
{ z = z-1;
if(z != -1)
{
System.out.print("Kante: "+knotenliste[kantenliste[z].start].label+" "+knotenliste[kantenliste[z].target].label+" ist eine ");
System.out.println(kantenliste[z].kantenart);
}
else
for (int i=0; i<kantengesamt; i++)
{
System.out.print("Kante: "+knotenliste[kantenliste[i].start].label+" "+knotenliste[kantenliste[i].target].label+" ist eine ");
System.out.println(kantenliste[i].kantenart);
}
}
public void ermittleKantenart()
{
for(int u=0; u<knoten; u++)
{
for(int j=0; j<knoten; j++)
{
if(adjazenzMatrix[u][j] == 1)
{
if (!((art == "ungerichtet") && (u==j)))
kantenliste[kanten] = Edge(u,j);
if ((u==j) && (art=="gerichtet"))
kantenliste[kanten].kantenart="Reuckwaertskante";
else if ((knotenliste[u].gefunden + 1)==knotenliste[j].gefunden)
kantenliste[kanten].kantenart="Baumkante";
else
kantenliste[kanten].kantenart="leer";
kanten++;
}
}
}
kantengesamt=kanten;
kanten=0;
for(int u=0; u<knoten; u++)
for(int j=0; j<knoten; j++)
if(adjazenzMatrix[u][j] == 1)
{
if (kantenliste[kanten].kantenart=="leer")
if ((verbindetBaumkanten(u,j)) && (knotenliste[u].gefunden > knotenliste[j].gefunden)&&
(knotenliste[u].abgearbeitet < knotenliste[j].abgearbeitet))
kantenliste[kanten].kantenart="Reuckwaertskante";
else if ((verbindetBaumkanten(u,j)) && (knotenliste[u].gefunden < knotenliste[j].gefunden)&&
(knotenliste[u].abgearbeitet > knotenliste[j].abgearbeitet))
kantenliste[kanten].kantenart="Vorwaertskante";
else if (!(u==j) && (art=="gerichtet"))
kantenliste[kanten].kantenart="Querkante";
kanten++;
};
}
public boolean verbindetBaumkanten(int start, int target)
{
for(int j=0; j<kantengesamt ; j++)
{if ((kantenliste[j].start==target) && (kantenliste[j].kantenart=="Baumkante") )
return true;
else if ((kantenliste[j].target==start) && (kantenliste[j].kantenart=="Baumkante") )
return true;
else if ((kantenliste[j].target==target) && (kantenliste[j].kantenart=="Baumkante") )
return true;
else if ((kantenliste[j].start==start) && (kantenliste[j].kantenart=="Baumkante") )
return true;
}
return false;
}
public void displayTopo()
{ System.out.println("Topologisch sortiert: ");
for(int j=0; j<knoten ; j++)
{
System.out.print(topologie.peek() +" ");
topologie.pop();
}
System.out.println();
}
public void bfs()
{
System.out.print("\n\nBFS-Durchlaufordnung: ");
knotenliste[0].bereitsBesucht = true;
displayVertex(0);
queuey.enqueue(0);
while( !queuey.istLeer() )
{
int v = getAdjUnvisitedVertex( queuey.peek() );
if(v == -1)
queuey.dequeue();
else
{
knotenliste[v].bereitsBesucht = true;
displayVertex(v);
queuey.enqueue(v);
}
}
for(int j=0; j<knoten; j++)
knotenliste[j].bereitsBesucht = false;
}
public int getAdjUnvisitedVertex(int v)
{
for(int j=0; j<knoten; j++)
if(adjazenzMatrix[v][j] == 1 && knotenliste[j].bereitsBesucht==false)
return j;
return -1;
}
public void zeigeAdjMatrix()
{
System.out.println("\nAdjazenzmatrix:");
Object[][] showMat = new Object[knotenanzahl+1][knotenanzahl+1];
showMat[0][0] = ' ' ;
for(int i=0; i<knotenanzahl; i++){
for(int row=1; row<=knotenanzahl; row++){
showMat[0][row] = this.knotenliste[row-1].label;
showMat[i+1][row] = this.adjazenzMatrix[i][row-1];}
for(int col=1; col<=knotenanzahl; col++){
showMat[col][0] = this.knotenliste[col-1].label;
showMat[col][i+1] = this.adjazenzMatrix[col-1][i];}}
for (int k = 0; k<=knotenanzahl; ++k) {
for (int l = 0; l<=knotenanzahl; ++l) {
System.out.print(showMat[k][l] + "\t");}
System.out.println("");}
}
public void pruefeGrad()
{
System.out.println("\n\nEin- und Ausgangsgrade:");
int countIndegree=0, countOutdegree=0;
int[] In = new int[knotenanzahl];
int[] Out = new int[knotenanzahl];
for(int i=0; i<knotenanzahl; i++){
for(int j=0; j<knotenanzahl;j++){
if (adjazenzMatrix[j][i] ==1)
countIndegree++;
if(adjazenzMatrix[i][j] == 1)
countOutdegree++;
}
In[i]=countIndegree;
Out[i]=countOutdegree;
System.out.print("Eingangsgrad von Knoten " + knotenliste[i].label + ": " + countIndegree + "\t");
System.out.print("Ausgangsgrad von Knoten " + knotenliste[i].label + ": " + countOutdegree + "\n");
countIndegree=0;
countOutdegree=0;
}
int ungerade=0;
for (int l=0; l<knotenanzahl; l++){
if(Out[l]%2 !=0)
ungerade++;
}
System.out.println("\n--> Anzahl Knoten ungeraden Ausgangsgrades: " + ungerade);
if(ungerade== 0)
System.out.println("==> Eulerkreis möglich!");
else if(ungerade==2)
System.out.println("==> Eulerpfad möglich!");
else
System.out.println("==> Weder Eulerkreis noch -pfad möglich!");
int test=0;
for(int k=0; k<knotenanzahl; k++){
if((In[k] != 0) && (Out[k] != 0))
test++;}
if(test==knotenanzahl)
System.out.println("==> Hamiltonpfad und/ oder -kreis möglich!");
else
System.out.println("==> Kein Hamiltonkreis, jedoch Hamiltonpfad möglich!");
}
return this;
}
</code>
<run id="4f9875926c9de">
//G1 von S.145
//zur differenzierung ungeeignet - bfs & dfs liefern gleiche ordnung!
//G aus PDF-09 besser!!
theGraph = Graph(6, "gerichtet");
theGraph.addVertex('A'); // 1 (start)
theGraph.addVertex('B'); // 2
theGraph.addVertex('C'); // 3
theGraph.addVertex('D'); // 4
theGraph.addVertex('E'); // 5
theGraph.addVertex('F'); // 6
theGraph.addEdge(1, 2); // A-B
theGraph.addEdge(1, 4); // A-D
theGraph.addEdge(1, 6); // A-F
theGraph.addEdge(2, 3); // B-C
theGraph.addEdge(2, 4); // B-D
theGraph.addEdge(3, 4); // C-D
theGraph.addEdge(3, 5); // C-E
theGraph.addEdge(3, 6); // C-F
theGraph.addEdge(4, 5); // D-E
theGraph.addEdge(4, 3); // D-C
theGraph.addEdge(5, 6); // E-F
theGraph.zeigeAdjMatrix();
theGraph.dfs();
theGraph.dfsrek(1);
theGraph.bfs();
theGraph.pruefeGrad();
//funktioniert prinzipiell
/* TODO:
* konstruktor mit parameterübergabe (x)
* nutzereingabe optimieren (d.h. edge 1 = array-index 1) (x)
* adjazenzmatrix darstellen (mit rand) (x)
* queue implementieren + bfs (x)
* fallunterscheidung gerichtet-ungerichtet (x)
* YAY~ :D
* eulerprüfung(code) mit pfadangabe(pseudo) (~)
* hamiltonprüfung(code) mit pfadangabe(pseudo) (~)
* DFS von beliebigem startknoten (~)
* SCC ( )
*/
</run>
<run id="4fa6e6115a107">
nikolaus = Graph(5, "ungerichtet");
nikolaus.addVertex('A'); // 1 (start)
nikolaus.addVertex('B'); // 2
nikolaus.addVertex('C'); // 3
nikolaus.addVertex('D'); // 4
nikolaus.addVertex('E'); // 5
nikolaus.addEdge(1, 2); // A-B
nikolaus.addEdge(1, 3); // A-D
nikolaus.addEdge(1, 4); // A-F
nikolaus.addEdge(2, 3); // B-C
nikolaus.addEdge(2, 4); // B-D
nikolaus.addEdge(3, 4); // C-D
nikolaus.addEdge(3, 5); // C-E
nikolaus.addEdge(4, 5); // D-E
nikolaus.zeigeAdjMatrix();
nikolaus.pruefeGrad();
</run>
<run id="4fa9861cdf0d1">
sachen = Graph(9,"gerichtet");
sachen.addVertex('A'); //1//Unterhose
sachen.addVertex('B'); //2//Hose
sachen.addVertex('C'); //3//Guertel
sachen.addVertex('D'); //4//Hemd
sachen.addVertex('E'); //5//Kravatte
sachen.addVertex('F'); //6//Jacket
sachen.addVertex('G'); //7//Socken
sachen.addVertex('H'); //8//Schuhe
sachen.addVertex('I'); //9//Uhr
sachen.addEdge(1,2);
sachen.addEdge(1,8);
sachen.addEdge(2,8);
sachen.addEdge(2,3);
sachen.addEdge(3,6);
sachen.addEdge(7,8);
sachen.addEdge(4,3);
sachen.addEdge(4,5);
sachen.addEdge(5,6);
sachen.dfsrek(1);
sachen.displayTopo();
</run>
<run id="4fad1e5012b57">
kantentest = Graph(6,"gerichtet");
kantentest.addVertex('u');//1
kantentest.addVertex('v');//2
kantentest.addVertex('w');//3
kantentest.addVertex('x');//4
kantentest.addVertex('y');//5
kantentest.addVertex('z');//6
kantentest.addEdge(1,2);
kantentest.addEdge(1,4);
kantentest.addEdge(2,5);
kantentest.addEdge(3,5);
kantentest.addEdge(3,6);
kantentest.addEdge(4,2);
kantentest.addEdge(5,4);
kantentest.addEdge(6,6);
kantentest.dfsrek(1);
kantentest.displayTopo();
kantentest.ermittleKantenart();
kantentest.displayKantenart(0);
</run>