深度优先搜索&广度优先搜索实现

Question

我已经实现了DFS和BFS实现。我想检查代码是否可读，是否包含任何问题，是否可以改进。

GraphImplementation

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;

}

Answer 1

数据结构

你的术语有点离题。树有根，有孩子。另一方面，任意图，…我认为“起源”和“邻居”更合适。

• 访问标志:将已访问/未访问的标志存储在Node中会影响灵活性。一旦执行了dfs()或bfs()，该图形就会被“毁了”。您将无法将所有节点重置为未访问状态。(嗯，您可以手动完成，因为Node.state毕竟是一个公共字段。但这也很糟糕。)相反，我建议dfs()和bfs()保留一个已访问节点的HashSet。遍历完成后，只需丢弃集合即可。
• State.Visiting:这个值从未被使用过。
• Node.getNode()：名称表示它将返回一个节点，但它不返回。另外，通过返回整个数组和数组的原始值而不是副本，您将允许调用方以未经批准的方式更改图形的连接。最好是提供遍历所有邻居和获取特定邻居的方法。
• 子顶点数组：Node构造函数说：vertices = new Node[8];，但是addNode()检查if (count < 10)。您应该使用vertices.length进行测试。如果超出了容量，则不应将其打印到System.out作为副作用。相反，抛出一个异常，以便调用方决定如何处理它。更好的是，使用可扩展的数据结构，这样您就不必处理容量限制了。一个简单的替代方法是使用ArrayList<Node>，但在…上读取
• Graph.vertices和Node.child:这些数组似乎具有相同的目的，冗余。
• Graph.createNewGraph()：这很麻烦。能写出图g=新图()；g.addEdge("A"，"B")；g.addEdge("B"，"C")；…)不是很好吗？返回g；

我的建议：

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);
        }
    }
}

遍历

dfs()和bfs()方法只能打印节点名。由于System.out.print()调用与图遍历代码混在一起，所以不能将代码重用到其他任何东西。最好是实现一个Iterator，这样调用方就可以决定如何处理每个节点。

此外，DFS和BFS是完成类似任务的两种不同策略。因此，它们应该在两个具有共享接口的类中实现。我建议使用Iterator<String>。

宽度第一迭代器是原始代码的一个非常简单的转换，主要区别是迭代器现在负责跟踪访问过的顶点。

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;
    }
}

不幸的是，您将发现不能再使用递归进行深度优先遍历。相反，您必须使用显式堆栈将其重写为迭代解决方案，这会使代码更加复杂。(或者，如果您放弃了创建Iterator的想法，转而使用访客模式，那么您可以保持相同的递归代码结构)。

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());
    }
}

测试

这个问题值得进行更好的测试。原始代码总是将其输出输出到System.out，因此没有编写单元测试的好方法。现在，您可以对结果做任何您想做的事情，因此可以编写适当的单元测试。

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"));
    }
}

Answer 2

正如我在我的其他答案中提到的，硬编码System.out.println()作为每个节点的操作会损害代码的可重用性。为了让调用者指定要在每个节点上执行的操作，而不需要在深度第一迭代器中展开递归，您可以使用访客模式。

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);
                }
            }
        }
    }

}

我使节点类型成为通用的，仅仅是因为它是可能的。

下面是演示它的用法的测试。

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());
    }
}

正如您所看到的，控制反转会使调用者更加尴尬。但是您仍然可以指定任意的操作。此外，使用Java8方法引用，简单的情况很容易--您只需编写graph1.preOrderTraversal("A", System.out::println)即可。

Answer 3

我会使用列表而不是数组和公共计数器。例如：

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;
   }
}

图形类中也有一个bug，因为您的数组仅限于8个条目，但是您正在填充它直到您的计数器>= 10。

Node类包含带有getter的公共成员？我会把他们变成私人的;)

我也会删除多余的评论。例句：“为每一个孩子”在一个for循环。因为每个人都知道for循环是干什么的。

让您的代码描述如下：

for(Node child: root.getChild())
 if(child.state == State.Unvisited)
  dfs(n);