Posts Graph is Tree or Not (geeksforgeeks - SDE Sheet)
Post
Cancel

Graph is Tree or Not (geeksforgeeks - SDE Sheet)

PROBLEM DESCRIPTION

You are given an undirected graph of N nodes (numbered from 0 to N-1) and M edges. Return 1 if the graph is a tree, else return 0.

Note: The input graph can have self-loops and multiple edges.

geeksforgeeks

SOLUTION

We can solve this by using a breadth-first search (BFS) approach to traverse the graph while keeping track of visited nodes. We create an adjacency list from the given edges and start the traversal from an arbitrary node (usually node 0). During the traversal, we check for cycles and self-loops, marking each visited node. Finally, we verify if all nodes were visited, which confirms whether the graph is a tree (connected and acyclic).

Major Steps:

  • Create an adjacency list from the edges.
  • Start BFS from an arbitrary node. We should be able to visit all nodes from any given node.
  • Cycle detection: Check for cycles and self-loops during traversal.
  • Visited tracking: Mark nodes as visited and count them.
  • Connectivity check: Ensure all nodes are visited to confirm the graph is a tree.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
class Solution {

    public boolean isTree(int n, int m, ArrayList<ArrayList<Integer>> edges)
    {

        // Create adjacency list representation of the graph
        List<Integer>[] adj = createGraph(n, edges);

        // Array to keep track of visited nodes
        boolean[] visited = new boolean[n];

        // Count of visited nodes
        int visitedCount = 0;

        // Initialize a queue for BFS and start with node 0
        Queue<Integer> q = new LinkedList<>();
        q.add(0);

        // BFS traversal of the graph
        while(!q.isEmpty()){

            // Get the current node
            Integer current = q.poll();

            // If the current node is already visited, there is a cycle
            if(visited[current])
                return false;

            // Mark the current node as visited
            visited[current] = true;

            // Increment the visited nodes count
            visitedCount++;

            // Get all the neighbors of the current node
            List<Integer> neighbors = adj[current];

            // Process each neighbor
            for(int neighbor: neighbors){

                // Check for self-loop, which is not allowed in a tree
                if(current == neighbor)
                    return false;

                // If the neighbor has not been visited yet, add it to the queue
                if(!visited[neighbor])
                    q.add(neighbor);

            }

        }

        // Return true if all nodes were visited (graph is connected)
        return visitedCount == n;
    }

    public List<Integer>[] createGraph(int n, ArrayList<ArrayList<Integer>> edges){

        // Initialize adjacency list
        List<Integer>[] adj = new List[n];

        for(int i=0; i<n; i++)
            adj[i] = new ArrayList<>();

        // Fill the adjacency list with edges
        for(int i=0; i<edges.size(); i++){

            int u = edges.get(i).get(0); // Get node u
            int v = edges.get(i).get(1); // Get node v

            // Since the graph is undirected, add edges in both directions
            adj[u].add(v);
            adj[v].add(u);
        }

        return adj;
    }
}
This post is licensed under CC BY 4.0 by the author.