Übung Grundbegriffe der Graphentheorie 2
Aus ProgrammingWiki
Wiki-Quelltext dieser Seite.
= Graphen in Java =
Minimum Spanning Tree
<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>
<popup name="*">
<code>
$javac Prims.java
$java Prims
Enter the number of vertices
5
Enter the Weighted Matrix for the graph
0 4 0 0 5
4 0 3 6 1
0 3 0 6 2
0 6 6 0 7
5 1 2 7 0
SOURCE : DESTINATION = WEIGHT
1 : 2 = 4
5 : 3 = 2
2 : 4 = 6
2 : 5 = 1
</code>
</popup>
[https://upload.wikimedia.org/wikipedia/commons/archive/b/b1/20150611221338%21MAZE_30x20_Prim.ogv]
== 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!