43. Graphs-7 : Extra Algos⭐

# Note-

1. SCC:
- only for directed graphs
- strongly connected component ( component in which for every pair of nodes u,v we can go from u to v as well as from v to u )
- In a graph having SCCs, we can traverse bidirectionally within a SCC & unidirectionally b/w SCCs. But, when we reverse the graph, then we can traverse only within a SCC not b/w adjacent ones
 
----------
2. Kosaraju and Tarjan Algo are used to find SCCs
3. Applications include finding deadlocks, clusters, echo chambers, dependency cycle, etc.
------------------------------
4. Bridges:
- only for undirected graphs
- they are edges which if removed disconnects the graph.
5. Articulation points: They are node which if removed (along with all its edges) disconnects the graph.
6. Applications include network resilience analysis, thus finding critical node and edge.

7. If discovery time(node B) < disc(A) => B is ancestor of node A
8. disc[curr node] = disc[last visited node] +1
9. disc: discovery time (time when we reached first to this node)
10. low of a node: lowest discovery time amongst all possible reachable nodes from current node, hence we update low of a node
----------------------------------------------------------------------------------------------------------------------------

1. Kosaraju's Algorithm-

Approach- time: O(V+E)

1. store node in a stack as per topo sort 
2. create a new reversed graph 
3. do dfs on new graph , as per stack nodes
- stores SCCS in a 2d vector, which stores each SCC during final dfs
- no. of SCCs = no. of dfs nodes in stack for which we did a dfs call
-------------------------

----------------------------------------------------------------------------------------------------------------------------

2. Tarjan's Algorithm-⭐

Used to find:
- bridges (or, non cyclic edges) in a graph
- articulation points
- SCCs
------------------------
# Approach- Modified DFS using discovery time concept

- we need 2 additional arrays in DFS: discovery time[], lowest discovery time[]

- bridge exists between two components only if, discovery time of u < all the discovery times on the right side as shown in image above.
- bridge condition: disc[parent] < low[child] ⭐

- when current node finds a visited non parent neighbour, low of current node is updated: 
    low[node] = min( low[node], disc[visited non parent neighbour] )⭐

- when we backtrack to a parent node, then we update low of parent node:
   low[parent node] = min( low[parent node] , low[child node] )
--------------------------------------------------------------
# Algo: 
1. for each node set disc time and low to default values as u go deeper using DFS
2. do dfs till u reach a node from which u can't move further (node has a visited adj non parent node)
3. update low of this node & backtrack to parent node
4. check if this edge is a bridge, by comparing disc of parent with low of child node
5. repeat from step 3
----------------------------------------------------------------------------------------------------------------------------

3. Articulation point- (cut vertex)


same as Tarjan Algo with 3 changes-
1. add root node condition
2. count children
3. change < to <= in the AP check condition

-----------------------------------------------------------------------------------------------------------------------------

Comments

Post a Comment

Popular posts from this blog

30.) DP on subsequences

Image
Subset sum = target✅⭐ Partition equal subset sum✅ Partition array into 2 subsets with min abs [sum(v1)-sum(v2) ]✅ Count subsets with sum k✅⭐ Count partitions with given diff✅ target sum✅ 0/1 knapsack✅⭐ min coins✅---->count min coins to be taken coin change-2--->count n(ways) of taking coins⭐✅ unbounded knapsack✅ rod cutting problem✅ ----------------------------------------------------------------------------------------------------------------------------- 2 ways to generate all subsequences- Power Set, or Recursion subset means subsequence in dsa ----------------------------------------------------------------------------------------------------------------------------- 1. Target Sum- QUES- return true if there exists a subset with sum equal to the target in the array... Soln assuming all array elements are positive  here f(n-1,target) will tell if there's a subsequence till n-1 index with sum = target 1.) RECURSIVE SOLN-        ( time: 2^n    ...
Read more

36. Graphs-2 (traversal problems)

Image
1. No. of provinces Count total components in a graph, using any traversal technique ----------------------------------------------------------------------------------------------------------------------------- 2. Rotten oranges⭐     Multi source BFS time: O(n*m)   space: O(n*m) -------------- - count all fresh at start and then count if these many will rot in the process or not - here we do not need a visited matrix since we can modify given - we update time each time there rots atleast one orange in a BFS cycle --------------------------------------------------------------------------------------------------------------------------- 3. No. of Islands Count no. of islands (land surrounded by water in 4 directions) ---------------------------------------------------- time: O(n^2)  space: O(n^2) No. of islands = no. of graph components ----------------------------------------------------------------------------------------------------------------------------- 4. ...
Read more

35. Graphs-1 (basics)

Image
# Note -  1. it has nodes/vertices (N) connected by edges (E) 2. d egree(N)  = n(edges) connected to a node 3. in-degree(N) = no. of in-going edges  4. out-degree(N) = no. of out-going edges  5.  Total degree of undirected graph = (2*E) 6.  DAG - directed acyclic graph 7.  Path -  a sequence of nodes where all  adj nodes have a direct edge b/w them -------------------------------------------------------------------------------------------------------------------------- 1. Representation- 1. Adjacency Matrix:  space: O(n^2) store info about presence of edges between 2 nodes -------------------------------------------------------- 2. Adjacency list:   space: O(n) - store info about adjacent neighbours of a node - for unweighted graph instead of a pair we will store them as integer array ----------------------------------------------------------------------------------------------------------------------------- 2. BFS- time: O(N+...
Read more