Breitensuche

[jeko87]

Hallo,
also ich muss für die Uni ein Programm schreiben welches die Breitensuche implementiert.
Soweit auch kein Problem, Graph wird auch korrekt erstellt.

Mein Problem ist allerdings die Darstellung der Schichten.
Also man fänkt beim Startknoten an (Schicht 0), dann kommen 2 neue Knoten dazu, 1 und 2. Diesen wären dann in der Schicht 1.
Jetzt kommen die Knoten 3 und 4 (verbunden mit Knoten 1) und bilden Schicht 2.
Danach kommen Knoten 5 und 6 (verbunden mit Knoten 2) und wären ebenfalls in Schichte 2...

Also meiner Implementierung nach ist alles korrekt bis auf Knoten 5 und 6...diese werden in Schichte 3 gelegt...
Die Implementierung ist aufgebaut nach dem Pseudocode aus unserer Vorlesung


ich wäre froh wenn mir jemand weiterhelfen könnte...
vielen Dank schon im Voraus

hier ist mal mein Code

package graph;

import java.util.*;
import java.util.concurrent.ArrayBlockingQueue;

import graphbib.*;

public class BFS
{    
    public static void solve(IUndirectedGraph g, int s, LinkedList<int[]> rBFSTree, int[] rLayer)
    {        
        Queue<Integer> q = new ArrayBlockingQueue<Integer>(rLayer.length);
        boolean[] reached = new boolean[rLayer.length]; 
        
        q.add(s);
       
        reached[s]=true;
        rLayer[s] = 0;
        int iter = 0;
        while(!q.isEmpty()) 
        {
            for (int j = 0; j <= q.size(); j++)     
            {
                int u = q.remove();
                System.out.println(u);
                Set<Integer> n = g.getNeighbours(u); // wir suchen die Nachbarn von Knoten u

                for (Iterator<Integer> i = n.iterator(); i.hasNext();)   
                {
                    Integer v = i.next();
                    if(!reached[v])  // Knoten v wurde noch nicht bearbeiten
                    {
                        int[] input = {u,v};
                        rBFSTree.add(input);    // Baum erweitern
                        reached[v]=true;
                        q.add(v); // in Queue einsetzen
                        System.out.println(v+" im Layer " +(iter+1));
                        rLayer[v] = iter+1;       
                    }
                }
                System.out.println("it: "+(iter+1));
                iter=iter+1; //Layeriterator
            }
        }
    }

    @SuppressWarnings("static-access")
    public static void main(String [ ] args)
    {
        BFS b = new BFS();
        int m = 7;

        IUndirectedGraph g = GraphBibliography.createUndirectedGraph(m);
        g.addEdge(0, 1);
        g.addEdge(0, 2);
        g.addEdge(1, 3);
        g.addEdge(1, 4);
        g.addEdge(2, 5);
        g.addEdge(2, 6);

        int s = 0;

        LinkedList<int[]> rEdges = new LinkedList<int[]>();
        int[] rLayer = new int[m];

        b.solve(g, s, rEdges, rLayer);      
    }
}

also meiner Meinung nach liegt das Problem bei einer der Schleifen, da werden nur die Nachbarknoten von Knoten 1 beachtet, anschliessend wird zwa wieder bei Knoten 2 weitergemacht, jedoch wird der Schichtenzähler auch hochgezählt

 

[Marcinek]

Entweder oder aber nicht beide

  while(!q.isEmpty()) 
        {
            for (int j = 0; j <= q.size(); j++)

 

[DerMathematiker]

Ich empfehle den Graph als AdjazenzArray (nicht liste!!) zu implementieren und die Breitesuche in einem int[] mit pointern selbst zu verwalten. Wenn man in die Größenordnung von Graphen mit Millionen Knoten und Kanten kommt gabs bei mir mit Objekten immer Probleme.

 

[jeko87]

erstmal vielen Dank für eure Antworten. Ich hab das Problem mittlerweile gelöst. Habt mir wirklich weitergeholfen

ja, wenn ich die Möglichkeit hätte eine Implementierung zu wählen, würd ich auch nicht die Liste wählen...warum weiss ich nicht, aber die Array-Implementierung fällt mir leichter.
Aber da wir uns halt an unsere Angaben halten müssen, muss ich mich halt mit der Adjazenzliste irgendwie versuchen anzufreunden ^^

nun ja, hat ja schliesslich geklappt...danke nochmals