Übung Grundbegriffe der Graphentheorie 2

Aus ProgrammingWiki

Archivierte Version vom 2015-11-02T18:45:03+00:00. Aktuelle Version

Inhaltsverzeichnis

1 Graphen in Java

Graphen in Java

UBUNG

Grundidee: Die Adjazenzmatrix wird mit Hilfe einer zweidimensionalen Reihung dargestellt.

	AZ	BI	FT	KL	KO	MZ	RB	SP	TR
AZ	Details	Details 35	Details 36	Details 48	Details	Details 33	Details	Details	Details
BI	Details 35	Details	Details	Details	Details	Details 35	Details 28	Details	Details
FT	Details 36	Details	Details	Details 48	Details	Details	Details	Details 31	Details
KL	Details 48	Details	Details 48	Details	Details	Details	Details	Details	Details 116
KO	Details	Details	Details	Details	Details	Details	Details 54	Details	Details 128
MZ	Details 33	Details 35	Details	Details	Details	Details	Details	Details	Details
RB	Details	Details 28	Details	Details	Details 54	Details	Details	Details	Details 98
SP	Details	Details	Details 31	Details	Details	Details	Details	Details	Details
TR	Details	Details	Details	Details 116	Details 128	Details	Details 98	Details	Details

U2

Der folgende gerichtete Graph sei durch seine Kantenliste gegeben:
7, 10, 1, 7, 1, 4, 1, 5, 2, 1, 2, 3, 3, 6, 6, 5, 4, 5, 5, 2, 7, 4
Geben Sie die Adjazenzmatrix des Graphen an.

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

Inhaltsverzeichnis

Graphen in Java

UBUNG

U2

Ergänzung zum Graph-Interface:

Suche