如何以深度优先搜索格式打印出这些字母

Question

如何将这些字母打印出深度优先搜索格式如何使输出 return 结果为：[a, c, e, b, d, g, f, h, j] 而不是 [a, j, e, h, f, b, g, d, c]？我认为我的 depthFirstTransversal 方法有问题，但我不知道在哪里。我的目标是最终接受输入：一个CEj e b f h bdg 并得到结果： [a, c, e, b, d, g, f, h, j]

@Yunnosch 我尽力了，让我知道你的想法： depthFirstTraversal 获取输入图和根并将其放入集合

声明已访问 LinkedHashSet 和一个名为 stack

的堆栈

将根“a”压入堆栈当堆栈不为空时：字符串顶点 = stack.pop() =“a” 如果（访问的不包含顶点）将顶点“a”添加到已访问。 For(the vertex v: getAdjVertices(vertex) “a”。它将一个标签作为输入，returns 一个新的顶点和数组列表 Stack.push(v.label)

我认为我的代码 return 是深度优先搜索，但我希望它 return 从第一个输入到最后一个输入的结果，而不是从最后一个输入到第一个的结果。所以如果 c e 和 j 依赖于 a，我希望它是 return a c e j，而不是 a j e c

import java.util.*;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.stream.Collectors;

public class Graph {

    public static 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;
        }
    }
    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;
        }
    }
    static Graph createGraph() {
        Graph graph = new Graph();
        graph.addVertex("a");
        graph.addVertex("c");
        graph.addVertex("e");
        graph.addVertex("j");
        graph.addVertex("b");
        graph.addVertex("f");
        graph.addVertex("h");
        graph.addVertex("d");
        graph.addVertex("g");
        graph.addEdge("a", "c");
        graph.addEdge("a", "e");
        graph.addEdge("a", "j");
        graph.addEdge("e", "b");
        graph.addEdge("e", "f");
        graph.addEdge("e", "h");
        graph.addEdge("b", "d");
        graph.addEdge("b", "g");


        return graph;
    }
    public static void main(String[] args) {
        Graph graph = createGraph();
        System.out.println(GraphTraversal.depthFirstTraversal(graph, "a"));
    }
}

Answer 1

邻居按照您的创建顺序添加到堆栈中，并且您希望按该顺序遍历图形，您创建的 ArrayList 支持该顺序，但堆栈是 LIFO，这意味着对于任意节点，如果邻居是首先添加到堆栈，它最后弹出和处理（例如，如果 c 作为 a 的邻居首先添加到堆栈，它最后弹出，并且首先访问 j）所以你必须最后添加它（相反order）先遍历。

    if (!visited.contains(vertex)) {
        visited.add(vertex);
        List<Vertex> neighbors = graph.getAdjVertices(vertex);
        for (int i = neighbors.size()-1; i >= 0; --i) {
            Vertex v = neighbors.get(i);
            stack.push(v.label);
        }
    }

如何以深度优先搜索格式打印出这些字母

How to print these letters out in depth first search format

java

depth-first-search