virat9358/graph

Graph

  Steps by Knight     Application:Shortest Path in matrix   Rotten Oranges   Minimum cost path
  Use bfs approach by making all possiblities frst
  dp intiliaze -1, if we moved to that mark it as 0
  
  Biconnected graph: If we remove 1 vertices it can't disconnected
  Transitive closure of a graph
  frst track the all the destinations that particular node reaches(visited array)
  after that update adjacency list getting visited array
  
  Find whether path exist                                  Application: Find number of island
  after finding source or destination, go dfs approach (make sure all edge case implemented like) 
  i < 0 || i >= size || j < 0 || j >= size || grid[i][j] == 0 return false;
  
  **Detect cycle in a directed graph**                             **Detect cycle in a undirected graph**
  keep track and mark visited, if we visited again then                  Same as Directed, but no need to track bfsvisited
  use dfsvisited(imagine recursive calls diagram) for
  checking whether we meet this node for not                             just need to track of parent node for detecting	
  for particular traversal and update it
  
  Dijkstra Algorithm     Network Delay time Bellman ford:Negative weight cycle
                               Dijkstra's algo application                                                    make a distance vector and update it for all nodes
                               Intiallize all the signal to INT_MAX, and start with given node as 0,          except starting node, and check again for detecting
                               Use bfs approach and updated all nodes signal
                               
  Critical connections in a network
  we use dfs approach for finding frst_time
  after end of graph, such that its visited all nodes then we updated the min_time using backtracking
  for detecting bridges min_time[node] = min(min_time[node], min_time[child])
  for detecting edges first_time[node] < min_time[child] then push it
   
  

NOTE

  Find town Judge(Indeg and Outdeg Concept)
  Word boggle problem    Find string in the grid
   first search for given word, and next go on
   mark what is visited v[i][j] != word[k] this condition
  

Theory

  Topological Sorting: It should be DAG, there will be many possibilites find indeg choose which is least
  So for implementation use DFS + stack   Topological sort **Application:** Alien dictionary       Prerequisites tasks   Course schedule
                                         We are getting indeg and relationship from the given strings
                                         and used bfs approach for finding topological sort
  
  Bipartite graph: It need to be split into 2 independent sets like 2 coloring
  so 0 for not colored    Bipartite graph
  	1 for blue
  	-1 for red
  	check for valid color using dfs
  Eulerian Path
  	  number of vertices with an odd edges is > 2 then no path
  	  if it has even, then we start from any nodes (odd_vertices == 0)
  	  if it has 2, then we start from any 2 vertices (odd_vertices == 2)
  	  there will be no case where exactly one vertex has odd number of edges
  	  
  A Spanning Tree of a connected graph is a subgraph that contains all of that graph’s                Minimum spanning tree
     vertices and is a single tree. with E' = |V| - 1. It can't be disconnected                        we need to neglect highest weight from the graph so, we visited already that node, 
   MST is having minimum weight among all ST. A complete undirected graph can have n^(n-2) ST's        then no need to include it, add all lowest weights by using priority queue(min heap)
  From completed graph by removing max(e-n+1)edges, we can construct a ST                              and mark all the nodes that visited
   
  Strongly Connected graphIf every vertices can reach all other vertices then it is SCC. Every single node is SCC. If we reverse edge direction
  in Directed graph, the property doesn't change. 
  In dfs approach make a visulization of passing and marking nodes for better
  

Approaches

  When source and destination given use bfs, by using question condition
  when we want to search all possibilites use dfs