AuK/Durchläufe durch Graphen SS12
Aus ProgrammingWiki
Wiki-Quelltext dieser Seite.
<language>Java</language>
Text vor TOC, evtl. Intro etc.
<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 ==
<language>Java</language>
= 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);
};
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 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,3);
kanten.addEdge(5,4);
kanten.addEdge(6,6);
kanten.dfsrek(6);
kanten.displayTopo();
</run>