java - 深度优先搜索算法工作原理

Question

深度优先搜索无法正常工作。老实说，我不确定这是否是当前的实现方式。我是实现图表的新手，并且想成为这方面的专家。我哪里出错了，我不明白如何在 dfs() 函数中打印元素，这样我就可以知道 dfs 应该是什么样子。

是否推荐子元素的 getter 和 setter 方法？

这是我的代码:

    package graphs;

    public enum State {

        Unvisited,Visiting,Visited;

    }

    package graphs;

    public class Node {

        public Node[] adjacent;
        public int adjacentCount;
        private String vertex;
        public graphs.State state;

        public Node(String vertex)
        {
            this.vertex = vertex;
        }
        public Node(String vertex, int adjacentlen)
        {
            this.vertex = vertex;
            adjacentCount = 0;
            adjacent = new Node[adjacentlen];
        }

        public void addAdjacent(Node adj)
        {
            if(adjacentCount < 30)
            {
                this.adjacent[adjacentCount] = adj;
                adjacentCount++;
            }
        }

        public Node[] getAdjacent()
        {
            return adjacent;

        }

        public String getVertex()
        {
            return vertex;
        }

    }

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


    package graphs;

    import java.util.Stack;
    import graphs.State;
    public class Dfs {

        /**
         * @param args
         */

        static boolean visited[];

        public void dfs(Node root)
        {       
            if(root == null) return;

            Stack<Node> s = new Stack<Node>();
            s.push(root);
            root.state = State.Visited;

            System.out.println("root:"+root.getVertex() + "\t");
            while(!s.isEmpty())
            {
                Node u = s.pop();
                for(Node n: u.getAdjacent())
                {

                    if(n.state != State.Visited)
                    {
                        dfs(n);
                    }
                }
            }
        }

        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].addAdjacent(temp[1]);
    temp[0].addAdjacent(temp[2]);
    temp[0].addAdjacent(temp[3]);

    temp[1].addAdjacent(temp[0]);
    temp[1].addAdjacent(temp[4]);
    temp[1].addAdjacent(temp[5]);

    temp[2].addAdjacent(temp[0]);
    temp[3].addAdjacent(temp[0]);
    temp[4].addAdjacent(temp[1]);
    temp[5].addAdjacent(temp[1]);

            for (int i = 0; i < 7; i++) 
            {
                g.addNode(temp[i]);
            }
            return g;
        }

        public static void main(String[] args) {


            Graph g = createNewGraph();
            Dfs s = new Dfs();
            //Node[] n = g.getNode();

            s.dfs(g.getNode()[0]);

        }

    }

Answer 1

这里不需要堆栈。仅递归:

public void dfs(Node node) {
    if (node == null) {
        return;
    }

    System.out.println("Node: " + node.getVertex());
    node.state = State.Visited;

    for (Node n : node.getAdjacent()) {
        if (n.state != State.Visited) {
            dfs(n);
        }
    }
}

更新

检查路径是否存在:

public boolean isPath(Graph graph, Node start, Node target) {
    for (Node node : graph.getNode()) {
        if (node != null) {
            node.state = State.Unvisited;
        }
    }

    dfs(start);

    return target.state == State.Visited;
}