Is there anything wrong with DFS on the graph?-CodePudding

I'm going to do DFS in Java. However, there is a problem of revisiting vertex even if check

Here is Graph Class

class Graph{
    class Node{
        int vertex;
        int cost;
        boolean marked;
        
        Node (int vertex, int cost){
            this.vertex = vertex;
            this.cost = cost;
            this.marked = false;
        }

        public int getVertex() {
            return this.vertex;
        }
    }
    
    List<ArrayList<Node>> adlist;
    int size;
    
    Graph(int initsize){
        adlist = new ArrayList<ArrayList<Node>>();
        this.size = initsize;
        for(int i = 0; i < initsize; i  ) {
            this.adlist.add(new ArrayList<Node>());
        }
    }
    
    public void put(int start, int dest, int weight) {
        this.adlist.get(start).add(new Node(dest, weight));
    }
    
    public void dfs(Graph root, int index) {
        Stack<Integer> stack = new Stack<>();
        stack.push(index);
        
        while(!stack.isEmpty()) {
            int r = stack.pop();
            
            for(Node i : root.adlist.get(r)) {
                if(i.marked == false) {
                    i.marked = true;
                    stack.add(i.getVertex());
                }
            }
            System.out.printf("%d ", r);
        }   
    }
}

For example, given a graph like this

(0, 1), (0, 5), (1, 2), (1, 3), (1, 4), (2, 0), (3, 4), (4, 2)

I think the correct dfs answer is 0 5 1 4 2 3

This code answer is 0 5 1 4 2 0 3 4 2

Is there anything I missed?

CodePudding user response：

The problem is that you always create a new Node for each edge. For example, if you have an edge from 0 to 2 and another one from 1 to 2:

You add to list 0 a new Node 2.
You add to list 1 a new Node 2.

These two nodes are both numbered 2 however they are different objects. This means if you mark one of them the other one is still unmarked. Therefore you`re dfs traverses both of them as if they are different nodes.

In order to mitigate your problem, you could save the marked nodes with a Set instead of the Node objects. In this set you simply remember the number you have already seen:

public void dfs(Graph root, int index) {
    Set<Integer> marked = new HashSet<>();
    marked.add(index);
    
    Stack<Integer> stack = new Stack<>();
    stack.push(index);
    
    while(!stack.isEmpty()) {
        int r = stack.pop();
        
        for(Node i : root.adlist.get(r)) {
            int vertexNum = i.getVertex();
            
            if(!marked.contains(vertexNum)) {
                marked.add(vertexNum);
                stack.add(vertexNum);
            }
        }
        System.out.printf("%d ", r);
    }   
}