Zählen der Anzahl der Kanten, die in einer breiten ersten Suche durchlaufen wurden?

Question

Das ist mein bfs Algorithmus. Ich möchte die Anzahl der Kanten speichern, die ich in den Feldkanten durchlaufen habe, aber ich kann nicht herausfinden, wo die Variable platziert werden soll, um für jede Kante eine hinzuzufügen. Ich bekomme immer Antworten, die zu lang sind, also denke ich, dass das schwieriger ist, als einfach die Kante zu erhöhen.

Es sollte beachtet werden, dass dies nur die Kanten entlang des wahren Pfades berechnen soll, 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; 
    } 

Alle und alle Hilfe wird geschätzt. wenn Sie mehr Klassen benötigen/Methoden mich

EDIT

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 ein Vertex cameFrom Feld, das Sie auf den Vertex zeigen, von dem Sie kamen, als dieser Knoten besucht wurde. Sie könnten sogar Ihr Feld boolean visited durch dieses ersetzen (wenn es null ist, wurde die Vertex noch nicht besucht).

Dann, wenn Sie die Vertex y finden, folgen Sie einfach den Zeigern zurück zu Vertex x Zählen, wie viele Schritte es dauert, wie Sie gehen.

Wenn Sie Ihre Vertex Klasse nicht ändern möchten, behalten Sie während Ihrer Suche einfach eine Map<Vertex,Vertex>, die die Zuordnungen von dem Scheitelpunkt, den Sie besuchen, zu dem Scheitelpunkt speichert, von dem Sie kamen. Wenn du am Ende angelangt bist, kannst du auf die gleiche Weise dem Pfad zum Anfang folgen.

---

Etwas in dieser Richtung vielleicht:

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 wissen lassen, ist die Anzahl der Kanten einfach die Größe der search. Warteschlange.

EDIT:

Eine mögliche Lösung ist es Schicht für Schicht zu tun. Lassen Sie uns sagen Sie

und das Diagramm für den Abstand zwischen Vertex A, F gefragt wie folgt aussieht:

A 
|\ 
B C 
| 
D 
|\ 
E F 

zuerst den Abstand zwischen A und B, C (die leicht berechnen, da B und C unmittelbaren Nachbarn sind von A. Dann berechne den Abstand zwischen A und D (was einfach ist, weil D ein unmittelbarer Nachbar von B ist, dann A und E, F. Speichere die Entfernung in dem Knotenpunkt A. Jetzt, nachdem du das BFS ausgeführt und bestimmt hast Das Suchergebnis, können Sie einfach nach der Entfernung fragen. Betrachten Sie this visuelles Diagramm.