JavaScript Coding Test Course, Counting the Number of Connected Components

Problem Description

This problem involves counting the number of connected components in a given undirected graph. An undirected graph consists of vertices (v) and edges (e) and represents the connectivity between vertices. That is, if there is an edge between two vertices, then these two vertices are directly connected. The connected components of a graph refer to a set of vertices that cannot be connected further. In this problem, there can be multiple sets, and the vertices within each set can reach each other but cannot reach vertices in other sets. For example, consider the following graph.

          0 --- 1     3 --- 4
                |
                2
        

In this graph, there are two connected components: {0, 1, 2} and {3, 4}. Therefore, the number of connected components is 2.

Input Format

The function takes two parameters:

• n: Number of vertices (0 ≤ n ≤ 1000)
• edges: A list of edges, where each edge is an array consisting of the vertex numbers. Example: [[0,1], [1,2], [3,4]]

Output Format

Returns the number of connected components.

Examples

          Input: n = 5, edges = [[0,1], [1,2], [3,4]]
          Output: 2

          Input: n = 6, edges = [[0,1], [0,2], [1,3]]
          Output: 3
        

Solution Method

To calculate the number of connected components, we can use the DFS (Depth First Search) algorithm. DFS starts from one vertex and explores adjacent vertices deeply, visiting unvisited vertices. By utilizing this algorithm, we can traverse the graph and identify connected components. The steps to implement this are as follows:

1. Graph Creation: Convert the graph from the information of vertices and edges into an adjacency list format.
2. Create a Visited Array: Create an array to check if each vertex has been visited.
3. Implement DFS: Use a recursive function to implement DFS traversal, checking all vertices connected to each vertex upon visiting it.
4. Count Connected Components: Visit all vertices, increasing the count of connected components every time a new starting vertex is discovered.

JavaScript Code Implementation

            
            function countConnectedComponents(n, edges) {
                // Convert the graph to an adjacency list
                const graph = Array.from({length: n}, () => []);
                edges.forEach(([u, v]) => {
                    graph[u].push(v);
                    graph[v].push(u);
                });

                const visited = new Array(n).fill(false);
                let count = 0;

                function dfs(node) {
                    visited[node] = true;
                    for (const neighbor of graph[node]) {
                        if (!visited[neighbor]) {
                            dfs(neighbor);
                        }
                    }
                }

                for (let i = 0; i < n; i++) {
                    if (!visited[i]) {
                        dfs(i);
                        count++; // Increase count every time a new connected component is found
                    }
                }

                return count;
            }

            // Example execution
            console.log(countConnectedComponents(5, [[0,1],[1,2],[3,4]])); // Output: 2
            console.log(countConnectedComponents(6, [[0,1],[0,2],[1,3]])); // Output: 3
            
        

Complexity Analysis

The time complexity of this algorithm is O(V + E), where V is the number of vertices and E is the number of edges. This is due to the fact that we visit all vertices and edges in the graph. The space complexity is also O(V), which includes the space used to store the visited array and the graph.

Conclusion

In this course, we have implemented an algorithm to count the number of connected components using JavaScript. Graph theory is a very important topic in coding tests, and it is crucial to practice problems related to it thoroughly to build your skills. We hope this helps deepen your understanding through various examples and fosters your own algorithmic thinking.