Apologies for the Video Editing mistake from "06:51 to 07:18", =========================================================== Time Complexity: Suppose, V is the number of Vertices (Nodes), and E is the number of Edges. Basically we are generating an Adjacency List that takes O(V+E) work, and then we are traversing over the adj list to find number of connected components, which also takes O(V+E) time. So, total Overall time complexity would be O(V+E). ---------------------------------------------------------------------------------------------------------------------- Space Complexity: For the space Complexity, we will have to generate an adj list, which takes the space of sum of total Vertices + Edges, O (V+E). Also, we will have to create an extra Array to store all the nodes that we have Visited, which takes O(V) space. So the Overall Space complexity will be O(V+E).
I meant to say that, either Adjacency Metrix or Adjacency List, either would work. But we should only use Adjacency Metrix, when we have a very dense graph (Too many edges). Because Adjacency Metrix is more space consuming data Structure, than Adjacency List. I hope this clarifies the confusion. Thanks
@@DestinationFAANG I mean why in dense graphs adjacency matrix should be used. Is there any proper reasoning behind it. Will adjacency list work slower incase of dense graph. Can you please throw a bit of light on this part
Adj List is stored like this: Node 1: List of Edges for Node 1 Node 2: List of Edges for Node 2 Node 3: List of Edges for Node 3 ................. Now suppose if a Graph has too many edges (Dense Graph), for every single node in an Adj List, we might have to iterate many entries in the "List of Edges" for that particular node. If the number goes too big it might take us O(n) time just to iterate over number of edges, for any particular Node. ==================================================== Adj Metrix is stored like this. E1, E2, E3, E4, E5, E6............ V1 V2 V3 V4 V5 . . . So, in a very Dense Graph, we can create a (V*E) size of 2D Metrix, to store graph details. It is less time consuming to iterate over an ADJ Metrix, compared to ADJ list, if the number of edges are too many. Because finding any particular Node to edge connection can be done instantaneously in ADJ Metrix. But the issue with ADJ Metrix is that it consumes more space compared to adj List, so we only use it when we know that the given input graph is actually a very Dense Graph.
********************** Java Solution **********************
class Solution {
public int countComponents(int n, int[][] edges) {
int counter = 0;
int[] visited = new int[n];
List[] adjList = new ArrayList[n];
for(int i=0; i
Apologies for the Video Editing mistake from "06:51 to 07:18",
===========================================================
Time Complexity:
Suppose, V is the number of Vertices (Nodes), and E is the number of Edges. Basically we are generating an Adjacency List that takes O(V+E) work, and then we are traversing over the adj list to find number of connected components, which also takes O(V+E) time.
So, total Overall time complexity would be O(V+E).
----------------------------------------------------------------------------------------------------------------------
Space Complexity:
For the space Complexity, we will have to generate an adj list, which takes the space of sum of total Vertices + Edges, O (V+E).
Also, we will have to create an extra Array to store all the nodes that we have Visited, which takes O(V) space.
So the Overall Space complexity will be O(V+E).
Imagine opening video someday and hearing
*hello guys, we are still with META, let's not stop leetcoding till we get in Google*
Lol….that would be Funny ... :)
You said when the number of edge are too large we use adjacency matrix. I did not understand that. Why list would not work??
I meant to say that, either Adjacency Metrix or Adjacency List, either would work.
But we should only use Adjacency Metrix, when we have a very dense graph (Too many edges).
Because Adjacency Metrix is more space consuming data Structure, than Adjacency List.
I hope this clarifies the confusion.
Thanks
@@DestinationFAANG I mean why in dense graphs adjacency matrix should be used. Is there any proper reasoning behind it. Will adjacency list work slower incase of dense graph. Can you please throw a bit of light on this part
Adj List is stored like this:
Node 1: List of Edges for Node 1
Node 2: List of Edges for Node 2
Node 3: List of Edges for Node 3 .................
Now suppose if a Graph has too many edges (Dense Graph), for every single node in an Adj List, we might have to iterate many entries in the "List of Edges" for that particular node.
If the number goes too big it might take us O(n) time just to iterate over number of edges, for any particular Node.
====================================================
Adj Metrix is stored like this.
E1, E2, E3, E4, E5, E6............
V1
V2
V3
V4
V5
.
.
.
So, in a very Dense Graph, we can create a (V*E) size of 2D Metrix, to store graph details.
It is less time consuming to iterate over an ADJ Metrix, compared to ADJ list, if the number of edges are too many.
Because finding any particular Node to edge connection can be done instantaneously in ADJ Metrix.
But the issue with ADJ Metrix is that it consumes more space compared to adj List, so we only use it when we know that the given input graph is actually a very Dense Graph.
@@DestinationFAANG thanks a lot sir🔥🔥