so in this video we will be learning about connected components in a graph now what do we mean by connected components till now we have seen uh graphs like this if you remember well enough i've also seen graphs like this in the first lecture i told you this is also a graph it might be a binary tree but this can also be called as a graph this is a connected graph so we can also call this as a graph but what if i ask you is this a graph like if i show you something like this is this a graph then you might say yes remember this is a graph this is a graph this is a graph this is a graph there are four graphs this is a single node this can also be treated as a single node you're correct you're absolutely correct these are four graphs but can i say these four graphs can they be one single graph you might say nose driver they are not connected this is where the definition connected components come in so if i try to number them for an example one two 3 4 5 6 7 8 9 10 okay some number there imagine someone comes up and sees the definition of graph given an undirected graph with ten notes one two three four five six seven eight eight edges and he says there just to be one two one three two four three four okay five six six seven five seven and eight nine he just tells you about these eight edges so apparently it's a graph it's a graph which is in four pieces it's a graph which is in one piece two piece three piece four piece the last one being a single guy so this is what we call components instead of piece it's uh four components the graph has been broken down into four different components so next time you see two different portions and they're not connected don't say that those are not graphs so these are four different components of a single graph yeah they could have been four different graphs but according to the question and the input you can see them to be a part of a single graph so you will be applying a lot of algorithms going forward okay applying a lot of algorithms will be learning about algorithms assume a traversal algorithm okay assume a traversal algorithm will not take any name because i haven't uh taught you that so what will happen in future is if assuming you're doing a travis algorithm you'll be like one two four five assume you started a journey and you start like one then you go to two then you go to four then you go to three so on this traversal you will never be able to reach these components you will be uh you will never be able to reach these components this is why any traversal that you will do any traversal you will always use something as a visited array yes you will always use something as a visited array remember the concept visited array over here we have 10 nodes so what you'll do is you'll create an array of 11 size starting from the zeroth index and you can go on till the 10th index so the size of the array will be 11 and what you will do is remove this you will always run a loop for any algorithm from 0 and this node numbering is from 1 to 10 so you can always run a loop from 1 to 10 always and if the node is not visited remember this if the node is not visited you will call the traversal algorithm from that node i'll explain you know what happens you might be confused what is happening but let's understand so initially what you'll do is you'll see everyone to be unvisited which is false okay everyone initially is unvisited so thereby it will be false so what happens is when you start your traversal from one and you see one is unvisited so you see one is unvisited yes the if says one is unvisited so you go and say traversal of one traversal of one so one starts a traversal and the traversal algorithms are designed in such a way that they will traverse the entire connected portions of the graph entire connected portions of the graph so it goes to 1 goes to 2 goes to 4 and goes to 3 so apparently it will mark because it went to everyone right it went to everyone so it will mark everyone as visited because it traversed everyone now the traversal i will move to two so it will see who is not who is already visited in my traversal yes in my traversal i have already visited one two three four so i'll not go for two then i'll go to three i'll not go then i'll go to four i will not go next when i go to five i see five over here is zero non-visited then you again call the traversal for five now five will traverse six will travel seven will drop so it's done next you'll be like six seven next it goes to eight eight will say i have not been visited so now you'll go and do a traversal for eight and nine it'll mark it as two next nine travels next you go to ten not travis so ten will be visited so in this way any algorithm in the future you don't just call like you can't do something like okay we start the traversal algorithm from node one and this will make sure that it visits everyone this is not possible if the graph has multiple components because you carefully saw if you started from one would have only visited this portion and these portions would have not been touched so for any traversal algorithm just make sure this is the pattern this is the pattern you always run from one to ten and he check for one not visited go and start it so it will mark everyone whom he can for the next guy again he goes for the next guy again he goes for the next guy again he goes so this is how the traversal algorithms will be executed and this is what the connected components are okay so guys i hope you have understood this video just in case you did please make sure you like this video and if you're new to our channel what are you waiting for hit that subscribe button right over man just hit it and if you haven't checked out our dp series and the hd sheet please make sure you check it out the link will be in the description and here with this i'll be wrapping up this video let's begin the next one till then bye ever forget your golden