Übung Grundbegriffe der Graphentheorie 2

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

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

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