Übung Grundbegriffe der Graphentheorie 2
Aus ProgrammingWiki
Wiki-Quelltext dieser Seite.
= Graphen in Java =
<code>
#include <iostream>
#include <queue>
#include <random>
#include <utility>
#include <vector>
#include <cstdio>
using namespace std;
const int xsize = 20;
const int ysize = 30;
int main() {
random_device rd;
mt19937 en(rd());
uniform_real_distribution<double> uni(0,1);
vector<int> v(xsize*ysize, 0);
vector<int> w(xsize*ysize*2, 1);
vector<vector<pair<double, pair<int, int>>>> e(xsize*ysize);
for(int i=0; i<xsize; i++) {
for(int j=0; j<ysize; j++) {
int k = i*ysize + j;
if(i>0) e[k].push_back(make_pair(uni(en), make_pair(k, (i-1)*ysize + j)));
if(j>0) e[k].push_back(make_pair(uni(en), make_pair(k, i*ysize + (j-1))));
if(i<xsize-1) e[k].push_back(make_pair(uni(en), make_pair(k, (i+1)*ysize + j)));
if(j<ysize-1) e[k].push_back(make_pair(uni(en), make_pair(k, i*ysize + (j+1))));
}
}
priority_queue <pair<double, pair<int, int>>> frontier;
int x = 0, y = 0;
v[x*ysize + y] = 1;
for(auto k : e[0]) {
frontier.push(k);
}
while(!frontier.empty()) {
auto z = frontier.top();
frontier.pop();
int a = z.second.first;
int b = z.second.second;
if(v[b]) continue;
v[b] = 2;
int aa = min(a,b);
int bb = max(a,b);
if(bb-aa == 1) {
w[2*aa] = 0;
} else {
w[2*aa+1] = 0;
}
for(auto k : e[b]) {
if(!v[k.second.second]) {
frontier.push(k);
}
}
// print the thing lol
for(int j=0; j<2*ysize+1; j++) {
cout << "1 ";
}
for(int i=0; i<xsize; i++) {
cout << endl << "1 ";
for(int j=0; j<ysize; j++) {
cout << "102"[v[i*ysize + j]] << " " << "01"[w[2*(i*ysize + j)]] << " ";
}
cout << endl << "1 ";
for(int j=0; j<ysize; j++) {
cout << "01"[w[2*(i*ysize + j)+1]] << " 1 ";
}
}
cout << endl;
v[b] = 1;
}
}
</code>
== 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>
[https://upload.wikimedia.org/wikipedia/commons/archive/b/b1/20150611221338%21MAZE_30x20_Prim.ogv]
==Ü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!