Depth First Search & Breadth First Search implementation

我已经实现了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;

}

该代码是用于学习/分配目的还是用于工作软件/应用程序？

@Xiang m尝试自行学习图和各种搜索算法以提高树和图的效率

我发现它很有用-opendatastructures.org/ods-java/12_3_Graph_Traversal.html。用伪代码清楚地说明所有内容。

#1 楼

数据结构

您的术语有点过头了。树木有根和孩子。另一方面，任意图……我认为“原点”和“邻居”会更合适。一旦执行Node或dfs()，该图将被“破坏”。您将无法将所有节点重置为未访问状态。（嗯，您可以手动执行此操作，因为毕竟bfs()是一个公共字段。但这也很讨厌。）相反，我建议Node.state和dfs()保留bfs()的访问节点。一旦遍历完成，就丢弃该集合。
状态。访问：从未使用过该值。
Node.getNode（）：名称表明它将返回单个节点，但是不会返回t。另外，通过返回整个数组以及数组的原始值而不是副本，您可以让调用者以未经批准的方式更改图形的连接。更好地提供迭代所有邻居并获取特定邻居的方法。

子顶点数组：HashSet构造函数说：Node但是，vertices = new Node[8];检查addNode()。您应该改为对if (count < 10)进行测试。

如果超出容量，则不应打印到vertices.length。而是引发一个异常，以便调用者可以决定如何处理它。

更好的是，使用可扩展的数据结构，这样您就不必处理容量限制。一个简单的替代方法是使用System.out，但请继续阅读... Graph.createNewGraph（）：很麻烦。能够写

Graph g = new Graph();
g.addEdge("A", "B");
g.addEdge("B", "C");
…
return 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);
        }
    }
}

/>遍历

您的ArrayList<Node>和dfs()方法只能打印节点名称。您无法将代码重用于其他任何事情，因为bfs()调用与图形遍历代码混合在一起。最好实现System.out.print()，以便调用者可以决定如何处理每个节点。

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

广度优先迭代器是原始代码的非常简单的翻译，主要区别在于迭代器现在负责跟踪访问了哪些顶点。

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<String>的想法，而改用visitor模式，则可以保留相同的递归代码结构。）

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

测试

这个问题值得更好的测试。原始代码始终将其输出打印到Iterator，因此没有编写单元测试的好方法。现在，您可以对结果进行任何操作，因此可以编写适当的单元测试。

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

\ $ \ begingroup \ $
最好使用什么：Graph.vertices与Node.child？
\ $ \ endgroup \ $
–fscore
2014年4月29日23:42

\ $ \ begingroup \ $
都没有！而是存储Graph.edges。
\ $ \ endgroup \ $
– 200_success
2014年4月29日在23:44

\ $ \ begingroup \ $
迭代器的折衷方案是什么？只是为了避免两行代码，使用迭代器就足够了吗？
\ $ \ endgroup \ $
–fscore
2014年4月29日在23:47

\ $ \ begingroup \ $
实现Iterator的主要好处是每个人都可以立即知道如何使用它。迭代器为调用者提供了非常方便的界面，但以使深度优先遍历代码复杂为代价。
\ $ \ endgroup \ $
– 200_success
2014年4月30日19:25在

\ $ \ begingroup \ $
@ 200_success为什么您建议将边的类型设置为私有Map > edge = new HashMap >（）; ??
\ $ \ endgroup \ $
–莫娜·贾拉勒（Mona Jalal）
16-3-21在9:50

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

}

I已经使节点类型成为通用类型，只是因为它是可能的。

这里有测试来证明其用法。，控制权的倒置使调用者的处境更加尴尬。但是您仍然可以指定任意动作。同样，使用Java 8方法引用，这种简单情况很容易-您只需编写graph1.preOrderTraversal("A", System.out::println)即可。

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

Graph类中也存在一个错误，因为您的数组限制为8个条目，但您要填充直到您的计数器> =10。

您的Node类包含带有getter的公共成员？我会将它们设为私有；）

我还将删除多余的注释。
例如：for循环中的“为每个孩子”。由于每个人都知道for循环的作用。

让您的代码成为描述：

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

\ $ \ begingroup \ $
为什么要使用列表而不是数组？有什么权衡？
\ $ \ endgroup \ $
–fscore
2014年4月29日在21:14

\ $ \ begingroup \ $
数组是连续分配的内存，在列表中没有保证。因此，访问数组中的对象要快得多。 *数组的大小不是动态的，但列表是动态的。
\ $ \ endgroup \ $
–机票
2014年4月29日在21:19

\ $ \ begingroup \ $
对我来说，列表更易于处理。他们不会抛出讨厌的溢出错误。您不需要计数器，因为列表已包含这些信息。
\ $ \ endgroup \ $
–ceco
2014年4月29日在21:19

\ $ \ begingroup \ $
不，吸气剂必须是公开的。成员字段应该是私有的。
\ $ \ endgroup \ $
–ceco
2014年4月29日在21:48

\ $ \ begingroup \ $
@Xiang ArrayList在后台使用连续数组，而LinkedList使用不连续的节点链。
\ $ \ endgroup \ $
– David Harkness
2014年4月29日在22:15

#4 楼

总体来说不错的设计。但是，您需要注意几点。

访问修饰符：
您的代码具有一些公共属性和公共获取方法。这是没有道理的。您应该仔细选择访问修饰符。如果此代码被某些用户用作API，则任何人都可以访问子节点（NodeArray）并将其设置为null。

/>

public Node[] child;

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

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

您的DFS和BFS功能不是静态的。当您将create函数设置为静态时，我认为没有理由这样做。最好使其一致。

\ $ \ begingroup \ $
所以您说我应该在那些方法中使用private并在主程序中导入类以使用这些方法？这可能是另一种方式
\ $ \ endgroup \ $
–fscore
2014年4月29日在21:25

\ $ \ begingroup \ $
不，应采用的方法是将类属性设置为私有，然后提供公共设置器/获取器。这样，您将可以控制如何更改数据。
\ $ \ endgroup \ $
–机票
2014年4月29日在21:29

\ $ \ begingroup \ $
您可以编辑我的代码，并向我展示一些您在说什么的示例吗？
\ $ \ endgroup \ $
–fscore
2014年4月29日在21:35

\ $ \ begingroup \ $
代码已编辑。现在应该很容易理解。
\ $ \ endgroup \ $
–机票
2014年4月30日0:24在

\ $ \ begingroup \ $
一般来说，提供getter和setter来防止其他人干预对象的内部状态是一个好主意。但是，这些特定的获取器和设置器增加了复杂性，但没有对公共Node []子项提供太多保护。
\ $ \ endgroup \ $
– 200_success
2014年4月30日19:31

编程黑洞网

Depth First Search & Breadth First Search implementation

评论

#1 楼

评论

#2 楼

#3 楼

评论

#4 楼

评论