Übung Grundbegriffe der Graphentheorie 2
Aus ProgrammingWiki
Wiki-Quelltext dieser Seite.
= Graphen in Java =
==Java Program to Find MST(Minimum Spanning Tree) using Prim’s Algorithm ==
<code>
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>
== 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>
<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>
[https://upload.wikimedia.org/wikipedia/commons/archive/b/b1/20150611221338%21MAZE_30x20_Prim.ogv]
== Algorithmus von Prim ==
Der Algorithmus von Prim dient der Berechnung eines minimalen Spannbaumes in einem zusammenhängenden, ungerichteten, kantengewichteten Graphen.<br>
<code>
von Purpy Pupple (Eigenes Werk) [<a href="http://creativecommons.org/licenses/by-sa/3.0">CC BY-SA 3.0</a> oder <a href="http://www.gnu.org/copyleft/fdl.html">GFDL</a>], <a href="https://commons.wikimedia.org/wiki/File%3AMazegeneration.gif">via Wikimedia Commons</a>
== UBUNG ==
Grundidee:
Die Adjazenzmatrix wird mit Hilfe einer zweidimensionalen Reihung dargestellt.<br>
[[Bild:S3anbrem_Ubung1.png]]
<br>
{| class="wikitable"
|-
! !! AZ !! BI !! FT !! KL !! KO !! MZ !! RB !! SP !! TR
|-
|AZ || <popup></popup>|| <popup>35</popup> || <popup>36</popup> ||<popup>48</popup>|| <popup></popup> ||<popup>33</popup> || <popup></popup> || <popup></popup> || <popup></popup>
|-
|BI || <popup>35</popup>|| <popup></popup> || <popup></popup> ||<popup></popup>|| <popup></popup> ||<popup>35</popup> || <popup>28</popup> || <popup></popup> || <popup></popup>
|-
|FT || <popup>36</popup>|| <popup></popup> || <popup></popup> ||<popup>48</popup>|| <popup></popup> ||<popup></popup> || <popup></popup> || <popup>31</popup> || <popup></popup>
|-
|KL || <popup>48</popup>|| <popup></popup> || <popup>48</popup> ||<popup></popup>|| <popup></popup> ||<popup></popup> || <popup></popup> || <popup></popup> || <popup>116</popup>
|-
|KO || <popup></popup>|| <popup></popup> || <popup></popup> ||<popup></popup>|| <popup></popup> ||<popup></popup> || <popup>54</popup> || <popup></popup> || <popup>128</popup>
|-
|MZ || <popup>33</popup>|| <popup>35</popup> || <popup></popup> ||<popup></popup>|| <popup></popup> ||<popup></popup> || <popup></popup> || <popup></popup> || <popup></popup>
|-
|RB || <popup></popup>|| <popup>28</popup> || <popup></popup> ||<popup></popup>|| <popup>54</popup> ||<popup></popup> || <popup></popup> || <popup></popup> || <popup>98</popup>
|-
|SP || <popup></popup>|| <popup></popup> || <popup>31</popup> ||<popup></popup>|| <popup></popup> ||<popup></popup> || <popup></popup> || <popup></popup> || <popup></popup>
|-
|TR || <popup></popup>|| <popup></popup> || <popup></popup> ||<popup>116</popup>|| <popup>128</popup> ||<popup></popup> || <popup>98</popup> || <popup></popup> || <popup></popup>
|}
== U2 ==
Der folgende gerichtete Graph sei durch seine Kantenliste
gegeben:<br>
<b>7, 10, 1, 7, 1, 4, 1, 5, 2, 1, 2, 3, 3, 6, 6, 5, 4, 5, 5, 2, 7, 4</b>
<br>
Geben Sie die Adjazenzmatrix des Graphen an.
<br>
<popup name="*">
[[Bild:S3anbrem_Erg2.JPG]]
</popup>
<popup name="*">
[[Bild:S3anbrem_Erg1.JPG]]
</popup>
== Ergänzung zum Graph-Interface: ==
<br>
<code>
public interface Graph{
public int addNode();
public boolean addEdge(int orig, int dest);
public Collection<Integer> getChildren(int node);!
}
</code>
Breitendurchlauf als Iterator:
<code>
public class BfsIterator implements Iterator<Integer>{
private Graph g;
private Queue<Integer> q;
private Set<Integer> visited;
public BfsIterator(Graph g, int s){
this.g = g;
this.q = new LinkedList<Integer>();
q.add(s);
this.visited = new HashSet<Integer>();
}
public boolean hasNext() { return !this.q.isEmpty(); }
public Integer next() {
Integer n = this.q.poll();
for(Integer m: this.g.getChildren(n))
if(!this.visited.contains(m) && !this.q.contains(m))
this.q.add(m);
this.visited.add(n);
return n;
}
}
</code>
==Ü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!