Tiefe erste Suche und breiteste Suche Implementierung

182187
fscore

Ich habe DFS- und BFS-Implementierungen implementiert. Ich möchte überprüfen, ob der Code lesbar ist, Probleme enthält und verbessert werden kann.

Graphimplementierung

package graphs;


import java.util.*;
import graphs.State;
public class GraphImplementation 
{
    public void dfs(Node root)
    {       
        //Avoid infinite loops
        if(root == null) return;

        System.out.print(root.getVertex() + "\t");
        root.state = State.Visited;

        //for every child
        for(Node n: root.getChild())
        {
            //if childs state is not visited then recurse
            if(n.state == State.Unvisited)
            {
                dfs(n);
            }
        }
    }

    public void bfs(Node root)
    {
        //Since queue is a interface
        Queue<Node> queue = new LinkedList<Node>();

        if(root == null) return;

        root.state = State.Visited;
         //Adds to end of queue
        queue.add(root);

        while(!queue.isEmpty())
        {
            //removes from front of queue
            Node r = queue.remove(); 
            System.out.print(r.getVertex() + "\t");

            //Visit child first before grandchild
            for(Node n: r.getChild())
            {
                if(n.state == State.Unvisited)
                {
                    queue.add(n);
                    n.state = State.Visited;
                }
            }
        }


    }

    public static Graph createNewGraph()
    {
        Graph g = new Graph();        
        Node[] temp = new Node[8];

        temp[0] = new Node("A", 3);
        temp[1] = new Node("B", 3);
        temp[2] = new Node("C", 1);
        temp[3] = new Node("D", 1);
        temp[4] = new Node("E", 1);
        temp[5] = new Node("F", 1);

        temp[0].addChildNode(temp[1]);
        temp[0].addChildNode(temp[2]);
        temp[0].addChildNode(temp[3]);

        temp[1].addChildNode(temp[0]);
        temp[1].addChildNode(temp[4]);
        temp[1].addChildNode(temp[5]);

        temp[2].addChildNode(temp[0]);
        temp[3].addChildNode(temp[0]);
        temp[4].addChildNode(temp[1]);
        temp[5].addChildNode(temp[1]);

        for (int i = 0; i < 7; i++) 
        {
            g.addNode(temp[i]);
        }
        return g;
    }

    public static void main(String[] args) {

        Graph gDfs = createNewGraph();
        GraphImplementation s = new GraphImplementation();

        System.out.println("--------------DFS---------------");
        s.dfs(gDfs.getNode()[0]);
        System.out.println();
        System.out.println();
        Graph gBfs = createNewGraph();
        System.out.println("---------------BFS---------------");
        s.bfs(gBfs.getNode()[0]);

    }

}

Graph.java:

package graphs;

public class Graph {

    public int count; // num of vertices
    private Node vertices[];

    public Graph()
    {
        vertices = new Node[8];
        count = 0;
    }

    public void addNode(Node n)
    {
        if(count < 10)
        {
            vertices[count] = n;
            count++;
        }
        else
        {
            System.out.println("graph full");
        }
    }

    public Node[] getNode()
    {
        return vertices;
    }
}

Node.java:

package graphs;
import graphs.State;
public class Node {

    public Node[] child;
    public int childCount;
    private String vertex;
    public State state;

    public Node(String vertex)
    {
        this.vertex = vertex;
    }

    public Node(String vertex, int childlen)
    {
        this.vertex = vertex;
        childCount = 0;
        child = new Node[childlen];
    }

    public void addChildNode(Node adj)
    {
        adj.state = State.Unvisited;
        if(childCount < 30)
        {
            this.child[childCount] = adj;
            childCount++;
        }
    }

    public Node[] getChild()
    {
        return child;
    }

    public String getVertex()
    {
        return vertex;
    }

}

State.java:

package graphs;

public enum State {

    Unvisited,Visiting,Visited;

}
Antworten
21
Ist dieser Code für Lern- / Zuweisungszwecke oder zum Arbeiten von Software / App? wayfare vor 5 Jahren 0
@ Xiang Ich versuche, Graphen selbst zu erlernen und verschiedene Suchalgorithmen, um in Bäumen und Graphen effizient zu werden fscore vor 5 Jahren 0
Ich finde es nützlich - http://opendatastructures.org/ods-java/12_3_Graph_Traversal.html. Erklärt alles klar mit Pseudo-Code. Sanjay Kumar vor 4 Jahren 0

4 Antworten auf die Frage

41
200_success

Datenstruktur

Ihre Terminologie ist ein bisschen aus. Bäume haben Wurzeln und Kinder. Willkürliche Diagramme dagegen ... Ich denke, "Herkunft" und "Nachbarn" wären angemessener.

  • Besuchte Flagge: Speichern der besuchten / nicht besuchten Flagge in der NodeFlexibilität der Verletzungen. Sobald Sie ein dfs()oder ausführen bfs(), ist das Diagramm "ruiniert". Sie können nicht alle Knoten auf den nicht besuchten Status zurücksetzen. (Nun, Sie könnten es manuell tun, da Node.statees ja ein öffentliches Feld ist. Aber das ist auch unangenehm.) Stattdessen schlage ich das vor dfs()und bfs()behalte einen HashSetder besuchten Knoten. Sobald die Überquerung abgeschlossen ist, verwerfen Sie einfach das Set.

  • State.Visiting: Dieser Wert wird niemals verwendet.

  • Node.getNode (): Der Name legt nahe, dass ein einzelner Knoten zurückgegeben wird. Dies ist jedoch nicht der Fall. Durch die Rückgabe des gesamten Arrays und des Originals des Arrays anstelle einer Kopie würde der Anrufer die Verbindungen des Diagramms auf nicht genehmigte Weise ändern lassen. Besser Möglichkeiten anbieten, alle Nachbarn zu durchlaufen und einen bestimmten Nachbarn zu holen.

  • Kinder Vertex - Array: Der NodeKonstruktor sagt: vertices = new Node[8]; Allerdings addNode()prüft if (count < 10). Sie sollten vertices.lengthstattdessen testen .

    Wenn die Kapazität überschritten wird, sollten Sie nicht als Nebeneffekt drucken System.out. Weisen Sie stattdessen eine Ausnahme aus, damit der Anrufer entscheiden kann, wie er damit umgehen soll.

    Besser noch, verwenden Sie eine erweiterbare Datenstruktur, damit Sie sich nicht mit Kapazitätsgrenzen beschäftigen müssen. Ein einfacher Ersatz wäre die Verwendung von ArrayList<Node>, aber lesen Sie weiter ...

  • Graph.vertices vs. Node.child: Diese Arrays scheinen den gleichen Zweck zu haben, redundant.

  • Graph.createNewGraph (): Es ist umständlich. Wäre es nicht schön, schreiben zu können?

    Graph g = new Graph();
    g.addEdge("A", "B");
    g.addEdge("B", "C");
    …
    return g;
    

Mein Vorschlag:

public class Graph {
    // Alternatively, use a Multimap:
    // http://google-collections.googlecode.com/svn/trunk/javadoc/com/google/common/collect/Multimap.html
    private Map<String, List<String>> edges = new HashMap<String, List<String>>();

    public void addEdge(String src, String dest) {
        List<String> srcNeighbors = this.edges.get(src);
        if (srcNeighbors == null) {
            this.edges.put(src,
                srcNeighbors = new ArrayList<String>()
            );
        }
        srcNeighbors.add(dest);
    }

    public Iterable<String> getNeighbors(String vertex) {
        List<String> neighbors = this.edges.get(vertex);
        if (neighbors == null) {
            return Collections.emptyList();
        } else {
            return Collections.unmodifiableList(neighbors);
        }
    }
}

Traversal

Ihre dfs()und bfs()Methoden können immer nur die Knotennamen drucken. Sie können den Code nicht für andere Zwecke wiederverwenden, da die System.out.print()Anrufe mit dem Durchlaufcode für Diagramme vermischt werden. Es ist besser, eine Iteratorso zu implementieren, dass der Anrufer entscheiden kann, was mit jedem Knoten zu tun ist.

DFS und BFS sind zwei verschiedene Strategien, um eine ähnliche Aufgabe zu erfüllen. Daher sollten sie in zwei Klassen mit einer gemeinsam genutzten Schnittstelle implementiert werden. Schlage ich vor Iterator<String>.

Der Iterator mit der ersten Breite ist eine ziemlich unkomplizierte Übersetzung Ihres ursprünglichen Codes. Der Hauptunterschied besteht darin, dass der Iterator nun dafür verantwortlich ist, zu verfolgen, welche Scheitelpunkte besucht wurden.

public class BreadthFirstIterator implements Iterator<String> {
    private Set<String> visited = new HashSet<String>();
    private Queue<String> queue = new LinkedList<String>();
    private Graph graph;

    public BreadthFirstIterator(Graph g, String startingVertex) {
        this.graph = g;
        this.queue.add(startingVertex);
        this.visited.add(startingVertex);
    }

    @Override
    public void remove() {
        throw new UnsupportedOperationException();
    }

    @Override
    public boolean hasNext() {
        return !this.queue.isEmpty();
    }

    @Override
    public String next() {
        //removes from front of queue
        String next = queue.remove(); 
        for (String neighbor : this.graph.getNeighbors(next)) {
            if (!this.visited.contains(neighbor)) {
                this.queue.add(neighbor);
                this.visited.add(neighbor);
            }
        }
        return next;
    }
}

Leider stellen Sie fest, dass Sie die Rekursion nicht mehr für das Durchlaufen der ersten Tiefe verwenden können. Stattdessen müssen Sie es als iterative Lösung mit einem expliziten Stack umschreiben, wodurch der Code komplizierter wird. (Alternativ können Sie, wenn Sie die Idee eines Anlegens aufgeben Iteratorund stattdessen das Besuchermuster verwenden, die rekursive Codestruktur beibehalten.)

public class PreOrderDFSIterator implements Iterator<String> {
    private Set<String> visited = new HashSet<String>();
    private Deque<Iterator<String>> stack = new LinkedList<Iterator<String>>();
    private Graph graph;
    private String next;

    public PreOrderDFSIterator(Graph g, String startingVertex) {
        this.stack.push(g.getNeighbors(startingVertex).iterator());
        this.graph = g;
        this.next = startingVertex;
    }

    @Override
    public void remove() {
        throw new UnsupportedOperationException();
    }

    @Override
    public boolean hasNext() {
        return this.next != null;
    }

    @Override
    public String next() {
        if (this.next == null) {
            throw new NoSuchElementException();
        }
        try {
            this.visited.add(this.next);
            return this.next;
        } finally {
            this.advance();
        }
    }

    private void advance() {
        Iterator<String> neighbors = this.stack.peek();
        do {
            while (!neighbors.hasNext()) {  // No more nodes -> back out a level
                this.stack.pop();
                if (this.stack.isEmpty()) { // All done!
                    this.next = null;
                    return;
                }
                neighbors = this.stack.peek();
            }

            this.next = neighbors.next();
        } while (this.visited.contains(this.next));
        this.stack.push(this.graph.getNeighbors(this.next).iterator());
    }
}

Tests

Dieses Problem verdient eine bessere Prüfung. Mit dem ursprünglichen Code, auf den immer gedruckt wurde System.out, gab es keine gute Möglichkeit, Komponententests zu schreiben. Jetzt können Sie mit den Ergebnissen alles tun, was Sie möchten, sodass Sie die richtigen Komponententests schreiben können.

import static org.junit.Assert.*;

import org.junit.BeforeClass;
import org.junit.Test;
import org.junit.runner.RunWith;
import org.junit.runners.JUnit4;

import java.util.*;

// javac -cp .:junit.jar GraphTest.java
// java -cp .:junit.jar:hamcrest-core.jar org.junit.runner.JUnitCore GraphTest

@RunWith(JUnit4.class)
public class GraphTest {

    public static Graph graph1;

    @BeforeClass
    public static void makeGraphs() {
        Graph g = graph1 = new Graph();
        g.addEdge("A", "B");
        g.addEdge("B", "C");
        g.addEdge("B", "D");
        g.addEdge("B", "A");
        g.addEdge("B", "E");
        g.addEdge("B", "F");
        g.addEdge("C", "A");
        g.addEdge("D", "C");
        g.addEdge("E", "B");
        g.addEdge("F", "B");
    }

    private void expectIteration(String answer, Iterator<String> it) {
        StringBuilder sb = new StringBuilder();
        while (it.hasNext()) {
            sb.append(' ').append(it.next());
        }
        assertEquals(answer, sb.substring(1));
    }

    @Test
    public void preOrderIterationOfIsolatedVertex() {
        expectIteration("Z", new PreOrderDFSIterator(graph1, "Z"));
    }

    @Test
    public void preOrderIterationFromA() {
        expectIteration("A B C D E F", new PreOrderDFSIterator(graph1, "A"));
    }

    @Test
    public void preOrderIterationFromB() {
        expectIteration("B C A D E F", new PreOrderDFSIterator(graph1, "B"));
    }

    @Test
    public void BreadthFirstIterationOfIsolatedVertex() {
        expectIteration("Z", new BreadthFirstIterator(graph1, "Z"));
    }

    @Test
    public void BreadthFirstIterationFromA() {
        expectIteration("A B C D E F", new BreadthFirstIterator(graph1, "A"));
    }

    @Test
    public void BreadthFirstIterationFromB() {
        expectIteration("B C D A E F", new BreadthFirstIterator(graph1, "B"));
    }
}
Was wäre besser zu verwenden: Graph.vertices vs. Node.child? fscore vor 5 Jahren 0
Weder! Speichern Sie stattdessen `Graph.edges`. 200_success vor 5 Jahren 0
Was ist mit dem Austausch von Iteratoren? Nur um 2 Zeilen Code zu vermeiden, wäre der Einsatz des Iterators ausreichend? fscore vor 5 Jahren 0
Der Hauptvorteil der Implementierung eines "Iterators" besteht darin, dass jeder sofort wissen kann, wie er verwendet wird. Der "Iterator" bietet eine sehr bequeme Schnittstelle für den Anrufer, jedoch wird der Code für den Tiefgang zuerst kompliziert. 200_success vor 5 Jahren 0
hey @ 200_success Warum schlagen Sie Kanten als private Map vor?> Kanten = neue HashMap> (); ?? ,>,> Mona Jalal vor 3 Jahren 0
@MonaJalal Die Schlüssel sind Knotennamen. Die Werte sind eine Liste der Nachbarn des Knotens. 200_success vor 3 Jahren 0
7
200_success

Wie ich bereits in meiner anderen Antwort erwähnt habe, System.out.println()schadet das Festcodieren, da die Aktion für jeden Knoten die Wiederverwendbarkeit von Code beeinträchtigt. Damit der Aufrufer die Aktion angeben kann, die auf jedem Knoten ausgeführt werden soll, ohne die Rekursion im Iterator für tiefe zuerst abzurollen, können Sie das Besuchermuster verwenden .

import java.util.*;

public class Graph<T> {

    public static interface Visitor<T> {
        void visit(T vertex);
    }

    // Alternatively, use a Multimap:
    // http://google-collections.googlecode.com/svn/trunk/javadoc/com/google/common/collect/Multimap.html
    private Map<T, List<T>> edges = new HashMap<T, List<T>>();

    public void addEdge(T src, T dest) {
        List<T> srcNeighbors = this.edges.get(src);
        if (srcNeighbors == null) {
            this.edges.put(src,
                srcNeighbors = new ArrayList<T>()
            );
        }
        srcNeighbors.add(dest);
    }

    public Iterable<T> getNeighbors(T vertex) {
        List<T> neighbors = this.edges.get(vertex);
        if (neighbors == null) {
            return Collections.emptyList();
        } else {
            return Collections.unmodifiableList(neighbors);
        }
    }

    public void preOrderTraversal(T vertex, Visitor<T> visitor) {
        preOrderTraversal(vertex, visitor, new HashSet<T>());
    }

    private void preOrderTraversal(T vertex, Visitor<T> visitor, Set<T> visited) {
        visitor.visit(vertex);
        visited.add(vertex);

        for (T neighbor : this.getNeighbors(vertex)) {
            // if neighbor has not been visited then recurse
            if (!visited.contains(neighbor)) {
                preOrderTraversal(neighbor, visitor, visited);
            }
        }
    }

    public void breadthFirstTraversal(T vertex, Visitor<T> visitor) {
        Set<T> visited = new HashSet<T>();
        Queue<T> queue = new LinkedList<T>();

        queue.add(vertex);              //Adds to end of queue
        visited.add(vertex);

        while (!queue.isEmpty()) {
            //removes from front of queue
            vertex = queue.remove(); 
            visitor.visit(vertex);

            //Visit child first before grandchild
            for (T neighbor : this.getNeighbors(vertex)) {
                if (!visited.contains(neighbor)) {
                    queue.add(neighbor);
                    visited.add(neighbor);
                }
            }
        }
    }

}

Ich habe den Knotentyp generisch gemacht, nur weil es möglich ist.

Hier sind Tests, um seine Verwendung zu demonstrieren.

import static org.junit.Assert.*;

import org.junit.BeforeClass;
import org.junit.Test;
import org.junit.runner.RunWith;
import org.junit.runners.JUnit4;

import java.util.*;

// javac -cp .:junit.jar Graph.java GraphTest.java
// java -cp .:junit.jar:hamcrest-core.jar org.junit.runner.JUnitCore GraphTest

@RunWith(JUnit4.class)
public class GraphTest {
    private static class CrumbtrailVisitor implements Graph.Visitor<String> {
        private StringBuilder sb = new StringBuilder();

        public void visit(String vertex) {
            sb.append(' ').append(vertex);
        }

        public String toString() {
            return sb.substring(1);
        }
    };

    public static Graph<String> graph1;

    @BeforeClass
    public static void makeGraphs() {
        Graph<String> g = graph1 = new Graph<String>();
        g.addEdge("A", "B");
        g.addEdge("B", "C");
        g.addEdge("B", "D");
        g.addEdge("B", "A");
        g.addEdge("B", "E");
        g.addEdge("B", "F");
        g.addEdge("C", "A");
        g.addEdge("D", "C");
        g.addEdge("E", "B");
        g.addEdge("F", "B");
    }

    @Test
    public void preOrderVisitorFromA() {
        Graph.Visitor<String> crumbtrailVisitor = new CrumbtrailVisitor();
        graph1.preOrderTraversal("A", crumbtrailVisitor);
        assertEquals("A B C D E F", crumbtrailVisitor.toString());
    }

    @Test
    public void breadthFirstVisitorFromB() {
        Graph.Visitor<String> crumbtrailVisitor = new CrumbtrailVisitor();
        graph1.breadthFirstTraversal("B", crumbtrailVisitor);
        assertEquals("B C D A E F", crumbtrailVisitor.toString());
    }
}

Wie Sie sehen, wird die Umkehrung der Kontrolle für den Anrufer schwieriger. Sie haben jedoch immer noch die Möglichkeit, eine beliebige Aktion festzulegen. Mit Java 8-Methodenreferenzen ist der einfache Fall einfach: Sie können nur schreiben graph1.preOrderTraversal("A", System.out::println).

3
ceco

Ich würde Listen anstelle von Arrays und öffentlichen Theken verwenden. z.B.:

public class Graph
{
   private List<Node> vertices = new LinkedList<Node>();    

   public void addNode(Node n)
   {        
       if(vertices.length >= 10){
           System.out.println("graph full");
           return;
       }            
       vertices.add(n);      
   }

   public Node[] getNode()
   {
        return vertices.toArray;
   }
}

Es gibt auch einen Fehler in Ihrer Graph-Klasse, da Ihr Array auf 8 Einträge beschränkt ist, aber Sie füllen es, bis Ihr Zähler> = 10 ist.

Ihre Node-Klasse enthält öffentliche Mitglieder mit Gettern? Ich würde sie privat machen;)

Ich würde auch überflüssige Kommentare entfernen. zB: "für jedes Kind" in einer for-Schleife. Da weiß jeder was eine for-Schleife macht.

Lassen Sie Ihren Code die Beschreibung sein:

for(Node child: root.getChild())
 if(child.state == State.Unvisited)
  dfs(n);
Warum sollten Sie Listen anstelle von Arrays verwenden? Was ist der Kompromiss? fscore vor 5 Jahren 0
Arrays sind kontinuierlich reservierter Speicher und in der Liste gibt es keine Garantie. Daher ist der Zugriff auf Objekte in Arrays viel schneller. * Arrays sind nicht dynamisch, aber die Liste ist. wayfare vor 5 Jahren 0
Für mich sind Listen einfacher zu handhaben. Sie werfen keine bösen Überlauffehler. Sie benötigen keinen Zähler, da die Liste diese Informationen bereits enthält. ceco vor 5 Jahren 2
Wenn ich Getter-Methoden als privat verwende, wie würde ich es dann in der Hauptklasse verwenden? fscore vor 5 Jahren 0
Nein, die Getter müssen öffentlich sein. Die Mitgliederfelder sollten privat sein. ceco vor 5 Jahren 2
@Xiang `ArrayList` verwendet ein zusammenhängendes Array unter der Haube, während 'LinkedList` eine nicht zusammenhängende Kette von Knoten verwendet. David Harkness vor 5 Jahren 2
Ja, ich habe über LinkedList gesprochen, die im obigen Code verwendet wird. wayfare vor 5 Jahren 0
1
wayfare

Insgesamt ein gutes Design. Es gibt jedoch einige Punkte, auf die Sie achten sollten.

Zugriffsmodifizierer: Ihr Code verfügt über einige Eigenschaften als öffentlicher und auch als öffentlicher Getter. Das macht keinen Sinn. Sie sollten die Zugriffsmodifizierer sorgfältig auswählen. Jeder kann auf das untergeordnete Element (NodeArray) zugreifen und auf null setzen, wenn dieser Code von einem Benutzer als API verwendet wird.

public Node[] child;

public Node[] getChild()
{
    return child;
}

Das sollte sein

private Node[] child;

public Node[] getChild()
{
    return child;
}

public void setChild(Node node){
 // set Node to first empty location in Node array
  if(node != null)
    child[nonEmptyLocation] = node;
}

// if you want to set whole array
public void setChildren(Node[] nodes){
  if(nodes!= null && nodes.length > 0)// check that the data is valid
    this.nodes = nodes;
}

public class Graph {

   public int count; // num of vertices

Statische Funktionen: Ihre DFS- und BFS-Funktionen sind nicht statisch. Ich kann mir keinen Grund dazu vorstellen, wenn Sie die Funktion statisch erstellen. Besser machen es konsistent.

Sie sagen also, ich sollte in diesen Methoden private verwenden und Klassen in das Hauptprogramm importieren, um die Methoden zu verwenden? was könnte ein anderer Weg sein, es zu tun fscore vor 5 Jahren 0
Nein, die Art und Weise, wie dies getan werden sollte, besteht darin, die Klasseneigenschaften als privat zu definieren und dann öffentliche Setter / Getter bereitzustellen. Auf diese Weise haben Sie die Kontrolle darüber, wie die Daten geändert werden. wayfare vor 5 Jahren 0
Können Sie meinen Code bearbeiten und mir einige Beispiele von dem zeigen, was Sie sagen? fscore vor 5 Jahren 0
Code bearbeitet Sollte jetzt leicht verständlich sein. wayfare vor 5 Jahren 0
Im Allgemeinen ist es eine gute Idee, Getter und Setter bereitzustellen, um zu verhindern, dass sich andere Personen mit dem internen Zustand Ihres Objekts mischen. Diese speziellen Getter und Setter erhöhen jedoch die Komplexität, bieten jedoch keinen großen Schutz vor "public Node [] child". 200_success vor 5 Jahren 0
Genau. Der im Beitrag bereitgestellte Code dient dazu, das Konzept zu demonstrieren und keinen größeren Datenfehler zu erzielen. Die Dateneinstellungsregeln hängen stark vom Kontext des Problems und vom technischen Design des Moduls ab. wayfare vor 5 Jahren 0