6.11 Connected Components: how to find connected components in graph | Graph Theory

hi guys welcome back today's topic is connected components I will discuss with you what are connected components and how to find out connected components from a given graph okay so what are connected components in a graph connected components either up or defined can either then you can say set of vertices which are reachable okay or you can say connected component is a sub graph in which any two vertices are connected by paths and know what SS is connected with any other vertices in the super graph okay let us take an example suppose this one is our graph you just by looking in this graph you how to check is everything connected or you can see it every you know disconnected media with each other yes every node is connected with each other so this graph is having only one connected component okay and let us suppose we have this graph and now this one is our graph how many connected components are there is every node is connected with each other yes every node is connected with each other okay then this graph is having only one connected component now let us suppose you modify this graph and we delete this edge now this one is your graph fine how many connected components are there by looking in this graph how many can you come is is everything connected no everything is not connected see this one this one this one this one these five nodes are connected so this is one connected component now we have these two sorry nodes also and these are connected with each other so this one is a second connected component in this graph as I have told you the definition of connected components is basically a sub graph say this one is a graph or you can say super graph the connected components here we have 1 & 2 the connected components is a sub graph in which every node yeah every what is connected by parts see in this component in this component every what X is connected by these paths this one this one this one this one or this one okay and second condition was what no what this says is connected with any other vertex in the super graph super graph is this one and it's graphically the vertex connected in here with any other vertex because in super graph we have two more vertices but these vertices are not connected with these vertices so this is what the connected component so in this graph we have two connected components now let us suppose I delete this edge now how many connected components are there in this graph we have three connected components okay this is also known as one connected component this is also known as one can I get component and this is one can I get components one two and three three connected components we have if suppose our graph is like this this one was our super graph so in this graph how many connected components are there one is this one one is this one and one is this one three connected components are there so see this is a pictorial view by looking at this graph you can easily tell how many connected components are there but in case of computer we have to use some algorithm to find out these connected components okay so what algorithms can be used either DFS or BFS depth-first search or breadth-first search I'll discuss with you how to find out connected components using that DFS algorithm with the help of one example okay let us see now I will discuss the algorithm to find out the connected components in a given graph and either you can use DFS traversal or DFS traversal in this elbow i am using DFS traversal to find out the connected components the main funda is many times the DFS traversal would be cold there would be the same number of components CP FS traversal is called three times then there would be three in the number of connected components if DFS traversal is called two times in the graph then there would be two connected components okay like this we will call this suppose DFS graph from this vertex zero then we can traverse this this one then two then three but you cannot go further from three because there is no connected as this three is not connected with any four five six or seven fine so here you have to store then again DFS traversal would be called from this four and we can go to five we can traverse this five only we cannot go anywhere else then again DFS traversal will be called from six then we can traverse six seven and eight and that's it so how many times DFS traversal has been called that is 4 3 times 2 we have 1 2 3 3 number of connected components in this graph ok by looking at this graph only you cannot know you can also rail this one is one connected component this one is second this one is third let us take this example suppose we have this graph this is complete graph from having vertex from 0 to 8 and graph is having vertex V and then edges set of edges e connected components from a graph G you have to find out the very first thing is assigned a flag value minus 1 to all the vertices in the graph in the elbow also I have written the same line for each vertex V belongs to n here n is total number of vertices in this graph so n is here 0 2 it means 9 we have n value is 9 flag of V would be minus 1 we would be from 0 to 8 and flag of 0 to 8 could be minus 1 in starting count value is 0 count would be then a total number of connected components okay now for in V is equal to 0 will strut let us suppose from the vertex 0 thortex ok starting my over V value 0 we left in and yes lose nine and zero is less than nine if condition is true then we will enter in this four loop okay now in the for loop what is written if flag of V is equal to is equal to minus one if this condition is true yes this one is true biggest flag of zero flag of zero is what minus one yes this condition is true then we will go to the if condition and an if condition what we have called a DFS V flag DFS has been called fine so here we value is zero and flag would be flag is minus 1 so this DFS would be cold and the control will go to here only this is function calling and then control will go to the function definition here we have defined this DFS in to be in flag here we value is 0 and flag is minus 1 okay then what is there flag of V is 1 if flag is minus 1 after entering this function that flag of that vertex should be converted to 1 so flag of 0 would be 1 minutes this vertex has been visited or traversed fine 1 or 1 maybe we can say true or here minus 1 is false ok now see out we will print this week finally the output would be we would be printed the value of e is 0 ok 0 1 we printed now next is what for each adjacent node you if we now will check the adjacent node of this 0 how many additional and addition node are there 1 and 3 we have to at the same node so for each at the st. node U of P find out if flag of U is minus 1 right we have this adjacent node 1 and 3 let us take we will take this one first of all now u value is what here we have U is equal to what flag of u flag of 1 is minus 1 yes that is minus 1 in that case what we have done this condition is true then DFS will be called recursive this is recursive code in this function then DFS here will go fine DFS would be cold and this one is un flap you value is one and flag is minus one so DFS will be hold now here we have one and flag is minus one now we are at this place again flag of V is equal to 0 now VK Otsuka apni the vertex 1 now this flag of this would be 1 that is true and see out V then we will print this one okay next condition for each adjacent node U of V see now V is what this one okay and find out the each adjacent node of this one one guy descend note how many of us that 2 and 0 also okay 0 and 2 for each at the st. node U of we if flag of U is minus 1 now let us take adjacent node to fine now are you becomes 2 flag of you suppose we are taking at the same node u u is suppose we are taking 2 now user to flag of 2 is minus 1 yes this is minus 1 in that case again DFS would be cold here what now we have u value 2 and flag is minus 1 okay again DFS will be cold recursively ok into week V becomes what what value will be posed past 2 and minus 1 okay now flag of V is 1 now here V is what to this vertex to the flag of this would become 1 okay and see out we will print this to fine now suppose in this case we if we have this at this place at the vertex 1 so for each addition node U of we you can say why we go to this second node additional table cos 0 behind so if your go to 0 if you will take 0 - vortex then flag of you flag of you is flag of zero is what - one no this one is not minus one okay then we will not call this function BFS again okay that is why we will check for each at this end node is zero K minus one and then again we have yeah one more additional that is to to to kill a check who got you take it now check to pass okay that is to has been printed now for eat at this end node you OFI now V is what this to node to now address a node of 2 is 1 and 3 ok suppose one is there I'm one goal it thing flag of you is we have taken us one ok flag up one is what is this - one no this is not - one take a leave it say we have to check this condition for each node for each adjacent node and now we will check for this 3 because the addition node of 2 is 1 and 3 now 4 check for 3 now view is what 3 okay now this one is 3 flag of 3 is minus 1 yes this one is true then again DFS recursively will be cold now you value is what 3 and flag is minus 1 again this is cold now V value is what 3 and this one is minus 1 I will go to this loop flag of V now V key value K ok up key node 3 then this would become 1 and we would print this 3 okay now check for each adjacent node you OFI now B value is what this 3 by V values what this 3 find out 3 K address and note we have 0 & 2 if flag of U is equal to 0 minus 1 yes there any adjacent node of 3 having flag minus 1 no with this condition is not true ok so no now what would happen we have checked out each see this condition would be check for each addition node so for 2 & 4 4 0 & 4 - we have checked for 0 also that condition is not true we have checked for - also this condition not true now the control will be out from this loop okay and the control will go where where the function has been cold from here to back to this point only okay now again you can say at this point only then now what would happen count plus plus count value is what zero now count boom become one okay okay count food become one will be out from this if statement but we are not out from this for statement because here what would happen we plus plus so you cannot say that B would be 1 why so because V is already three we has already been updated we has reached to the node 3 from this function only now we would become what for hi now again check that go check of the condition for is less than 9 yes this condition is true then can we enter in this for loop if flag of V is equal to Sigma is equal to minus 1 yes flag of 4 is minus 1 this condition is true then you will enter there in this if condition if condition we again get how we will call this DFS now value of V is what for and flag is minus 1 this function will be cooled the control would go to here only ok now then what is the value of V what has been passed for and flag value is minus 1 fine now flag of V is equal to 1 we'll set this flag 1 okay now see out four would be printed here you can write see out / then four would be printed next line because the four would be printed in this line only then you cannot differentiate how many connected components are there and what are the vertices in that component so better if you will be right after the C out sorry count plus plus we write C out / and that is why this four would be printed in next line okay now we have printed this for for each at this end node U of V now here BV is what for at this end node of this 4 is 5 now you give value up Naposki are here 5 if flag of 5 is minus flag of u is minus 1 yes flag of 5 is minus 1 this condition is true then again this recursively DFS would be cold and the value of U is what 5 at this place and flag is minus 1 flag of 5 is minus 1 now here 5 would be passed and here is minus 1 then flag off me we value is there what 5 the flag of 5 would be set is 1 and see out this fight would be printed again check for each adjacent node U of V now V value is about 5 now check out the adjacent node of this 5 at this in order 5 is only we have one adjacent node that is 4 but this condition is not true for forward flag of 4 is minus 1 no this one is 1 this condition is not true and we have only one at this end node so we cannot check out further then finally we would go back to this point and then count plus plus and count would become now what - ok and see out / and here we would go to the next line fine now see out plus plug our see out / and has been printed we are out from this F condition but we are not out from this for loop again V plus plus fine then we what is the recent value of V what has been passed back that is value has been updated to Phi phony then V plus plus would be 6 now you cannot say that pal happening past 40 forty I'm gonna start yet at all five of you know it's functionally how Mary we keep a lookout you can fight then we give value would be six if flag of 6 is minus one yes this one is minus one this one is true again we would go to this DFS now we value would be passed as 6 and minus one now we would go to again here only V value is 6 and this one is minus one flag of we would be set as one six would be printed in next line now check out for each addition node u of V V value is 6 adjacent node is 7 and 8 first of all we will take this 7 now first you value is 7 flag of you value is now 7 flag of 7 is minus 1 here this condition is true then DFS would be gold and you is 7 and minus 1 would be passed here we have 7 and minus 1 fine flag of VV is 7 that would be set to 1 only and 7 would be printed okay now for each addition node U of V now V is what 7 7 Gydesen node happening by 6 or 8 we will check for suppose 8 because 6 KH occur ok this condition would not be true then again I'm the skellige occurring 8 k liy object cut away okay yet clearly how many check here sorry and that case what would happen same would be it would be passed here minus 1 again this would be 1 fine and it would be printed for each else in node of you of me 8 cards is in or 6 and 7 hem but this condition is not true for any node then we would go back to this point and count will be 3 see out plus 4 plus plus will go to the third line okay now out of this if statement now what is value of this V plus plus already this value has been updated to 8 now V plus plus they say over that would be 9 but 9 is not less than 9 this condition is not true then we Oh out of this four loop out of this four loop these are the bracket four for loop and out of this for loop what else has been printed see out count count value is worth three then three would be printed okay and we are out of this loop how many components are there three components are they account value is three so that is why we have three connected components in this graph so this is how you can check out this you know the kind of connected components in a given graph okay you would just take one example and place out this example with the help of one code okay so I'll see in the next video till then bye-bye take

Channel: Jenny's lectures CS/IT NET&JRF

Views: 87,678

Rating: 4.8668594 out of 5

Keywords: connected components, connected graph, what is graph, types of graphs, vertices and edges, directed and undirected graph, data structure, algorithms, jenny lamba, jennys lectures, jayanti khatri lamba, dfs, undirected graph, ugc net, ugc net syllabus, csir net, youtube, youtube channels, ugc net computer science, gate, bsc computer science, gate syllabus, computer science, engineering, graph theory, strongly connected components

Id: 9esCn0awd5k

Length: 20min 37sec (1237 seconds)

Published: Sat Feb 16 2019