38. Graphs-4 (cycle directed)

Topics-

1. Cycle detection in directed graph (DFS)✅
2. safe states                                     (DFS)⭐✅
3. Topo sort                                      (DFS+stack)✅
------------------------------------------------------------------
4. Kahn's algo                                  (Topo /BFS)✅
5. Cycle detection in directed graph (topo)✅
6. Course schedule -1 , 2                 (topo)✅
7. Alien dictionary                           (topo)⭐✅
8. safe states                                    (BFS)⭐✅
---------------------------------------------------------------------------------------------------------------

1. Detect a cycle in a directed graph-(DFS)

the undirected algo won't work here, since in undir we say a cycle is present if from another path we encounter a visited node

however, in dir graph we say a cycle is present if we encounter a vis node on the same path we are traversing in dfs

so, here we will use 2 visited arrays




RETURN TRUE AS SOON AS YOU GET A CYCLE

1. select non vis node to be starting node for dfs

2. mark vis=1 & pathvis=1 , for this node

3. Now, visit adj nodes of this node and if they have :

  • (vis=0),      then call dfs for them 
  • (vis=1 & path vis = 0) , then don't do dfs , there ain't any cycle.
  • (vis=1 & path vis = 1), then we got a cycle => return true

4. if  in a dfs call, the curr node has no further adjacent nodes 

  • then return false, and set pathvis=0 for this node
-----------------------------------------------------
----------------------------------------------------------------------------------------------------------------------------

2. Eventual safe state-(DFS)

 terminal node -  outdegree = 0
 safe node -         every path from it leads to terminal node

a node is a safe node, if every path from its adj nodes are ending at terminal node

(a node which is either part of a cycle, or leads to a cycle) != safe node
  1. cycle not detected => safe node => mark pathvis=0 => return false
  2. cycle detected =>  not a safe node => return true
  3. A node is safe if all its adj nodes returns to be safe (do not return true) after dfs calls
  4. Jaise hi cycle detect hoye fatafat true return krdo 
------------------------------------------------------------
we can also do it without safe check vector, as at last only those are the safe nodes whose pathvis=0

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

2. Topo sort -(DFS+stack)

only for DAG 
there can be multiple topo sort orders, we are printing any 1

------------------------------------------------------------
intuition-
last tak jao dfs kro aur jab adj nodes naa bache toh stack mein daaldo
--------------------------------------------------------
Algo- 
(ek node ke saare adj nodes ko visit krke ab us node ko stack m daaldo)

1. take a (vis=0) node and make a dfs call for it & mark it (vis=1)
2. make dfs call for only (vis=0) adj nodes of it
3. if a node can't make any further dfs calls => push it into the stack 
4. repeat from step 1
5. stack contains topo sort starting from last in element.
-------------------------------------------------------------
--------------------------------------------------------------------------------------------------------------------------

3. Topo sort: (BFS + Kahn's algo)

only for DAG

we will use modified BFS using indegree array instead of visited & a queue

NOTE- there will be at least 1 node with indegree 0

1. make indegree array
2. insert all nodes into queue with indegree = 0
-------
3. insert q.front into ans
4. reduce indegree of each adj nodes by 1 & insert into queue only those whose indegree=0|
------
REPEAT TILL QUEUE IS filled
----------------------------------------------------------------------------------------------------------------
-----------------------------------------------------------------------------------------------------------------------------

4. Cycle detection in dir graph: (BFS)

we will use Kahn's algo and try to find topo sort
if length of topo sort != no. of nodes , then it means topo sort is not applicable here, which means it is not a DAG so it means it has a cycle

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

5. Course schedule- 1,2

course schedule-1: 
topo sort hi hai , bas direction (a => b) ki jagah (b ==> a) hai, toh bas indegree array ke construction mein indeg[edges[i][0]]++ hoga instead of [i][1]

course schedule-2:
1. either, we can detect cycle by DFS and if it has cycle then we can't do topo and hence ans is {}
2. or, we can check by BFS if topo exists and then tell order if topo is possible
-----------------------------------------------------------------------------------------------------------------------------

6. Safe Nodes (by BFS)

terminal nodes are always safe nodes
terminal nodes have outdegree = 0

so we will do opposite of topo sort means we will see outdegrees for nodes of given graph
or, we will reverse edges direction of whole graph and see for nodes with indegree = 0

yellow edges are reversed of original

1. reverse the graph
2. do topo sort on new graph


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

7. Alien Dictionary🔥🔥

Read proper ques on GFG

we have to tell if, for given set of words, an order of alphabets is possible or not ?
OR, if topo sort is possible or not ? 
OR, DAG or not ?

e.g., ( wrt, wtf  )== > ( r-->t  &  t-->f )

soln: make directed edges and then do topo sort

1. the first non-matching character in 2 words gives us a directed edge with 2 nodes in the graph

so we want order of first k alphabets from og alphabets in alien language
so we would number them from 0 to k-1 (that is instead of making nodes of character we would deal with numbers and at last in storing answer convert those ascii values back to characters)

here size of adj list is K


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

Comments

Post a Comment

Popular posts from this blog

18. greedy algorithm

Image
assign greedily  like sabse kam distribute kro starting mein bade number last k liye bacha k rakho we use 2 pointer here ---------------------------------------------------------------------------------------------------------------------------- if smj ni aara ki konsa stl use kru, u can even solve ques with few varibles also. ----------------------------------------------------------------------------------------------------------------------------- Shortest Job First Problem Jump game 1 Jump game 2 Job Sequencing problem N Meetings in a room Insert Intervals Min platforms Valid parenthesis Candy Fractional Knapsack ------------------------------------------------------------------------------------------------------------------------ Shortest Job First Problem- --------------------------------------------------------------------------------------------------------------------------- JUMP GAME-1 --------------------------------------------------------------------------------------...
Read more

19. strings (LB)

Image
strings are 1d character array. e.g., char ch[10]; cin>>ch; string ends with '\0' cin with string works only if till space, tab or new line is absent in input... ----------------------------------------------------------------------------------------------------------------------------- ----------------------------------------------------------------------------------------------------------------------------- ----------------------------------------------------------------------------------------------------------------------------- ----------------------------------------------------------------------------------------------------------------------------- ----------------------------------------------------------------------------------------------------------------------------- STRING- dynamic size no null termination in built functions --------------------------------------------------- ------------------------------------------------------------------------- --------...
Read more

17. BINARY SEARCH on 2d arrrays

Image
 1.)   ROW WITH MAX 1s- given each row is sorted. BRUTE - simple 2 loops OPTIMAL - binary search lagalo to find index of 1st occurence of 1 in a row -------------------------------------------------------------------------------------------------------------- 2.) Search in 2d Matrix-(sorted rows consecutive) BRUTE - use 2 loops BETTER - check for only that row jisme target is between a[i][0] and a[i][c-1]  OPTIMAL - 2d array ko hypothetically 1d me karke binary search lagalo --------------------------------------------------------------------------------------------------------------- 3.) Search in matrix(sorted row and col but not consecutive) BETTER- use binary search for every row OPTIMAL -(time: N+M) --------------------------------------------------------------------------------------------------------------- 4.) Peak elements in matrix- BRUTE- 1.) we can do linear search and for each element compare with its 4 neighbours 2.) Or, we can find max element in matrix BET...
Read more