Übung Grundbegriffe der Graphentheorie 2

Aus ProgrammingWiki

Archivierte Version vom 2015-11-02T08:06:22+00:00. Aktuelle Version

Graphen in Java

Ergänzung zum Graph-Interface:

public interface Graph{
public int addNode();
   public boolean addEdge(int orig, int dest);
   public Collection<Integer> getChildren(int node);!
}

Breitendurchlauf als Iterator:

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

Übung Grundbegriffe der Graphentheorie 2

Graphen in Java

Ergänzung zum Graph-Interface:

Suche