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 in einem Graphen systematisch zu besuchen, um beispielsweise Informationen über dessen Struktur zu sammeln.
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 Kräuzungen von Gängen in Augenschein nimmt. Übertragen auf die Graphentheorie, existieren hierfür zwei bekannte algorithmische Lösungsverfahren, die Hauptgegenstand dieser Vorlesung sind.
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ärmung 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 =
'''Bezug auf:'''
<ul>
<li> '''Graphenrepräsentation:''' Arten und Darstellung $\rightarrow$ abhängig!</li>
<li> '''Sortierte Folgen:''' Bäume und Preorder </li>
<li> '''w. Datenstrukturen:''' Stack und Queue </li>
</ul>
= Unterscheidung von Durchlaufproblemen =
== Durchlauf aller Knoten ==
== Durchlauf aller Kanten ==
= Tiefendurchlauf/ -suche =
= Breitendurchlauf/ -suche =
= Iterative Tiefensuche =
= Anwendung/ weiterführende Themen =
== Starke Zusammenhangskomponenten ==
== Topologisches Sortieren ==
== TSP und CPP ==
= Java-Test =
<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>
<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>
<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="4f987d51e2b3c">
public Object Graph(int max, String a)
{
int knotenanzahl = max;
Object[] knotenliste = new Object[knotenanzahl];
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(this.art == "gerichtet")
adjazenzMatrix[start-1][end-1] = 1;
}
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)
{
displayKantenart(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);
};
displayKantenart(u);
knotenliste[u].farbe="schwarz";
zeit++;
knotenliste[u].abgearbeitet=zeit;
topologie.push(u+1);
}
public void displayKantenart(z)
{
System.out.print("Kante: "+knotenliste[z].vorgaenger+" "+knotenliste[z].label+" ist eine ");
if (knotenliste[z].farbe=="weiss")
System.out.println("Baumkante");
else if (knotenliste[z].farbe=="grau")
System.out.println("Reuckwaertskante");
else if (knotenliste[z].farbe=="schwarz")
System.out.println("Quer- oder Vorwaertskante");
}
public void kantenart()
{
System.out.print("Kante: "+knotenliste[z].vorgaenger+" "+knotenliste[z].label+" ist eine ");
if (knotenliste[z].farbe=="weiss")
System.out.println("Baumkante");
else if (knotenliste[z].farbe=="grau")
System.out.println("Reuckwaertskante");
else if (knotenliste[z].farbe=="schwarz")
System.out.println("Quer- oder Vorwaertskante");
for(int u=0; u<knoten; u++)
for(int j=0; j<knoten; j++)
if(adjazenzMatrix[u][j] == 1)
{
System.out.print("Kante: "+knotenliste[u].label+" "+knotenliste[j].label+" ist eine ");
if ((knotenliste[u].gefunden + 1)==knotenliste[j].gefunden)
System.out.println("Baumkante");
else if (knotenliste[u].gefunden > knotenliste[j].gefunden)
System.out.println("Reuckwaertskante");
else
System.out.println("Quer- oder Vorwaertskante");
};
}
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">
kanten = Graph(6,"gerichtet");
kanten.addVertex('u');//1
kanten.addVertex('v');//2
kanten.addVertex('w');//3
kanten.addVertex('x');//4
kanten.addVertex('y');//5
kanten.addVertex('z');//6
kanten.addEdge(1,2);
kanten.addEdge(1,4);
kanten.addEdge(2,5);
kanten.addEdge(3,5);
kanten.addEdge(3,6);
kanten.addEdge(4,2);
kanten.addEdge(5,4);
kanten.addEdge(6,6);
kanten.dfsrek(6);
kanten.displayTopo();
</run>