Übung Grundbegriffe der Graphentheorie 2
Aus ProgrammingWiki
Wiki-Quelltext dieser Seite.
''Sie sollen diese JAVA-Klasse in Netbeans oder Eclipse benutzen. Sie sollen nur richtige Eingaben im Konsole (oben) schreiben :) <br>
Wenn Sie die Fragen haben , probiere ich verschaffen .
Viel Erfolg!'' <br>
= '''Graphen in Java''' =
== '''Algorithmus von Prim''' ==
Der Algorithmus von Prim dient der Berechnung eines minimalen Spannbaumes in einem zusammenhängenden, ungerichteten, kantengewichteten Graphen.<br>
[https://upload.wikimedia.org/wikipedia/commons/archive/b/b1/20150611221338%21MAZE_30x20_Prim.ogv]
==='''Java Program to Find MST(Minimum Spanning Tree) using Prim’s Algorithm''' ===
<code id="562d004e971ca">
import java.util.InputMismatchException;
import java.util.Scanner;
public class Prims
{
private final boolean unsettled[];
private final boolean settled[];
private final int numberofvertices;
private final int adjacencyMatrix[][];
private final int key[];
public static final int INFINITE = 999;
private final int parent[];
public Prims(int numberofvertices)
{
this.numberofvertices = numberofvertices;
unsettled = new boolean[numberofvertices + 1];
settled = new boolean[numberofvertices + 1];
adjacencyMatrix = new int[numberofvertices + 1][numberofvertices + 1];
key = new int[numberofvertices + 1];
parent = new int[numberofvertices + 1];
}
public int getUnsettledCount(boolean unsettled[])
{
int count = 0;
for (int index = 0; index < unsettled.length; index++)
{
if (unsettled[index])
{
count++;
}
}
return count;
}
public void primsAlgorithm(int adjacencyMatrix[][])
{
int evaluationVertex;
for (int source = 1; source <= numberofvertices; source++)
{
for (int destination = 1; destination <= numberofvertices; destination++)
{
this.adjacencyMatrix[source][destination] = adjacencyMatrix[source][destination];
}
}
for (int index = 1; index <= numberofvertices; index++)
{
key[index] = INFINITE;
}
key[1] = 0;
unsettled[1] = true;
parent[1] = 1;
while (getUnsettledCount(unsettled) != 0)
{
evaluationVertex = getMimumKeyVertexFromUnsettled(unsettled);
unsettled[evaluationVertex] = false;
settled[evaluationVertex] = true;
evaluateNeighbours(evaluationVertex);
}
}
private int getMimumKeyVertexFromUnsettled(boolean[] unsettled2)
{
int min = Integer.MAX_VALUE;
int node = 0;
for (int vertex = 1; vertex <= numberofvertices; vertex++)
{
if (unsettled[vertex] == true && key[vertex] < min)
{
node = vertex;
min = key[vertex];
}
}
return node;
}
public void evaluateNeighbours(int evaluationVertex)
{
for (int destinationvertex = 1; destinationvertex <= numberofvertices; destinationvertex++)
{
if (settled[destinationvertex] == false)
{
if (adjacencyMatrix[evaluationVertex][destinationvertex] != INFINITE)
{
if (adjacencyMatrix[evaluationVertex][destinationvertex] < key[destinationvertex])
{
key[destinationvertex] = adjacencyMatrix[evaluationVertex][destinationvertex];
parent[destinationvertex] = evaluationVertex;
}
unsettled[destinationvertex] = true;
}
}
}
}
public void printMST()
{
System.out.println("SOURCE : DESTINATION = WEIGHT");
for (int vertex = 2; vertex <= numberofvertices; vertex++)
{
System.out.println(parent[vertex] + "\t:\t" + vertex +"\t=\t"+ adjacencyMatrix[parent[vertex]][vertex]);
}
}
public static void main(String... arg)
{
int adjacency_matrix[][];
int number_of_vertices;
Scanner scan = new Scanner(System.in);
try
{
System.out.println("Enter the number of vertices");
number_of_vertices = scan.nextInt();
adjacency_matrix = new int[number_of_vertices + 1][number_of_vertices + 1];
System.out.println("Enter the Weighted Matrix for the graph");
for (int i = 1; i <= number_of_vertices; i++)
{
for (int j = 1; j <= number_of_vertices; j++)
{
adjacency_matrix[i][j] = scan.nextInt();
if (i == j)
{
adjacency_matrix[i][j] = 0;
continue;
}
if (adjacency_matrix[i][j] == 0)
{
adjacency_matrix[i][j] = INFINITE;
}
}
}
Prims prims = new Prims(number_of_vertices);
prims.primsAlgorithm(adjacency_matrix);
prims.printMST();
} catch (InputMismatchException inputMismatch)
{
System.out.println("Wrong Input Format");
}
scan.close();
}
}
</code>
Output --> Lösung
<popup name="*">
Enter the number of vertices<br>
5<br>
Enter the Weighted Matrix for the graph<br>
0 4 0 0 5<br>
4 0 3 6 1 <br>
0 3 0 6 2<br>
0 6 6 0 7<br>
5 1 2 7 0<br>
SOURCE : DESTINATION = WEIGHT<br>
1 : 2 = 4<br>
5 : 3 = 2<br>
2 : 4 = 6<br>
2 : 5 = 1<br>
</popup>
<br>
<br>
''' Zusätzliche Informationen '''
[[https://www.youtube.com/watch?v=Pn874kEc3IA
]]
[[https://www.youtube.com/embed/ENWVRcMGDoU]]
== Create a Balanced Binary Tree of the Incoming Data ==
<code>
//This is a java program to insert elements in a Binary Search Tree
import java.util.Scanner;
class BSTNode
{
BSTNode left, right;
int data;
public BSTNode()
{
left = null;
right = null;
data = 0;
}
public BSTNode(int n)
{
left = null;
right = null;
data = n;
}
public void setLeft(BSTNode n)
{
left = n;
}
public void setRight(BSTNode n)
{
right = n;
}
public BSTNode getLeft()
{
return left;
}
public BSTNode getRight()
{
return right;
}
public void setData(int d)
{
data = d;
}
public int getData()
{
return data;
}
}
class BSTree
{
private BSTNode root;
public BSTree()
{
root = null;
}
public boolean isEmpty()
{
return root == null;
}
public void insert(int data)
{
root = insert(root, data);
}
private BSTNode insert(BSTNode node, int data)
{
if (node == null)
node = new BSTNode(data);
else
{
if (data <= node.getData())
node.left = insert(node.left, data);
else
node.right = insert(node.right, data);
}
return node;
}
public void inorder()
{
inorder(root);
}
private void inorder(BSTNode r)
{
if (r != null)
{
inorder(r.getLeft());
System.out.print(r.getData() + " ");
inorder(r.getRight());
}
}
public void preorder()
{
preorder(root);
}
private void preorder(BSTNode r)
{
if (r != null)
{
System.out.print(r.getData() + " ");
preorder(r.getLeft());
preorder(r.getRight());
}
}
public void postorder()
{
postorder(root);
}
private void postorder(BSTNode r)
{
if (r != null)
{
postorder(r.getLeft());
postorder(r.getRight());
System.out.print(r.getData() + " ");
}
}
}
public class Insertion_BST
{
public static void main(String[] args)
{
Scanner scan = new Scanner(System.in);
BSTree bst = new BSTree();
System.out.println("Binary Search Tree Insertion Test\n");
int N = 10;
for (int i = 0; i < N; i++)
{
bst.insert(scan.nextInt());
System.out.print("\nPost order : ");
bst.postorder();
System.out.print("\nPre order : ");
bst.preorder();
System.out.print("\nIn order : ");
bst.inorder();
}
scan.close();
}
}
</code>
<br>'''
2. MOEGLICHKEIT'''
<code>
//This is a java program to make a self balancing binary tree for the input data
import java.util.Scanner;
class SBBSTNodes
{
SBBSTNodes left, right;
int data;
int height;
public SBBSTNodes()
{
left = null;
right = null;
data = 0;
height = 0;
}
public SBBSTNodes(int n)
{
left = null;
right = null;
data = n;
height = 0;
}
}
class SelfBalancingBinarySearchTrees
{
private SBBSTNodes root;
public SelfBalancingBinarySearchTrees()
{
root = null;
}
public boolean isEmpty()
{
return root == null;
}
public void clear()
{
root = null;
}
public void insert(int data)
{
root = insert(data, root);
}
private int height(SBBSTNodes t)
{
return t == null ? -1 : t.height;
}
private int max(int lhs, int rhs)
{
return lhs > rhs ? lhs : rhs;
}
private SBBSTNodes insert(int x, SBBSTNodes t)
{
if (t == null)
t = new SBBSTNodes(x);
else if (x < t.data)
{
t.left = insert(x, t.left);
if (height(t.left) - height(t.right) == 2)
if (x < t.left.data)
t = rotateWithLeftChild(t);
else
t = doubleWithLeftChild(t);
} else if (x > t.data)
{
t.right = insert(x, t.right);
if (height(t.right) - height(t.left) == 2)
if (x > t.right.data)
t = rotateWithRightChild(t);
else
t = doubleWithRightChild(t);
} else
;
t.height = max(height(t.left), height(t.right)) + 1;
return t;
}
private SBBSTNodes rotateWithLeftChild(SBBSTNodes k2)
{
SBBSTNodes k1 = k2.left;
k2.left = k1.right;
k1.right = k2;
k2.height = max(height(k2.left), height(k2.right)) + 1;
k1.height = max(height(k1.left), k2.height) + 1;
return k1;
}
private SBBSTNodes rotateWithRightChild(SBBSTNodes k1)
{
SBBSTNodes k2 = k1.right;
k1.right = k2.left;
k2.left = k1;
k1.height = max(height(k1.left), height(k1.right)) + 1;
k2.height = max(height(k2.right), k1.height) + 1;
return k2;
}
private SBBSTNodes doubleWithLeftChild(SBBSTNodes k3)
{
k3.left = rotateWithRightChild(k3.left);
return rotateWithLeftChild(k3);
}
private SBBSTNodes doubleWithRightChild(SBBSTNodes k1)
{
k1.right = rotateWithLeftChild(k1.right);
return rotateWithRightChild(k1);
}
public int countNodes()
{
return countNodes(root);
}
private int countNodes(SBBSTNodes r)
{
if (r == null)
return 0;
else
{
int l = 1;
l += countNodes(r.left);
l += countNodes(r.right);
return l;
}
}
public boolean search(int val)
{
return search(root, val);
}
private boolean search(SBBSTNodes r, int val)
{
boolean found = false;
while ((r != null) && !found)
{
int rval = r.data;
if (val < rval)
r = r.left;
else if (val > rval)
r = r.right;
else
{
found = true;
break;
}
found = search(r, val);
}
return found;
}
public void inorder()
{
inorder(root);
}
private void inorder(SBBSTNodes r)
{
if (r != null)
{
inorder(r.left);
System.out.print(r.data + " ");
inorder(r.right);
}
}
public void preorder()
{
preorder(root);
}
private void preorder(SBBSTNodes r)
{
if (r != null)
{
System.out.print(r.data + " ");
preorder(r.left);
preorder(r.right);
}
}
public void postorder()
{
postorder(root);
}
private void postorder(SBBSTNodes r)
{
if (r != null)
{
postorder(r.left);
postorder(r.right);
System.out.print(r.data + " ");
}
}
}
public class Balanced_B_Tree
{
public static void main(String[] args)
{
Scanner scan = new Scanner(System.in);
SelfBalancingBinarySearchTrees sbbst = new SelfBalancingBinarySearchTrees();
System.out.println("Self Balancing Tree\n");
int N = 10;
for (int i = 0; i < N; i++)
sbbst.insert(scan.nextInt());
System.out.println("\nPre-order :");
sbbst.preorder();
System.out.println("\nIn-order :");
sbbst.inorder();
System.out.println("\nPost-order :");
sbbst.postorder();
scan.close();
}
}
</code>
<br>
Output --> Loesung<br>
<popup>
<code>
Self Balancing Tree
45
46
48
98
23
34
65
59
21
10
Pre-order :
46 34 21 10 23 45 65 48 59 98
In-order :
10 21 23 34 45 46 48 59 65 98
Post-order :
10 23 21 45 34 59 48 98 65 46
</code>
</popup>
<br>
==''' Implement Binary Tree''' ==
<code>
/*
* Java Program to Implement Binary Tree
*/
import java.util.Scanner;
/* Class BTNode */
class BTNode
{
BTNode left, right;
int data;
/* Constructor */
public BTNode()
{
left = null;
right = null;
data = 0;
}
/* Constructor */
public BTNode(int n)
{
left = null;
right = null;
data = n;
}
/* Function to set left node */
public void setLeft(BTNode n)
{
left = n;
}
/* Function to set right node */
public void setRight(BTNode n)
{
right = n;
}
/* Function to get left node */
public BTNode getLeft()
{
return left;
}
/* Function to get right node */
public BTNode getRight()
{
return right;
}
/* Function to set data to node */
public void setData(int d)
{
data = d;
}
/* Function to get data from node */
public int getData()
{
return data;
}
}
/* Class BT */
class BT
{
private BTNode root;
/* Constructor */
public BT()
{
root = null;
}
/* Function to check if tree is empty */
public boolean isEmpty()
{
return root == null;
}
/* Functions to insert data */
public void insert(int data)
{
root = insert(root, data);
}
/* Function to insert data recursively */
private BTNode insert(BTNode node, int data)
{
if (node == null)
node = new BTNode(data);
else
{
if (node.getRight() == null)
node.right = insert(node.right, data);
else
node.left = insert(node.left, data);
}
return node;
}
/* Function to count number of nodes */
public int countNodes()
{
return countNodes(root);
}
/* Function to count number of nodes recursively */
private int countNodes(BTNode r)
{
if (r == null)
return 0;
else
{
int l = 1;
l += countNodes(r.getLeft());
l += countNodes(r.getRight());
return l;
}
}
/* Function to search for an element */
public boolean search(int val)
{
return search(root, val);
}
/* Function to search for an element recursively */
private boolean search(BTNode r, int val)
{
if (r.getData() == val)
return true;
if (r.getLeft() != null)
if (search(r.getLeft(), val))
return true;
if (r.getRight() != null)
if (search(r.getRight(), val))
return true;
return false;
}
/* Function for inorder traversal */
public void inorder()
{
inorder(root);
}
private void inorder(BTNode r)
{
if (r != null)
{
inorder(r.getLeft());
System.out.print(r.getData() +" ");
inorder(r.getRight());
}
}
/* Function for preorder traversal */
public void preorder()
{
preorder(root);
}
private void preorder(BTNode r)
{
if (r != null)
{
System.out.print(r.getData() +" ");
preorder(r.getLeft());
preorder(r.getRight());
}
}
/* Function for postorder traversal */
public void postorder()
{
postorder(root);
}
private void postorder(BTNode r)
{
if (r != null)
{
postorder(r.getLeft());
postorder(r.getRight());
System.out.print(r.getData() +" ");
}
}
}
/* Class BinaryTree */
public class BinaryTree
{
public static void main(String[] args)
{
Scanner scan = new Scanner(System.in);
/* Creating object of BT */
BT bt = new BT();
/* Perform tree operations */
System.out.println("Binary Tree Test\n");
char ch;
do
{
System.out.println("\nBinary Tree Operations\n");
System.out.println("1. insert ");
System.out.println("2. search");
System.out.println("3. count nodes");
System.out.println("4. check empty");
int choice = scan.nextInt();
switch (choice)
{
case 1 :
System.out.println("Enter integer element to insert");
bt.insert( scan.nextInt() );
break;
case 2 :
System.out.println("Enter integer element to search");
System.out.println("Search result : "+ bt.search( scan.nextInt() ));
break;
case 3 :
System.out.println("Nodes = "+ bt.countNodes());
break;
case 4 :
System.out.println("Empty status = "+ bt.isEmpty());
break;
default :
System.out.println("Wrong Entry \n ");
break;
}
/* Display tree */
System.out.print("\nPost order : ");
bt.postorder();
System.out.print("\nPre order : ");
bt.preorder();
System.out.print("\nIn order : ");
bt.inorder();
System.out.println("\n\nDo you want to continue (Type y or n) \n");
ch = scan.next().charAt(0);
} while (ch == 'Y'|| ch == 'y');
}
}
</code>
<br>
Output --> Loesungen<br>
<popup>
<code>
$ java Insertion_BST.java<br>
$ java Insertion_BST<br>
<br>
Binary Search Tree Insertion Test<br>
<br>
Add element: 3
<br>
Post order : 3
Pre order : 3
In order : 3
<br>
Add element: 5
<br>
Post order : 5 3
Pre order : 3 5
In order : 3 5
</code>
</popup>
=== Find Number of Spanning Trees in a Complete Bipartite Graph ===
1. Import Scanner<br>
2. Implementieren Sie eine Klasse NumOfSpanningBipartite,die folgende Anforderungen erfuellt:<br>
- Die integer Zahlen "firstSetSize" und "secondSetSize" werden werden im Methode als Parameter erwartet und in privaten Attributen abgespeichert. <br>
- return (this.firstSetSize^(this.secondSetSize - 1)) *(this.secondSetSize ^ (this.firstSetSize -1)); <br>
3. Implementieren Sie eine main- Klasse nur mit String[args] Parameter <br>
- Deklarieren Sie m und n als Zahlvariable(int)<br>
- Benutzen Sie die Scanner Prozedure.<br>
- Drucken Sie " Enter the size of the bipartite graph(m and n)<br>
- Benutzen Sie eine Methode Scanner fuer m und n (next...())<br>
- Erzeugen Sie ein neues Objekt bipartite.<br>
- Benutzen Sie System.out.println(...+bipartite.numerOfSpanningTree(m,n)))<br>
- Schliessen Sie Scanner Methode.<br>
<br>
OUTPUT:
<popup>
enter the size of the bipartite graph (m and n)<br>
2 2<br>
the number of spanning trees are 9<br>
</popup>
<font color = "red"> Ich hoffe, dass ganze Gruppe damit zurechtkommen :D
Aber machen Sie keine Sorgen, die Loesungen werde ich nach der Unterrichte schreiben.Wenn jemand eine Frage habt, probiere ich zu helfen! :}
</font color>
<popup>
<code>
1. import java.util.Scanner;
2.
3. public class NumOfSpanningBipartite
4. {
5. private int firstSetSize;
6. private int secondSetSize;
7.
8. public int numberOfSpanningTree(int firstSetSize, int secondSetSize)
9. {
10. this.firstSetSize = firstSetSize;
11. this.secondSetSize = secondSetSize;
12. return (this.firstSetSize^(this.secondSetSize - 1)) *(this.secondSetSize ^ (this.firstSetSize -1));
13. }
14.
15. public static void main(String...arg)
16. {
17. int m, n;
18. Scanner scanner = new Scanner(System.in);
19. System.out.println("enter the size of the bipartite graph (m and n)");
20. m = scanner.nextInt();
21. n = scanner.nextInt();
22.
23. NumOfSpanningBipartite bipartite = new NumOfSpanningBipartite();
24. System.out.println(" the number of spanning trees are " + bipartite.numberOfSpanningTree(m, n));
25. scanner.close();
26. }
27. }
</code>
</popup>
=''' Aufgaben''' =
=== '''Aufgabe1''' ===
[[Bild:S3anbrem_Graph34.gif]]<br>
Wieviele Zusammenhangskomponenten hat der Graph? <br>
<popup name="*">
2
</popup>
Ist der Graph bipartit?<br>
<popup name="*">
Nein, es gibt Kreise ungerader Länge
</popup>
dG(x,y) =?<br>
<popup name="*">
3
</popup>
dG(x,z) <br>
<popup name="*">
2
</popup>
Wieviel Kreise gibt es im Graphen ?<br>
<popup name="*">
5
</popup>
Wieviele Wege gibt es von x nach y?<br>
<popup name="*">
4
</popup>
=<font color="green">Übung zu Gozinto-Graphen</font color>=
Zur Produktion eines Endproduktes A werden 4 Teile vom Typ B, 2 Teile Typ C, 3Teile Typ D und 1Teil vom Typ E benötigt. Typ E fließt mit je 1Teil auch noch in die Produktion von D und C ein. Ein weiterer Bautyp F fließt zu je 2Stk in die Produktion von C und mit je 1Stk in die Produktion von B ein.<br>
1.Zeichne einen Gozinto-Graphen zu dem beschriebenen Sachverhalt.<br>
2.Wir erhalten einen Auftrag und sollen 150A, 400B, 50C, 100D, 200E und 300F
bereitstellen. Ermitteln sie den Gesamtbedarf für alle Teile der Produktionskette!
LÖSUNG<br>
Direktmatrix ------ und ------ Einheitsmatrix
0| 1| 0| 2| 0| 0 | 1| 0| 0| 0| 0| 0
0| 0| 0| 0| 0| 4 | 0| 1| 0| 0| 0| 0
0| 0| 0| 1| 1| 1 | 0| 0| 1| 0| 0| 0
0| 0| 0| 0| 0| 2 | 0| 0| 0| 1| 0| 0
0| 0| 0| 0| 0| 3 | 0| 0| 0| 0| 1| 0
0| 0| 0| 0| 0| 0 | 0| 0| 0| 0| 0| 1
Einheitsmatrix - Direktmatrix
1|-1| 0| 2| 0| 0
0| 1| 0| 0| 0|-4 +4*Zeile6
0| 0| 1|-1|-1|-1 +Zeile6
0| 0| 0| 1| 0|-2 +2*Zeile6
0| 0| 0| 0| 1|-3 +3*Zeile6
0| 0| 0| 0| 0| 1
1|-1| 0| 2| 0| 0 +2*Zeile4 | +Zeile2
0| 1| 0| 0| 0| 4
0| 0| 1|-1|-1| 1
0| 0| 0| 1| 0| 2 +Zeile5 |+Zeile4
0| 0| 0| 0| 1| 3
0| 0| 0| 0| 0| 1
Ergebnis der Invertierung
1| 1| 0| 2| 0| 8
0| 1| 0| 0| 0| 4
0| 0| 1| 1| 1| 6
0| 0| 0| 1| 0| 2
0| 0| 0| 0| 1| 3
0| 0| 0| 0| 0| 1
Multiplikation mit Primärbedarfvektor
(1*300)+(1*400)+(0*200)+(2*50)+(0*100)+(8*150) = 2000<br>
0+400+0+0+0+600 = 1000<br>
0+0+200+50+100+900 = 1250<br>
0+0+0+50+0+300 = 350<br>
0+0+0+0+100+450 = 550<br>
0+0+0+0+0+150 = 150<br>
= <font color="green">Übung zu Bipartität</font color> =
<ul>
<li><b>Aufgabe</b>Erstelle ein Programm welches testet ob ein zusammenhängender Graph bipartit ist oder nicht. Orientiere dich dabei an dem in der Vorlesung vorgestellten Algorithmus im Abschnitt: <font color="green">Konstruktion einer Zerlegung von V in <font color="red">S</font color> und <font color="blue">T</font color></font color>!<br>
<li><b>Zusatzaufgabe:</b> Schreibe das Programm so um, dass es auch für nicht zusammenhängende Graphen funktioniert.
<li><b>Zusatzaufgabe:</b> Führe eine empirische Effizienzanalyse mit dem Testprogramm durch.<br>
</ul>
Hilfestellung zur Aufgabenstellung findest du in dem folgenden Code für ein funktionierendes Testprogramm, welches allerdings noch einige Optimierungsmöglichkeiten bietet!
<ul>
<li><b>Zusatzaufgabe:</b> Hat das vorgestellte Programm linearen Aufwand? Begründe deine Antwort.
</ul>
<popup name="Antwort">
Da in dem Programm eine Adjazenzmatrix(2-dimensional) übergeben wird, in welcher jeder Eintrag getestet werden muss, ist der Aufwand exponenziel. Eine Adjazenzliste würde für den Aufwand eine Verbesserung bewirken. Mehr dazu in den Vorlesungsfolien von Graphentheorie 1.
</popup>
<code>
//Javaprogram zum testen ob ein Graph bipartit ist oder nicht
import java.util.*;
import java.lang.*;
import java.io.*;
//===================================================================================================================================
class Bipartite
{
final static int KnotenAnzahl = 4; // Anzahl der Knoten
boolean istBipartit(int G[][],int start) // Testunktion für einen Graphen G[][]. Startknoten muss mit übergeben werden.
{ //True wenn bipartit, false wenn nicht.
// Wert 1 steht für Farbe a, 0 für Farbe b
int FarbenArray[] = new int[KnotenAnzahl]; // Farbenarray - Zuordnung von Farben zu jedem Knoten.
for (int i=0; i<KnotenAnzahl; ++i)
FarbenArray[i] = -1; // Solange noch keine Farbe zugeordnet wurde hat jeder Knoten den Wert '-1'
FarbenArray[start] = 1; // Startknoten färben
LinkedList<Integer>keller = new LinkedList<Integer>(); // Keller für neu eingefärbte Knoten
keller.add(start);
while (keller.size() != 0)
{
// Knoten aus dem Keller holen und in u speichern
int u = keller.poll();
for (int v=0; v<KnotenAnzahl; ++v)
{
if (G[u][v]==1 && FarbenArray[v]==-1) //wenn Graph von u nach v existiert und v noch keine Farbe hat...
{
FarbenArray[v] = 1-FarbenArray[u]; //färbung zu 0 wenn u 1 ist, wenn u 0 ist färbung zu 1
keller.add(v); //neu gefärbten Knoten zur weiteren untersuchung in den Keller legen
}
else if (G[u][v]==1 && FarbenArray[v]==FarbenArray[u]) //wenn Graph von u nach v existiert und beide
// Knoten die selbe farbe haben...
return false;
}
}
return true;
}
//=================MAIN=================
public static void main (String[] args)
{
//Graph als Adjazenzmatrix erstellen
int G[][] = {{0, 1, 1, 1},
{1, 0, 1, 0},
{1, 1, 0, 1},
{1, 0, 1, 0}};
//Testfunktion aufrufen
Bipartite b = new Bipartite();
if (b.istBipartit(G, 0))
System.out.println("Graph ist bipartit");
else
System.out.println("Graph ist nicht bipartit");
}
}
</code>