Ü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''' ==
[[https://www.youtube.com/embed/6hfOvs8pY1k]]
== '''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>
Lösung
<popup name="*">
<code>
</code>
</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>
==''' 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>
=== 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 Konstruktor 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>
<popup>
$javac NumOfSpanningBipartite.java<br>
$java NumOfSpanningBipartite<br>
enter the size of the bipartite graph (m and n)<br>
2 2<br>
the number of spanning trees are 9<br>
</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>
==Übung zu Gozinto-Graphen==
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!