Graphs

GRAPH  Modelling -

• Multi-Source BFS --> Use normal BFS but insert all the sources in queue and make their distance = 0 --> Update the distance for others as usual for normal BFS (Link)
  
  
• Transform existing Graph and use BFS (non-weighted) & Dijkstra (weighted)
• Hot (red) - Cold (blue) problem => Update graph s.t. red & blue are alternate 
• make 2*n nodes as A => A' and A''
• connect A' -> B'' (for hot) and A'' -> B' (for cold)
• Directed - weighted G + can remove k edges
• make G => k+1 times as A', A'', A''', .....
• Add edge of weight 0 in between the k+1 graphs
  
  
  

• n city + m roads + max storage (c litre) => weighted road (consume w litre) + cost[i] (cost per litre to refuel at i-th point) => min. cost from s to t
  
  We have to move from A to B  capacity = 3.
  From A -> A' -- 1 litre needed at value in cost array.
  From A''' -> B' because loss of 2 litres (as shown in the below diagram) at edge weight of 0 litres.
  
  As destination is B => any of B, B', B'', B''' is sufficient => use hospital trick => connect all B, B', B'', B''' to a new node

NOTES -

• In tree -> never a cycle => only parent is enough to stop repetition
  But for graph -> need visited array to avoid repetition
  
  
• Don't check for parent in directed graph bcz 0->1 and 1->0 is cycle but print NO (if check node != parent) as 0 is parent of 1
• But check in undirected graph bcz 2 nodes can never make cycle => at least 3
  
  
• To detect cycles in directed graph
• BFS - Check if graph is DAG using queue and kahn's algo => if Yes -> NO cycle
• DFS (2 methods)
• If node is present in recursion stack => cycle present
• Use concept of colour --> mark vis = 0 if not visited, 1 if visited but not analysed and 2 if fully analyzed (If colour = 1 -> present in recursion stack)
  
  
• To detect cycles in undirected graph
• BFS (2 methods)
• See Accepted solution --> Idea - mark vis = 1 (if fully analysed) and if found vis=1 again => cycle exist
  
• Graph is 0<->1 and 1<->2 and 2<->0
  -> first insert 0 => vis[0]=1 -> insert 1 and 2 (bcz neighbour of 0)
  -> vis[1]=1 -> insert 2 again bcz vis[2]≠1 and neighbour of 1
  (NOTE - 2 is inserted 2 times => once through 0 and then from 1)
  -> vis[2] = 1-> now no insertion bcz all neighbours are now visited
  -> now, second 2 is here -> since vis[2] = 1 -> cycle present
• NOTE - here parent array is not needed
  
  
• Preferred - Use queue and parent to check if visited=1 & parent != node
• Here, mark vis = 1 jaise hi found for first time
• DFS - Use parent to check for cycle
• To print a cycle => use DFS 
  
  
• 0-1 BFS ==> djikstera mai use priority queue to sort weights --> but here only 2 weights --> can use normal dequeue to sort -> Time = O(E) bcz no log(V) factor
  
• If edge weight is 0 -> insert at front, if edge weight is 1 -> insert at back
  
  
• Shortest distance in O(V+E)   ---> BEST
• any graph with unit weight ---> use BFS
• weighted DAG (Directed Acyclic Graph) ---> use topological sort
  
  
• Topological Sort - if there is edge from a to b, then a appears before b in that order
• ONLY valid for DAG (directed acyclic graph)
• Why not undirected graph ?
• bcz edge from a to b => a is before b and edge from b to a => b appears before a => NOT possible simultaneously
• If cycle is present => 1->2->3->1 => 1 appears before 3 & 3 appears before 1
• NOT possible simultaneously
  
  
• Using DFS - Watch for intuition
• put only those who are fully analysed in ans bcz now we are sure that nothing will come after it --> At last, reverse ans
  
  
• Using BFS (Kahn's Algorithm)- find indegree --> If it is 0 => push in queue and subtract 1 from all its neighbour --> Do until every node visited
  
  
• 

    All path from src to dest
    if cycle is present =>    aainfinite paths -> like 20213,      2020213   and so on ...

• 
  Strongly connected component - maximal connected component such that there exists a path from 
  
   $u$ x to y <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>v</mi></math>$v$ and a path from   $v$y to x for all x and y inside the component $u$
• Every SCC are disjoint and covers all vertices of graph

**************************************************************************

*    All below shortest path algorithms are valid for directed graph                                        *
*    --> can also work for undirected bcz a—b is same as (a->b and a<-b) edge                   *
**************************************************************************

• Djikstera - graph with positive weights
• Find lengths of shortest paths from starting vertex to all other vertices.
• Also called single-source shortest path problem.
• 
  Initialize min_dist[src]= 0 & others = ∞
• Why only positive weights work ? 
• Dijkstra’s algorithm assumes that
  once a node is marked visited
  => distance is fixed & never change
  However, if negative weight
  -> distance can decrease in future
  
  
  
• O(V² + E) --> do n iterations, in each find the unvisited vertex with min. distance from src (say v) --> mark v visited -> go to neighbour's of v -> update distance if found min. distance wrt v from current distance
• Why n iterations ? --> bcz in each iteration, we find new v => at max n vertices
• If distance[v] = infinity --> break bcz graph is disconnected & src can't reach any more vertices bcz min. of remaining is infinity
  
  
• OPTIMIZED - Above algo may work for dense graph, where E ≈ V²
• But for sparse graph where E <<< V --> gives TLE bcz V = 2e5 types
• Use priority queue (min heap) to find min. unvisited v in log(n) time 
• 1st element is weight bcz sorted wrt edge weight
• No need to use visited here --> bcz we used it earlier to find min. unvisited node --> but now, both are being taken care by priority queue
• whenever found visited --> pop it 
• push only if found new shorter route wrt source
• Update parent only if found shorter route --> use parent to print path
  
  
• If use array or normal queue --> O(V² + E)
• If use priority queue or set --> O((V + E ) * logV)
• pop minimum element => rebuild heap at max n times --> V*log(V) 
  push new better distance inside edge part --> E*log(V) 
  
  
• Benefit of set - erase any value (not just top)
  Can watch for - Better clarity 
• Why to erase -> bcz say node 4 gets distance changed from ∞ to 10 --> now again after some time --> update distance from 10 to 7 --> insert {7, 4}in priority queue but {10, 4} was already there --> unnecessary iteration for {10, 4}
• set can reduce this as whenever we insert {7, 4} --> we erase any other value present
• if (min_dist[curr] != pq.top().weight) --> continue;
• bcz this means that current's min_dist (10) ≠ actual min_distance (7)
• If not done --> complexity can increase up to O(V*E) --> TLE
  
  
• NOTE - Set has greater constant factor wrt priority queue (FACT)
• priority queue uses --> if (dist[curr] != pq.top().weight) --> continue;
• This increase factor from log(V) to log(E) = log(V²) = 2*log(V)
• In practice, priority queue is little bit faster than set

• Bellman Ford - find min. distance from source to all vertex with + or - edge weight
• Iterate (n-1) times => bcz every time at least 1 node is getting min. distance
  NOTE - source node ka min. distance = 0 --> phle se pta hai => ONLY (n-1) left
• Edges can be in any order
• Mathematical proof
  
• Perform n iterations => if distance of any node decrease => negative cycle exists
  bcz exactly after n-1 iterations => We must get shortest distance
• Time Complexity - O(V*E)
  
  
• Floyd Warshall - find min. distance from any vertex to any vertex with + or - edge
• Use adjacency matrix to store result 
• val[i][i] = 0 for all i
  val[i][j] = x where x is weight from node i to node j
  
  
• More of a brute force approach but still IDEA is —> shortest path between i to j will have some k intermediate nodes => treat each and every vertex from 1 to N as an intermediate node one by one
  
  
• Now, iterate i from 1 to n => update all shorter distance via vertex i
  eg. - if i = 2 --> for val[a][b] = min(val[a][b], val[a][2] + val[2][b]) 
  
  
• At the end, if any of val[i][i] < 0 => negative cycle exists
• Time Complexity - O(V^3)
• If E ≈ V and all edge weights are +ve => apply djikestra from each node
• Time Complexity = O(V*E*log(V))

Minimum Spanning Tree - Spanning tree is a tree (connected + NO cycle) made from given graph and MST is Spanning tree with minimum possible sum

• Prim's Algorithm - find MST for graph with + or - edge weight
• Starting node is like root of final MST => we can construct same tree with any node as root (bcz connected) --> any vertex can be chosen as starting node
• make parent array, visited array, min heap of {weight, node}
• parent can be used to construct MST
• make vis = 1 only if added into MST means fully analysed its neighbour
• At each step => select min edge-weight that connects vertex in MST to vertex outside MST and adds it to MST --> issiliye analyse only for not visited bcz they are not part of MST but added to min heap via vertex which is in MST --> if (vis[i] = = 1) ---> continue;
• Why this greedy works ?
• bcz at the end every vertex has only 1 edge attached to other (bcz tree)
  --> since total sum has to be minimum => select the minimum of all edge weight connected from that vertex
• Time Complexity = O((V +E) * log V)  --> same reason as djikstera
  
  
• Kruskal's Algorithm - sort {weight, x, y} wrt edge weight then do union of x and y ONLY if par[x] != par[y] ---> check parent and do union using DSU
• Time Complexity - O(E * logE + E)
• Sorting of edges - O(E * logE)
• iterate through all edges and apply DSU which takes O(1) => Total - O(E)

Disjoint set data structure - checks if 2 set are disjoint or not in nearly constant time

• Initialize par[i] = i --> every node is single and disjoint
• rank[i] = 0 or size[i] = 1 ---> BOTH union by rank or union by size take same time
• size is size of component
• rank is similar to height but not exactly height - Watch Video
  
• parent array stores ultimate parent (root node of component)
• 
  
  Find parent function - using path compression whenever we backtrack
  => update ultimate parent (par[i]=i) of every node on the path 
  Eg. - here we were asked to find(7)
  => when backtracking from 7 to 1 --> update parent of 2, 3, 5, 7 as 1

• Union by rank - attach smaller rank to larger bcz if bde height wale ko chhote ke niche lgaya => total height ↑ + jyada nodes aur niche chle gye => unke parent find krne mai jyada time lgega (NOTE - rank is similar to height)
• If same rank => kissi ko khi bhi lga do and make rank++ jisko parent bnaye ho
  
  
• Union by size - attach smaller size to larger size (Same reason as above) => increase size of larger bcz ab total size of component increase by chhote ka size
• If same size => kissi ko khi bhi lga do