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>
Note: Durchlauf (traversal) $\neq$ Suche (search)!
</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> Was ist der Unterschied zwischen gerichteten und ungerichteten Graphen?
<popup title="Lösung">
<ol >
Die Kante $(u,v)$ in einem ''ungerichteten'' Graphen ergibt zwei Kanten $(u,v)$ und $(v,u)$ in einem ''gerichtetetn'' Graphen. <br>
''Ungerichtete'' Graphen besitzen keine Schlingen.
</ol>
</popup>
</li>
<li>Welche Darstellungsformen für Graphen gibt es?
<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> Matrix oder Liste (Inzidenz/Adjazenz)</li>
<li> Bei Adjazenzdarstellung ist mit steigender Kantenzahl eine Matrix besser.</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>Nach welchem Prinzip arbeitet eine Warteschlange?
<popup title="Lösung">
<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>Nach welchem Prinzip arbeitet ein Stack?</li>
<popup title="Lösung">
<code id="4f986cf808f9a">
//note to self: code verstecken funktioniert auch innerhalb methoden
//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
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>
= Unterscheidung von Durchlaufproblemen =
== Durchlauf aller Knoten ==
=== Allgemeiner 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: Graph $G$ als Adjazenzlisten- oder -matrixdarstellung, eine Menge von Knoten mit den Zuständen unbesucht und besucht und eine Arbeitsliste $L$, die besuchte aber noch nicht abgearbeitete Knoten beinhaltet.</li>
<li> Algorithmus:
<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> 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>
=== u.a. Hamiltonkreise/ -pfade ===
== Durchlauf aller Kanten ==
=== u.a. Eulerkreise/ -pfade ===
=== 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 =
= Anwendung/ weiterführende Themen =
== Starke Zusammenhangskomponenten ==
== Topologisches Sortieren ==
== 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 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(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<kanten; 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-1].kantenart="Reuckwaertskante";
else if ((knotenliste[u].gefunden + 1)==knotenliste[j].gefunden)
kantenliste[kanten-1].kantenart="Baumkante";
else
kantenliste[kanten-1].kantenart="leer";
}
}
kanten=0;
for(int u=0; u<knoten; u++)
for(int j=0; j<knoten; j++)
if(adjazenzMatrix[u][j] == 1)
{
kanten++;
if ((verbindetBaumkanten(u,j)) && (knotenliste[u].label == knotenliste[j].vorgaenger))
kantenliste[kanten-1].kantenart="Reuckwaertskante";
else if ((verbindetBaumkanten(u,j)) && (knotenliste[j].label == knotenliste[u].vorgaenger))
kantenliste[kanten-1].kantenart="Vorwaertskante";
else
kantenliste[kanten-1].kantenart="Querkante";
};
}
public boolean verbindetBaumkanten(int start, int target)
{
for(int j=0; j<kantenanzahl ; j++)
{if (knotenliste[j].start==target )
return true;
else if (knotenliste[j].target==start )
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();
}
}
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>