如何在给定代码的情况下打印广度第一次横移的结果(Java)

Question

如何使用GitHub中的示例代码输出广度优先遍历的结果？我应该把Main方法放在哪里？谢谢，这是第一个类的代码链接：https://github.com/eugenp/tutorials/blob/master/data-structures/src/main/java/com/baeldung/graph/Graph.java，代码如下：

    package com.baeldung.graph;
    
    import java.util.ArrayList;
    import java.util.HashMap;
    import java.util.List;
    import java.util.Map;
    import java.util.stream.Collectors;
    
    public class Graph {
        private Map<Vertex, List<Vertex>> adjVertices;
    
        Graph() {
        this.adjVertices = new HashMap<Vertex, List<Vertex>>();
    }

    void addVertex(String label) {
        adjVertices.putIfAbsent(new Vertex(label), new ArrayList<>());
    }

    void removeVertex(String label) {
        Vertex v = new Vertex(label);
        adjVertices.values().stream().forEach(e -> e.remove(v));
        adjVertices.remove(new Vertex(label));
    }

    void addEdge(String label1, String label2) {
        Vertex v1 = new Vertex(label1);
        Vertex v2 = new Vertex(label2);
        adjVertices.get(v1).add(v2);
        adjVertices.get(v2).add(v1);
    }

    void removeEdge(String label1, String label2) {
        Vertex v1 = new Vertex(label1);
        Vertex v2 = new Vertex(label2);
        List<Vertex> eV1 = adjVertices.get(v1);
        List<Vertex> eV2 = adjVertices.get(v2);
        if (eV1 != null)
            eV1.remove(v2);
        if (eV2 != null)
            eV2.remove(v1);
    }

    List<Vertex> getAdjVertices(String label) {
        return adjVertices.get(new Vertex(label));
    }
    
    String printGraph() {
        StringBuffer sb = new StringBuffer();
        for(Vertex v : adjVertices.keySet()) {
            sb.append(v);
            sb.append(adjVertices.get(v));
        }
        return sb.toString();
    }

    class Vertex {
        String label;
        Vertex(String label) {
            this.label = label;
        }
        
        @Override
        public int hashCode() {
            final int prime = 31;
            int result = 1;
            result = prime * result + getOuterType().hashCode();
            result = prime * result + ((label == null) ? 0 : label.hashCode());
            return result;
        }
        
        @Override
        public boolean equals(Object obj) {
            if (this == obj)
                return true;
            if (obj == null)
                return false;
            if (getClass() != obj.getClass())
                return false;
            Vertex other = (Vertex) obj;
            if (!getOuterType().equals(other.getOuterType()))
                return false;
            if (label == null) {
                if (other.label != null)
                    return false;
            } else if (!label.equals(other.label))
                return false;
            return true;
        }

        @Override
        public String toString() {
            return label;
        }


        private Graph getOuterType() {
            return Graph.this;
        }
    }
}

下面是第二个类的链接：https://github.com/eugenp/tutorials/blob/master/data-structures/src/main/java/com/baeldung/graph/GraphTraversal.java，代码如下：

    package com.baeldung.graph;
    
    import java.util.LinkedHashSet;
    import java.util.LinkedList;
    import java.util.Queue;
    import java.util.Set;
    import java.util.Stack;
    
    import com.baeldung.graph.Graph.Vertex;
    
    public class GraphTraversal {
        static Set<String> depthFirstTraversal(Graph graph, String root) {
            Set<String> visited = new LinkedHashSet<String>();
            Stack<String> stack = new Stack<String>();
            stack.push(root);
            while (!stack.isEmpty()) {
                String vertex = stack.pop();
                if (!visited.contains(vertex)) {
                    visited.add(vertex);
                    for (Vertex v : graph.getAdjVertices(vertex)) {              
                        stack.push(v.label);
                    }
                }
            }
            return visited;
        }
    
        static Set<String> breadthFirstTraversal(Graph graph, String root) {
            Set<String> visited = new LinkedHashSet<String>();
            Queue<String> queue = new LinkedList<String>();
            queue.add(root);
            visited.add(root);
            while (!queue.isEmpty()) {
                String vertex = queue.poll();
                for (Vertex v : graph.getAdjVertices(vertex)) {
                    if (!visited.contains(v.label)) {
                        visited.add(v.label);
                        queue.add(v.label);
                    }
                }
            }
            return visited;
        }
    }

Answer 1

如果我正确理解了您的问题，您正在尝试打印一个Graph，但不确定将main()方法放在哪里。如果只是测试代码，您可以简单地将其放在图形类中，但是如果您试图使用这个类构建一个项目，那么您可能希望创建一个不同的类来存储main()方法。

打印很简单，因为他们给出了一个Set<String>。只需在该方法返回被访问的节点之前添加以下行。这会将访问节点列表转换为字符串。

System.out.println(visited.toString());

您可以使用以下代码对其进行测试：

static Graph createGraph() {
    Graph graph = new Graph();
    graph.addVertex("Bob");
    graph.addVertex("Alice");
    graph.addVertex("Mark");
    graph.addVertex("Rob");
    graph.addVertex("Maria");
    graph.addEdge("Bob", "Alice");
    graph.addEdge("Bob", "Rob");
    graph.addEdge("Alice", "Mark");
    graph.addEdge("Rob", "Mark");
    graph.addEdge("Alice", "Maria");
    graph.addEdge("Rob", "Maria");
    return graph;
}

public static void main(String[] args) {
    Graph graph = createGraph();
    GraphTraversal.breadthFirstTraversal(graph, "Bob");
}

这就给出了：

[Bob, Alice, Rob, Mark, Maria]

此外，您还评论说，当您尝试添加顶点时，会得到一个NullPointerException。没有足够的信息来找出为什么会出现异常，但检查单元测试可能会对您有所帮助，可以找出如何使用这个类。单元测试是here。

Answer 2

这里给出了这个例子https://www.baeldung.com/java-graphs

代码声明了adjVertices，但并没有实际创建它。您需要在下面添加，以修复空指针异常。

private Map<Vertex, List<Vertex>> adjVertices = new HashMap<Vertex, List<Vertex>>();