Graph New – 1

InterviewBit

  1. Graph Basic. GFG
  2. DFSGFG Code
    In DFS, we start from a vertex, we first print it and then recursively call DFS for its adjacent vertices.  We need to take care of the scenario where the graph is not connected.
    Iterative Depth First Traversal of GraphGFG. The logic here is to use a Stack.
    Start with the source node. Check if the current vertex has already been visited. If not print it and then push it adjacent vertex to stack. Before pushing also check if it’s already visited. This visited has to be performed twice.


  3. BFS – Code –
    The idea is same a BFS for a tree. The code implementation is same of Iterative Depth First Traversal of Graph using Stack, its just that we use queue here except that everything is same(take a simple example and check). We need to take care of the scenario where the graph is not connected.


  4. Topological Sort –  Code  GFG– Topological sorting for Directed Acyclic Graph (DAG) is a linear ordering of vertices such that for every directed edge uv, vertex u comes before v in the ordering. Topological Sorting for a graph is not possible if the graph is not a DAG.
    The first vertex in topological sorting is always a vertex with in-degree as 0 (a vertex with no in-coming edges).
    It is similar to DFS. In DFS, we start from a vertex, we first print it and then recursively call DFS for its adjacent vertices. In topological sorting, we use a stack. We don’t print the vertex immediately, we first recursively call topological sorting for all its adjacent vertices, then push it to a stack. Finally, print contents of stack.
    A vertex is pushed to stack only when all of its adjacent vertices (and their adjacent vertices and so on) are already in stack.
    Topological sort represents a linear representation of the graph.
    Node that appears after in a topological sort have no path from them to any node appearing before them in the topological sort.


  5. Dijkstra’s shortest path algorithm  shortest paths from source to all vertices in the given graph with no negative cycle but doesn’t works with negative weight In Short Full Video GFG Code. Works for both directed and undirected graph.
    Algo: It’s a greedy algorithm.
    1) Create a set sptSet (shortest path tree set) that keeps track of vertices included in shortest path tree, i.e., whose minimum distance from source is calculated and finalized. Initially, this set is empty.
    2) Assign a distance value to all vertices in the input graph. Initialize all distance values as INFINITE. Assign distance value as 0 for the source vertex so that it is picked first.
    3) While sptSet doesn’t include all vertices
    ….a) Pick a vertex u which is not there in sptSetand has minimum distance value.
    ….b) Include u to sptSet.
    ….c) Update distance value of all adjacent vertices of u. To update the distance values, iterate through all adjacent vertices. For every adjacent vertex v, if sum of distance value of u (from source) and weight of edge u-v, is less than the distance value of v, then update the distance value of v.
    The solution uses a Adjacency matrix. Time Complexity of the implementation is O(V^2). If the input graph is represented using adjacency list, it can be reduced to O(E log V) with the help of binary heap.
    We start with the source node. Then see all it’s neighbours. Update the minimum
    Note:
    1) The code calculates shortest distance, but doesn’t calculate the path information. We can create a parent array, update the parent array when distance is updated (like prim’s implementation) and use it show the shortest path from source to different vertices. The parent array will keep a mapping of which node introduced that minimum distance.
    2) The code finds shortest distances from source to all vertices. If we are interested only in shortest distance from source to a single target, we can break the for loop when the picked minimum distance vertex is equal to target. (See code)
    3) Dijkstra’s algorithm doesn’t work for graphs with negative weight edges. For graphs with negative weight edges, Bellman–Ford algorithm can be used. SO (In Dijkstra’s algorithm, once a vertex is marked as “closed” (and out of the open set) – the algorithm found the shortest path to it, and will never have to develop this node again – it assumes the path developed to this path is the shortest.)
    Complexity for code above – min distance O(V) and the inner loop below O(V), so 2.O(V) which makes it still O(V). Combined with outer loop you get O(V^2)


  6. Floyd Warshall Algorithm – All Pairs Shortest Path in a given graph – works with positive or negative edge weights but with no negative cycles. GFG
    Time Complexity: O(V^3) Code  Video
    Works for both directed and undirected graph with a small change SO
    k – via node, i – source, j – dest
    Also check the way to find the minimum path.


  7. Bellman Ford Algorithm – shortest paths from source to all vertices in the given graph with no negative cycle but works with negative weightYouTube GFG Code In 5 Minutes Works for both directed and undirected graph.
    Algo:It’s NOT a greedy algorithm.
    We only need to traverse the entire edge (relax all edges) V-1 times. Why ?
    We need the shortest path, so if there was a cycle we could find the minimum weight path in that cycle and remove the cycle.
    We need to start with the source edge and examine all the outgoing node. Then we start with the next edge and examine all it’s outgoing edge. In the code below and here on Mission-Peace also the graph has been arranged such that this is achieved by default when we loop through the edges. 
    The general idea to to traverse the edges and keep updating the minimum distance of the nodes from source.
    Note that in each iteration the dist of any vertex may be updated (unlike Dijkstra’s where once a vertex has been finalzied we don’t update it again). We need to make V-1 iterations over the E edges.  In each iteration we update the dist.
    For each node, we check to see the distance of the destination node of the edge can be reduced. If yes we update it. We can also a parent array to keep a check, as to which node introduced the other node. At the end we need to check if a negative weight cycle exists. 

    A negative weight cycle is a cycle with weights that sum to a negative number.
    The Bellman-Ford algorithm propagates correct distance estimates to all nodes in a graph in V-1 steps, unless there is a negative weight cycle. If there is a negative weight cycle, you can go on relaxing its nodes indefinitely. Therefore, the ability to relax an edge after V-1 steps is a test for the presence of a negative weight cycle. So the Bellman-Ford algorithm tests for negative weight cycles.

    1) Negative weights are found in various applications of graphs. For example, instead of paying cost for a path, we may get some advantage if we follow the path.

    2) Bellman-Ford works better (better than Dijksra’s) for distributed systems. Unlike Dijksra’s where we need to find minimum value of all vertices, in Bellman-Ford, edges are considered one by one.
    3) We iterate V-1 times, because from source to distance there can be maximum v-1 edges, else there exists a negative cycle in which case can find the distance.
    4) Time complexity of Bellman-Ford is O(VE) 


  8. Disjoint Set – Union, Find and Merge – Youtube, Code –  This concept is used for Kruskal and finding cycle in graph. Note the path compression code hereScreen Shot 2017-12-24 at 12.56.38 PM.png

  9. Minimum Spanning Tree: 
    A minimum spanning tree (MST) or minimum weight spanning tree is a subset of the edges of a connected, edge-weighted undirected graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight. That is, it is a spanning tree whose sum of edge weights is as small as possible. More generally, any undirected graph (not necessarily connected) has a minimum spanning forest, which is a union of the minimum spanning trees for its connected components.
    A minimum spanning tree has (V – 1) edges where V is the number of vertices in the given graph.
    In Prim’s algorithm, the next edge in the MST shall be the cheapest edge in the current vertex. In Kruskal’s algorithm, we shall choose the cheapest edge, but it may not be in the current vertex.
    Prim’s algorithm is found to run faster in dense graphs with more number of edges than vertices, whereas Kruskal’s algorithm is found to run faster in sparse graphs.
    Use Prim’s algorithm when you have a graph with lots of edges.
    For a graph with V vertices E edges, Kruskal’s algorithm runs in O(E log V) time and Prim’s algorithm can run in O(E + V log V) amortized time, if you use a Fibonacci Heap.

    Kruskal MSTCode Basic Video– This uses the concept of disjoint set and path compression. We have a weighted undirected graph.
    – Create an array of edges(this is specific to our graph implementation here).
    – We sort the edge in the ascending order of there weight.
    – We create disjoint set for all the vertex.
    – We know there will be V-1 edges in the MST.  So start looping.
    – Now we pick the edge with minimum weight.
    – Each edge has it’s src and des and weight.
    – We find the parent of the src and desc vertex using disjoint set logic. In our implementation we do path compression in findSubest()
    – If both there parent are different then we join these vertex and do a union of these 2 vertex in disjoint set and save the edge.
    – If there parents are same, we if we combine these they will form a cycle. (consider any example. If two vertex have the same parent, then they are already joined at the parent. If we join these two directly they will form a cycle).
    The code above we keep vertex value as 0,1,2,3 so that we can easily access them in array directly.
    Prim MST – Basic Flow Video TR Video, Code, GFG 


  10. Cycle in Undirected Graph Algorithm – Video (Both Type) MP-Code (Both Type)
    1. Using DisJoint Set –  GFG
    – Create an array of edge where each edge has src and dest.
    – Create an array of disjointSet for each vertex where each subset has parent(rank not needed for our use case).
    – Now start traversing each edge.
    – Each edge has two vertex  check for the parent of these vertex.
    – If there parent are not same, do a union.
    – If parent are same it means that these vertex have already been joined previously. So obviously there’s some other path to reach these edge. So cycle is present.
    The code looks a lot like Kruskal.
    2. Using DFS  –  GFG DFS Code  – The code here is same as DFS except the parent node that we need to pass and compare against.
    – Start with DFS keeping track of the visited set. When we start we also pass the parent node from which it was called. If it wasn’t called from by anyone just pass -1.
    – Add the vertex to visited set. Then start processing it’s children if isin’t visited yet. If it’s visited check if the parent vertex. If yes then it means we are trying to follow the path from where we came. Skip it. If the visited vertex is not the current’t vertex then it means this vertex has already been visited and thus cycle exists.
     This is because that node has two path from where it can be reached – one was from the parent which we didn’t go along. Still we reached there, it means that it can be reached from at-least one from node.


  11. Detect Cycle in Directed Graph Algorithm – Video Code GFG
    Algo:
      – We maintain 3 set – white, gray, black.
    white –  needs to be processed
    gray   –   being processed
    black –  have been processed(all the children are traversed).
    – Add all vertex to white set and start processing.
    – When we start with a vertex, move it from white to gray set.
    – Then do a DFS for that set.
    – Check if any child of the current vertex is in black set – skip that vertex(already processed).
    – If any child vertex is in gray set, then it means that a parent of the current set is already being processed in the gray set, and we are again trying to reprocess it. This implies that a cycle is present.
    – If none is true, do a DFS on the current vertex. If no cycle found move the vertex from gray to black.
    – Then start processing a new vertex from white set.
    In the current GFG solution since we use the vertex element as array index, we don’t really need to make three set, we can just use a single array and set it’s index value to the colour they represent else we would have maintained three HashSet for each of the type.


  12.  Find a Mother Vertex in a Graph  Code GFG
    Algo: When we do a DFS the last finishing node may be the mother node. We do a DFS and keep track of the last finishing node. This may or may not be the mother vertex(Imagine a disconnected graph. We need to handle such cases as well). Now do a DFS at this vertex. Now check if all the nodes have been visited by DFS from that vertex. If yes, then that’s a mother vertex else not.


  13. Transitive Closure of a Graph using DFS – Given a directed graph, find out if a vertex v is reachable from another vertex u for all vertex pairs (u, v) in the given graph.
    Code GFG
    Algo: This can be achieved using DFS. We create an array(it’s not adjacent matrix) for all the path.
    Transitive Closure of a Graph will help us decide if a path exists or not. We do a DFS here. The difference here is that, we always pass the parent/source node to indicate from where this DFS iteration started. Keep updating that in the result matrix.
    –  Create a matrix tc[V][V] that would finally have transitive closure of given graph. Initialize all entries of tc[][] as 0.
    – Call DFS for every node of graph to mark reachable vertices in tc[][]. In recursive calls to DFS, we don’t call DFS for an adjacent vertex if it is already marked as reachable in tc[][].


  14. Iterative Deepening Search(IDS) or Iterative Deepening Depth First Search(IDDFS) – Wiki Video GFG
    Algo: Simple DFS/BFS are not very cost effective for searching in a graph. BFS requires a lot of memory while DFS keeps traversing for a single vertex depth wise till it’s exhausted. So instead of going till the end we try to set a maximum level for searching. So we start with level = 0, and check if our target value is at level = 0, if found cool else we need to check the next level. We again start from level 0 and the move to level 1. If target is found good, else we move to the next level. Again we start from level 0, then 1, then 2. So we can see the when we start searching for a new level we start from the very beginning every time. But this is fine as the maximum number of vertex are at the bottom and not at the bottom.


  15.  It is given that the directed edges don’t form cycle. How to assign directions to undirected edges so that the graph (with all directed edges) remains acyclic even after the assignment?
    Algo: Do a topological sort. For every undirected edge (u, v), assign it direction from u to v if u comes before v in topological sorting, else assign it direction from v to u.
    Topological sort represents a linear representation of the graph. Node that appears after in a topological sort have no path from them to any node appearing before them in the topological sort. So if we connect all the undirected edge in the forward direction (maintaining the topological sort order) the graph will remain acyclic.


  16. Given a list of tickets, find itinerary in order using the given list. GFG
    Using Topological Sort – Code
    We create a graph for the given cities and then sort them.  This can also be solved using hashing.


  17. A DAG is given to us, we need to find maximum number of edges that can be added to this DAG, after which new graph still remain a DAG that means the reformed graph should have maximal number of edges, adding even single edge will create a cycle in graph. GFG
    Algo: Topological Sort.  Node that appears after in a topological sort have no path from them to any node appearing before them in the topological sort.


  18. *** Print all paths from a given source to a destination GFG Code
    Algo: Think about the path printing from root to leaf node in a BT. There we would pass the entire ArrayList. But here we don’t want to do that. So we maintain an array in which we keep track of the last index of inserted element. Plus as we know we need to take care of not to run into the loop. But as seen in the example on GFG, we can’t simply maintain a visited array as it will prevent us from moving onto another new path.
    So we need to take of two cases here – first not to run into a loop at the same time explore different paths. Plus keep storing all the vertex value in a single array and not generate a new array in each recursion.


  19. Connected Components in a UnDirected GraphGFG
    Algo: Since the graph is undirected, a simple DFS/BFS can generate all the pairs.Time complexity of above solution is O(V + E) as it does simple DFS for given graph.


  20. Given n friends and their friendship relations, find the total number of groups that exist. And the number of ways of new groups that can be formed consisting of people from every existing group. GFG
    Algo: It’s a problem about finding the connected components in a undirected graph. If we find the total number of connected components in a undirected graph, then all it’s permutation will give the total number of groups that can be formed.


  21. A disconnected Graph with N vertices and K edges is given. The task is to find the count of singleton sub-graphs. A singleton graph is one with only single vertex. GFG
    Algo:  The idea is simple for graph given as adjacency list representation. We traverse the list and find the indices(representing a node) with no elements in list, i.e. no connected components.


  22. Check if removing a given edge disconnects a graph. GFG
    Algo: Count the number of connected components. Remove the given edge. Count the connected components. Initial connected component and the new count will be different if a bridge was created.


  23. Find all reachable nodes from every node present in a given set. GFG – The idea is to use Connected Component concept. All the nodes in connected component will have the same  set of visitable nodes. So we need to identify each component and for any node in that the visitable nodes will be same. We don’t need to re-generate the visitable node for nodes, that already exists in that connected component.
    We will do a BFS for all the reachable nodes. The BFS method will return all the connected node. Store them are display. Check the code for clarity.


  24. Shortest Path in Directed Acyclic Graph. GFG Code
    Algo: Topological Sort. If there’s no cycle and we sort the graph. Nodes that appear after the source in linear ordering generated using topological sort can’t be reached. for other node after the source, we need to find the shortest path.
    Initially we create a dist array, where we store the initial distance of all nodes as INF except the source node which is set as 0. Then we stack poping the nodes from stack in the sorted order. For nodes, which don’t have distance as INF we need to check to see if we can update it’s distance.
    Now for the node poped we get all it’s adjacent nodes (iterator). We node the current distance of the adjacent node from the source node. We will try to minimize that like in all shortest path algo. Code. It’s like the minimum distance to reach the source-node(current node we are checking) + the weight to the node to it’s neighbour node. If the current weight is larger than  this we update the node value.


  25. Count all possible walks from a source to a destination with exactly k edges.  GFG Good Article and Code
    Algo: We use BFS here. While pushing the value, we also push the depth. When the depth reaches the specified value, we stop pushing after that as it won’t gave a solution and also prevents if there’s a loop.


  26. Check if a given graph is tree or not. GFG
    Algo: For a graph to be a tree, if should not have a cycle and should not be disconnected. We use the code to find cycle in an undirected graph(code). This will mark all the nodes visited and also detect if there exists a cycle. If not cycle found, see if all the vertex have been visited. If yes, then it’s a tree else not.
  27. Flood-fill Algorithm – This is simply saying traversing the entire matrix like a graph using DFS or BFS. Like the island problem or boggle. There’s are a few simple condition that we need to check.  Screen Shot 2017-12-05 at 8.27.11 PM
    Use of flood algorithm is found in solving a maze. Given a matrix, a source cell, a destination cell, some cells which cannot be visited, and some valid moves, check if the destination cell can be reached from the source cell. Link
    –  Find the number of islands in a 2D matrix represented by an array of 0 and 1 (Using DFS) Code GFG
  28. [Pending] Boggle. GFG
  29. [Pending] Snake and Ladder Problem. GFG
  30. [Pending] Longest Path in a Directed Acyclic Graph. GFG
  31. [Pending] Bridges in a GraphTR Video GFG
    Algo:


  32. [Pending] Connected Component in a Directed Graph – Kosaraju’s Algorithm – Check if a graph is strongly connected –  GFG  Using BFS

 

Advertisements

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s