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>
<language>Java</language>
<language>Java</language>
<language>Java</language>
<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 = '0';
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();
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 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(start)
{
System.out.print("\n\nDFS-Durchlaufordnung: ");
for(int j=0; j<knoten; j++) //anfang leer init
{
knotenliste[j].farbe="weiss";
knotenliste[j].vorgaenger='0';
}
zeit = 0; //ende leer init
for(int j=start; j<knoten; j++)
{
if (knotenliste[j].farbe="weiss")
dfsvisit(j);
}
for(int j=0; j<knoten; j++) //ausgabe
{
System.out.println(knotenliste[j].label+" "+knotenliste[j].farbe+" "+knotenliste[j].vorgaenger+" "+knotenliste[j].besucht+" "+knotenliste[j].abgearbeitet);
knotenliste[j].vorgaenger='0';
}
}
public void DFSvisit(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;
}
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.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>