Zählen der Anzahl der durchlaufenen Kanten bei einer Breadth First Search?

Question

Das ist mein bfs-Algorithmus. Ich möchte die Anzahl der Kanten, die ich durchquert habe, im Feld Kanten speichern, aber ich kann nicht herausfinden, wo ich die Variable platzieren soll, um für jede Kante eine hinzuzufügen. Ich erhalte immer wieder Antworten, die zu lang sind, also denke ich, dass dies schwieriger ist als die einfache Inkrementierung der Kante.

Es ist zu beachten, dass damit nur die Kanten entlang des wahren Pfades berechnet werden, nicht die zusätzlichen Kanten.

public int distance(Vertex x, Vertex y){
        Queue<Vertex> search = new LinkedList<Vertex>();
        search.add(x);
        x.visited = true;
        while(!search.isEmpty()){
            Vertex t = search.poll();
            if(t == y){
                return edges;
            }
            for(Vertex n: t.neighbours){
                if(!n.visited){
                    n.visited = true;
                    search.add(n);
                }

            }
            System.out.println(search + " " + t);
        }
        return edges;   
    }

Für jede Hilfe bin ich dankbar. Wenn Sie weitere Klassen/Methoden benötigen, lassen Sie es mich wissen.

EDITAR

import java.util.ArrayList;

public class Vertex {

    public static char currentID = 'a';
    protected ArrayList<Vertex> neighbours;
    protected char id;
    protected boolean visited = false;
    protected Vertex cameFrom = null;
    public Vertex(){
        neighbours = new ArrayList<Vertex>();
        id = currentID;
        currentID++;
        Graph.all.add(this);
    }
    public void addNeighbour(Vertex x){
        int a;
        while(x == this){
             a = (int) (Math.random()*(Graph.all.size()));
             x = Graph.all.get(a);
        }           
            if(!(neighbours.contains(x))){
                neighbours.add(x);
                x.addNeighbour(this);
                //System.out.println(this + " Linking to " + x);
            }
    }
    public void printNeighbours(){
        System.out.println("The neighbours of: " + id + " are: " + neighbours);
    }
    public String toString(){
        return id + "";
    }

}

Answer 1

In Ihrem Vertex Klasse, erstellen Sie eine Vertex cameFrom das Sie so einstellen, dass es auf das Feld Vertex aus dem Sie kamen, als dieser Knoten besucht wurde. Sie könnten sogar Ihre boolean visited Feld mit diesem (wenn es ein null el Vertex noch nicht besucht worden ist).

Dann, wenn Sie die Vertex y folgen Sie einfach den Hinweisen zurück zu Vertex x Zählen Sie, wie viele Schritte Sie brauchen, während Sie gehen.

Wenn Sie nicht Ihre Vertex Klasse, dann behalten Sie einfach eine Map<Vertex,Vertex> während Ihrer Suche, die die Zuordnungen von dem Punkt, den Sie besuchen, zu dem Punkt, von dem Sie kommen, speichert. Wenn Sie am Ende angekommen sind, können Sie den Weg zum Anfang auf dieselbe Weise zurückverfolgen.

---

Vielleicht etwas in dieser Richtung:

    public int distance(Vertex x, Vertex y){
        Queue<Vertex> search = new LinkedList<Vertex>();
        search.add(x);
        while(!search.isEmpty()){
            Vertex t = search.poll();
            if(t == y){
                return pathLength( t );
            }
            for(Vertex n: t.neighbours){
                if(n.cameFrom == null || n != x){
                    n.cameFrom = t;
                    search.add(n);
                }

            }
            System.out.println(search + " " + t);
        }
        return -1;  
    }

    public int pathLength( Vertex v )
    {
       int path = 0;

       while ( v.cameFrom != null )
       {
         v = v.cameFrom;
         path++;
       }

       return path;
    }

Answer 2

In diesem Beispiel entspricht die Anzahl der Kanten einfach der Größe des search Schlange.

EDIT:

Eine mögliche Lösung besteht darin, Schicht für Schicht vorzugehen. Angenommen, Sie fragen nach dem Abstand zwischen dem Scheitelpunkt A, F

und der Graph sieht wie folgt aus:

A
|\
B C
|
D
|\
E F

Berechnen Sie zunächst den Abstand zwischen A und B, C (was einfach ist, weil B und C unmittelbare Nachbarn von A sind). Berechnen Sie dann den Abstand zwischen A und D (was einfach ist, weil D ein unmittelbarer Nachbar von B ist), dann A und E, F. Speichern Sie den Abstand im Knoten A vertex. Nachdem Sie nun das BFS ausgeführt und das Suchergebnis ermittelt haben, können Sie einfach nach dem Abstand fragen. Sehen Sie sich diese visuelles Diagramm.