AC Java Graph DFS solution with adjacency list


  • 44
    public class Solution {
        public boolean validTree(int n, int[][] edges) {
            // initialize adjacency list
            List<List<Integer>> adjList = new ArrayList<List<Integer>>(n);
            
            // initialize vertices
            for (int i = 0; i < n; i++)
                adjList.add(i, new ArrayList<Integer>());
            
            // add edges    
            for (int i = 0; i < edges.length; i++) {
                int u = edges[i][0], v = edges[i][1];
                adjList.get(u).add(v);
                adjList.get(v).add(u);
            }
            
            boolean[] visited = new boolean[n];
            
            // make sure there's no cycle
            if (hasCycle(adjList, 0, visited, -1))
                return false;
            
            // make sure all vertices are connected
            for (int i = 0; i < n; i++) {
                if (!visited[i]) 
                    return false;
            }
            
            return true;
        }
        
        // check if an undirected graph has cycle started from vertex u
        boolean hasCycle(List<List<Integer>> adjList, int u, boolean[] visited, int parent) {
            visited[u] = true;
            
            for (int i = 0; i < adjList.get(u).size(); i++) {
                int v = adjList.get(u).get(i);
                
                if ((visited[v] && parent != v) || (!visited[v] && hasCycle(adjList, v, visited, u)))
                    return true;
            }
            
            return false;
        }
    }

  • 0
    H

    the hasCycle method can be made to a tail recursion.


  • 0
    H

    @HoSi Could you please explain the details?


  • 0
    B

    Java isn't optimized for tail recursion so it wouldn't give any benefit. Good thinking, though. :)


  • 0
    B

    You could probably do away with the check for visited by filling a set with 0 to n-1 as you are creating the adjacency list and then removing each one you visit as you check for a cycle. If the set isn't empty after the check then something was missed. Not an asymptotic difference but just one less O(n) traversal over the list.


  • 0
    R

    I think you can avoid the loop at:
    // make sure all vertices are connected
    by maintaining count of total visited vertices and comparing it to the total number of vertices at the end


  • 0
    W

    @jeantimex Hi, I think you just need do a normal dfs from any node, and do the visit check after that. The tree validation could be guaranteed by checking

    1. # of nodes == # of edges + 1
    2. No self loop

  • 1
    N

    parent is really good idea.


  • 0

    Same idea, but I think List[] is adequate to construct adjacent list. Thanks for sharing!


  • 3

    Can anyone explain some about (visited[v] && parent != v) || (!visited[v] && hasCycle(adjList, v, visited, u) ?


  • 0

    Can anyone help me to figure out the time complexity of this method? Thx!


  • 2
    M

    @huksy.li
    I think it's O( |E| + |V| )


  • 0

    @mycoy thanks!


  • 11
    J

    @Tōsaka-Rin I am confused by that too. So I used the same thoughts but made it more easily understand.

    public class Solution {
        public boolean validTree(int n, int[][] edges) {
            List<List<Integer>> graph = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                graph.add(new ArrayList<Integer>());
            }
    
            // initialize adjacency list.
            for (int i = 0; i < edges.length; i++) {
                graph.get(edges[i][0]).add(edges[i][1]);
                graph.get(edges[i][1]).add(edges[i][0]);
            }
            Set<Integer> visited = new HashSet<>();
            visited.add(0);
    
            // do DFS from vertex 0, after one round DFS, if there is no loop and visited contains all the vertexs,
            // it is a tree.
            boolean res = helper(-1, 0, visited, graph);
            if (!res) return res;
            return visited.size() == n ? true : false;
        }
    
        public boolean helper(int parent, int vertex, Set<Integer> visited, List<List<Integer>> graph) {
            List<Integer> subs = graph.get(vertex);
            for (int v : subs) {
                // if v is vertex's parent, continue.
                if (v == parent) continue; 
                // if v is not vertex's parent, and v is visited. that presents there is a cycle in this graph.
                if(visited.contains(v)) return false;
                visited.add(v);
                boolean res = helper(vertex, v, visited, graph);
                if (!res) return false;
            }
            return true;
        }
    }
    

  • 0
    L

    @jilianggqq Your solution is much easier to understand. Thanks.


  • 0
    L

    @jilianggqq In fact, I think use "pre" instead of "parent" should be better.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.