给定此代码 (Java) 如何打印宽度优先横向的结果

Question

如何使用 GitHub 中的示例代码打印广度优先横向的结果？我应该把 Main 方法放在哪里？谢谢，这是第一个 class 的代码 link： 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;
        }
    }
}

这是第二个 class 的 link： 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() 方法放在哪里。如果你只是测试代码，你可以简单地将它放在图表 class 中，但如果你试图使用这个 class 构建一个项目，你可能想要制作一个不同的 class 存储 main() 方法。

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

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。没有足够的信息来弄清楚为什么会出现异常，但是检查单元测试可能有助于您了解如何使用 class。单元测试是 here.

Answer 2

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

代码正在声明 adjVertices 但实际上并未创建它。您需要在下面添加而不是修复空指针异常。

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

给定此代码 (Java) 如何打印宽度优先横向的结果

How to print the results of a breadth first transversal given this code (Java)

java

directed-graph

depth