Übung Grundbegriffe der Graphentheorie 2

Wiki-Quelltext dieser Seite.

= Graphen in Java =

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