Graph Data Structures: DFS, Connectivity & Recursive Algorithms

[00:00:00]I [Music] we continue our study study of graphs we have seen in the previous class that graphs are useful to represent a large number of problems and we saw several problems in the previous class and we came to the conclusion that graphs is an important data structure and it is a data structure which can be used to solve a number of actual real life problems so what did we look at in graphs we Define a graph G to be two items let us take an example first a graph consisted of nodes and edges say this is N1 a graph consists of a set of nodes or a set of vertices V and a set of edges e where V is a set of vertices and e is a set of edges and each Edge is a pair of vertices for example here in this graph V is equal to N1 N2 N3 N4 and E is equal to N1 N2 N1 N4 N2 N3 N1 N3 and n 3 N2 N4 and N3 N4 1 2 3 4 5 6 edges are there so there are six edges here now here this pair is an unordered pair in the sense that N1 N2 is the same as N2 N1 but because this is a undirected graph graph can also be directed and directed graphs are represented by arrows every Edge will have an arrow now if every Edge has an arrow then the pairs here will become ordered pairs and if these arrows are there then the edges will be N1 N1 N2 N2 N3 N2 N4 N4 N3 N1 N3 and N4 N1 instead of the way it is written here sometimes unordered graphs or undirected graphs are represented in a directed fashion by writing both the arrows if you have only one Edge you represent them by putting in both the arrows so a very uh one Convention of representing graphs is by representing directed graphs so that for an indirect undirected graph you represent it by two directed arrows if there is an edge between N1 and two you represent it by two directed arrows so a graph may be an a directed graph or an undirected graph that is you can have a direct un a directed graph undirected graph and for both directed and undirected graphs as we said before you can have weights on the vertices as well as on the edges that is in some cases you can have weights on the edges in some cases you can have weights on the vertices and in some cases you can have weights on both so directed as well as undirected graphs may be weighted or unweighted and weights can be on both nodes as well as edges we use the terminology nodes and arcs so nodes is the terminology we use with vertices and arcs is the terminology which we use with edges now graph theory has got a lot of applications because graph theory is the most one of the most welld developed and wellb built theories now in graph of theory you have got several results related to graphs planar graphs non-planar graphs and several other issues are involved here we shall not go in deeply into those issues of graph Theory and graph mathematics what we are interested in here is graphs as a data structure and we shall see some algorithms or queries on graphs and try to solve those queries on graphs so in terms of a data structure we need to know how to represent a graph as a data structure and how to have uh answer some queries some simple queries on graphs there are several complex queries and complex problems that can be solved on graphs but we shall try to take examples of the basic simple data structure queries on graphs and then see how our algorithm design techniques that we have developed can be used effectively to design these functions efficiently in graphs we have seen how to represent graphs we saw that a graph can be represented by an adjacency Matrix in an adjacency Matrix which we saw in the previous class a graph is represented by an array an array of cities in this example so an array of nodes actually and an edge will be one or zero depending a cell will be one or zero depending on whether the directed Ed C1 from from C1 to C2 is there or not there and uh as we mentioned before undirected graphs will be represented by marking out both of them or by mentioning that it is symetric about one axis and directed graphs can be easily represented weights on graphs that is weights on the edges can be uh implemented by Mark putting the weight values on the cells and weights at a node can be implemented by maintaining a separate uh information with every Noe and marking the weight of the node only in one place this can so a separate array to Mark the node weights and this actually marks the edge weights this is The Edge weight Matrix so this is the adjacent C Matrix representation of a graph the next is the adjacency list in the adjacency list representation we represented a set of nodes where the node numbers node names as well as their weights could be put here and pointers which Mark the edges and C1 that is node C1 is connect node one is connected so if this is node one it is connected to node two and node 3 node two is connected to node one and node 5 as we mentioned in an indirected graph if we want to represent we represent both the edges so in an adjacency list we represent all the edges and therefore for spars Matrix this is a good way of representing the information because we need only the edge information and here most of it would have been zero but if it's a dense Matrix then this is a very good way of doing it because access to an edge is direct whereas here to access whether an edge exists is indirect the third is the direct representation in the direct representation we represented the graph as it exists like this that is if you recall what our original graph was then in the direct representation from C1 we put in a set of linkage nodes and Link it up this is connected from this to this and this to this so we linked it up similarly this is connected to three 1 2 and three so we linked it up so this way we got a direct representation on graphs so we discussed mainly these three representations on graphs and these can be represented in many ways next we try and answer things like certain queries on graphs and what are the queries on this data structure graph Edge based queries node based queries connectivity related queries or these are also called path based queries so a query may be of various types it can be a node-based query where you answer ask questions relating to nodes only what is the weight of a node is this node connected to any other node Etc Edge based queries does this Edge exist if it exists what is the weight of the node weight of the edge these are simple queries on the other hand you can have path-based queries which are more complex and it says that if the is the graph connected in the sense that is there a path from every node to every other node or in on a simple question is there a path from one node to another node given a node number say node number five is there a path from node number five to node number seven Etc so we will see what sort of queries we can answer in such situations Edge based queries can be simply answered and let us see which uh uh data structure is most efficient suppose I ask whether there is an edge or not an edge in an adjacency Matrix it is simply check by checking whether that element exists and we can extract that weight out whereas in an adjacency list we have to go through in an adjacency Matrix answering that query is direct you just access it and in constant time you can answer a single edge query on the other hand in an adjacency list this would be you would have to go through it one by one similarly for a direct representation you would have to access it if you ask it from a node again you would have had to access it and find out whether that uh Edge exists therefore if you have pure Edge based queries either you will implement it uh by a matrix representation or you will Implement a data structure which is more related to edges note based queries can be easily answered by asking out questions related to any node therefore node and Edge based queries are simple and they can be answered easily we come to the path-based queries and the first query we ask in a path and uh is that is there a path from vertex X to vertex y then we will ask other questions so let us first try and see how we will solve the problem of answering the query on the graph data structure of is there a path from vertex given a Vertex s to a Vertex G in a graph capital G is there a path from S1 to S2 say and we will consider undirected graph so our query is given a graph G = to v e and two vertices s and t in V is there a path from s to T in G for example let us say we have got a graph and we we are considering here only undirected graph so let us say we consider only undirected graphs let the numbers be 1 2 3 4 5 6 7 8 and 9 now this is an undirected graph you can write it out with v is equal to 1 2 up to 9 and E you can list out all the edges now is there suppose I give you 1 s is equal to 1 and T is equal to 4 the answer is yes because there is a path but if I give you s is equal to 2 and T is equal to 8 the answer is no so how do we find out whether there is such a solution to a graph so now we start using our algorithm design techniques to solve this problem and what is the basic idea in our algorithm design techniques the first idea is get a recursive definition to the problem and try and analyze that then try and analyze that recursive definition and after you Analyze That recursive definition try and use the techniques of algorithm design and data structuring to solve the problem and get the final result so let us see how we would solve the problem and how we would decompose it in a recursive fashion suppose we have to start from one a particular vertex a recursive definition of this would look like this when you are at a node say V if V is equal to T then you can terminate because if you have started from V and V is equal to T that is somebody has given you 1 one the answer to 1 One S equal to 1 and tal to one is obvious now if this is not so then what do you say if there is a path from V so V is not so case one is this case 2 V is not equal to T if V is not equal to T then look at the successors of V For example suppose this is V and our goal is this so 1 is not equal to 4 now if there is a path from 1 to 4 then there must be a path from either 2 to 4 or 3 to 4 that is if there is a path from 1 to 4 then and one is not equal to four then there must be a path from any one of the successes of 1 to four and if there is no path from any one of the successes to four then there is no path so the from this idea we get our basic recursive uh definition idea and the concept is search in a Vex V you are trying to search whether you have reached T and you'll start with s you'll call it with search s this is how we will call it I'm not writing out the definition um the data structures and the Declarations because we are now trying to just do the decomposition we are trying to say what is the recursive decomposition what is the basis condition if V = to = to T return 1 that is we have found so now V is not equal to D so this is the base condition we said that we'll have the base condition and the inductive condition that is the recursive conditions that is what we did in our recursive definition if this is not the case then for each Edge v w in G do X is equal to search so we try to search W and see what is the result if x is equal to equal to 1 that is if if there is a path sorry here also T should be there because T is an argument T is an argument so from if V is not equal to T then try to search from The Edge W to T and if you return with X then return with one because if you have found the path from W to T then you'll get it and you continue to do with all the edges and if you come out here that is you have not returned anywhere then obviously you have not found an edge from any of the successors of V neither is V true so you can return return zero so this is the basic recursive definition and here is the decomposition so what have we done what is our algorithm design technique our algorithm design technique as we mentioned before consists of decompos Base condition decomposition and recomposition so what is uh the idea that we have followed here the idea is that either that node from from that node we have got uh uh we have reached our goal or from that node we will try and find out successors and for all the successors we'll see if the successors can reach the goal if the successors can reach the goal then we have found the goal if the successes cannot reach the goal then there is no goal from this node itself so the problem decomposition and recomposition structure would look like this from V T you have got the base condition base condition is V = to equal to T return 1 otherwise decompose if the there are V W1 if these are the edges v w k if there are K edges then you call it recursively on all of them and if any one of them returns one the recomposition what is the recomposition if anyone returns one return one else that is else means what else means that all return zero then return zero so what does this mean this means that either T is the goal or from T any one of the successes you must reach the goal therefore this is the a correct decomposition a proof of this is obvious from the inductive definition so from the inductive definition we can easily prove that this algorithm is correct but once we go to implement this algorithm that is this definition is correct this problem decomposition style is correct but once we go to implement this algorithm we shall see what are the issues that will crop up so let us next try and implement the algorithm to implement the algorithm let us take in an example and let us take back the example that we started previously 1 2 3 4 5 6 7 8 and let us see what our algorithm is is it visible so let us try and work it out on this example and let us say the first query that we give is try to find out whether there is a path from one to one so let the first query be S is equal to 1 T is equal to 1 so this algorithm will be called with search s 1 one search one one so here you'll come to one you'll get this you'll return true so this problem is easily solved suppose I give s is equal to 1 and T is equal to 2 then suppose we have the situation that s is 1 and T is 2 so you'll call it with search 1 2 you'll come here search 1 2 this is not equal to 1 is not equal to two so for each Edge now suppose we start with this Edge then you'll call it here suppose we start with this Edge 2 first and 3 second so let us start here you'll call it here once you call it here you'll come and you'll get you'll call search 22 so that recursion will come in it will call 2 equal to 2 it will return one so once it returns one it will return one back into search one two so this will return one back and the problem will be solved but the if this does not mean the algorithm is perfectly correct because here we if we in search one two for each each Edge now if we did this Edge before this Edge because we'll be doing it in a particular order and suppose I I do it in the order two and then three then suppose the problem which is defined is this let us consider a definition which uh tries to solve this problem search what 1 3 here it will come with search 13 it will come here this is not true for each Edge so it'll first call search one two to search one two it will come here it'll come here once it comes here sorry it will not search one two it will search 2 three because WT W is 2 for the edge 1 2 W is 2 so it will call search 2 3 now once it call search 2 three it will come into this 2 is not equal to three so then again it will call for the edge now two has an edge to one so it'll again call since there is an edge to one because an undirected edge is represented by two directed edges it will call S search t w is 1 and three now see youve ended up in a you've got the same sub problem back and this will again call 2 three this will call 13 and you'll go into an infinite Loop so the problem with this if you notice is the problem possibility of going into an infinite loop I repeat to search 13 you'll start here then you'll come here then from here again you'll go back here then you'll come here and you'll continue in this Loop though so the algorithm will not terminate that is the algorithm will not finish off properly what do we do in such a situation what is the problem that has cropped up we have reached an identical solution and for this identical sub problem the algorithm will continue recurring in order to handle this identical sub problem what do we have to do if you remember our dynamic programming strategy all that we have to do is remember that we have come to this now let us look at this problem if we have already come to a note okay that is we have already visited a note that what does it mean it means that if you come to it again you'll be trying from here you'll be trying to solve the same sub problem again a sub problem that you have solved solved before in the Fibonacci problem it was just repetition of work that is the algorithm did not become incorrect here it is not only mere repetition of work it is repetition in such a way that your algorithm will go into an infinite Loop therefore dynamic programming not only makes it efficient here is an example where it becomes absolutely essential so how do we use dynamic programming here so let us see we will have to remember as we said before done array we'll have to remember that we have done this thing before so here we will call it a visited array we'll maintain an array visited of vertices here we this will be an array of vertices initialize all of them to zero now whenever you come to a note you say it has been visited so let us come here this part is okay for each agent we do before this you say visited V it's a global array is equal to 1 that is it is visited so once you come in you're mentioning that it is visited now for the edge all that you have got to do is mentioned here if if it is not visited only then you will search so if visited W isal to equal to zero only then will you search and do anything that is if it is visited only then will you try and do it if it is not visited you will not do it so by putting in the concept of this visited node we are now able to remember that we have come to this note before and let us see what effect it has on our algorithm let us try and resolve our problem as uh we were trying to solve that is we are trying to solve search 1 3 let us see what our visited array is we have got eight vertices initialize all of them to zero this is our visitor areay now when I come here the first thing that I do is V equal to T no because it is 13 then I make visited V One V is 1 so visited one is made one then for each Edge VW so 1 to two in V do if visited W is equal to zero so is visited 2 equal to Z yes so if visited 2 is equal to zero then I do this part as we were doing so I visit this so I call it recursively search so I call search 2 3 now in 2 three what do I do in 2 three what I do is I come here again I see is V equal to T2 equal to 3 no then I make visited 2 equal to 1 so I make visited 2 equal to 1 next for each Edge VW so one Edge I have to see so so I come here and see this Edge so what is The Edge 2 1 if visited W equal to equal to Z is visited 1 zero no visited one is one so I do not make this call and once I do not make this call why because I have remembered that I have already made this visit since I made this visit I do not make this call and I come out and the next stage is 2 three so I have made this visit so now I check for 2 three is visited 3 equal to Z visited 3 is zero so I call search 33 once I call search 33 and then I come here and I finish I have obtained my goal so using this technique we are able to avoid the problem of a loop so you now see that using the technique of dynamic programming we have been able to make our algorithm correct now let us see how this algorithm works and let us see whether this algorithm is efficient now let us see if I give 14 then it will come here from here it will come here here so now we'll work it out without this algorithm we'll see very quickly whenever I visit a note I Circle it so 14 I visit this then I'll come here I'll visit this then I'll come back here but since I've come here I've already visited it so I'll come back I'll come here I'll visit this from here I'll come here I'll come back because this is visited I'll not do it from here I'll come here this is visited I'll not do it so I will return zero because n nothing will work here so I'll return zero so this returns zero here so this continues this has failed here this has come here gone in and failed this will come here and work this out here it will find V equal to T and find goal so this is how from any node to any node if there is a connectivity this search algorithm will do it correctly now suppose I give you 16 then what would have happened let us do it a different color and start this would be visited first then this would be visited this would say it cannot be done it would come here this would be visited it would go back this would come here so this would return zero this would come here this would come here it would visit this come back return zero so everything would return zero so let us drop the search tree once we drop the search tree here we'll see how search six fails suppose we are given search 6 to search six we'll start searching with one two so one is visited one is visited we'll come here two will be visited from two we'll try to see 1 six but since this is visited we will come out we'll come and see here and we'll see 2 2 36 36 will Mark three visited and then 36 will try 1 six but once it comes here one is visited so it will not do 36 we try 2 six 2 six 2 is also visited so it will not do this so this one this one will return zero so here zero X is still zero nothing happens to X this will return zero because if you notice that if no Edge it becomes one it returns zero so this will come to here one will come back and try 1 3 sorry two it'll two will continue two has tried one two has tried two two will continue and try two and try 4 six 4 six 4 six on the other hand we'll try 2 six and fail and it has got no other edges so this will fail and return zero once this returns zero this two will return zero once two returns zero one will try 36 but again three so here four had become visited again three is visited so since three is visited this will fail and therefore this will return zero so if there is see you will see that we are visiting only those nodes which are connected and we are not visiting any other node and also we are visiting a node which is every Edge is visited only once so we will see that how this technique of using dynamic programming has helped us to solve the problem of graph connectivity this type of search using a recursive style using the dynamic programming of making it visited is called a depth for search of a graph and of an undirected graph in in a directed graph also you'll have depth for search in an undirected graph you have this concept of depth first search and this depth first search as we shall see in the next class is efficient and also is useful in solving a large number of problems so we shall see that in the next class