Übung Grundbegriffe der Graphentheorie 2

Aus ProgrammingWiki
Wiki-Quelltext dieser Seite.
= Graphen in Java =
== U1==

== 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>        
|}


__________________________________________________________________________________________________________________________________________________________________________________________________________________________


Die Klassenkameraden haben im vorigen Woche eine Vollständige Graphen vorgestellt und Grundbegriffe der Graphentheorie erklärt. 

Ein Graph heißt <b>vollständig</b>, wenn jede Ecke mit jeder anderen durch genau eine Kante verbunden ist. 
Das heißt, bei einem vollständigen Graphen sind je zwei Ecken verbunden, aber nur durch eine Kante. Der vollständige Graph mit n Ecken wird mit K_n bezeichnet.<br>
[[Bild:S3anbrem_VollständigerGraph.png]]


<b> Dagegen möchten wir heute andere Typen von Graphen vorstellen.</b> <br>
1. Bipartite Graphen.<br>
2. Gerichtete Graphen und Multigraphen<br>
3. Bewertete Graphen <br>
4. Bäume und Wälder<br>
5. Gozinto-Graphen<br>
<br>


== 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 Grundbegriffe der Graphentheorie 2

Suche
