38. Graphs-4 (cycle directed)

# Detect cycle in directed graph: (DFS)

the undirected graph algorithm won't work here, because we assumed that reaching a visited non parent node means we can return back, but so is not the case in directed graph.

in directed graph, we say a cycle is present, if we reach a visited node which is already present in the visited path of current node
----------------------------------------------
if  in a dfs call, the curr node has no further adjacent nodes 
then return false, and set pathvis=0 for this node
This happens when we backtrack 

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

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

# Topo sort-I (using DFS)

- only for DAG (directed graphs with no cycles)

- linear ordering of nodes such that if there is an edge b/w u & v, then u appears before v
- there can be multiple topo sort orders
- used to solve dependency problems

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

Intuition-

last tak jao dfs kro aur jab adj nodes naa bache toh stack mein daaldo

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

Algo-  current node ke saare adj nodes ko visit krke ab us node ko stack m daaldo

At the end, stack contains topo sorted nodes from top to bottom

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

# Topo sort-II (using Kahn's algo)

- In a DAG, there will be at least 1 node with indegree = 0

--------------
Approach-  Kahn's algo (BFS based)
repeatedly remove nodes that have indegree = 0

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

# Cycle detection in dir graph: (BFS)

we will use Kahn's algo and try to find topo sort

if (length of topo sort != N)  =>  topo sort is not applicable => not a DAG => cycle present

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

1. Course schedule-I,II

1.

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

------

2.

either, detect cycle by DFS & if it has cycle => can't do topo => hence ans is {}

or, check by BFS if topo exists & then tell order if topo is possible

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

2.1 Eventual safe state-⭐
(by DFS)

- terminal node: ( outdegree = 0 )

- safe node = every path from its adj nodes ends at a terminal node

- a node which is either part of a cycle, or leads to a cycle != safe node

- a node is unsafe if DFS from it enters a cycle

- a node is safe if all DFS paths from it avoids cycle

- thus we perform cycle detection in directed graph using dfs code with some modifications

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

2.2 Eventual Safe States-
(by reverse topo)

Approach-
since, terminal nodes (outdegreee = 0) are always safe nodes

since, topo sort naturally excludes cyclic paths

so, do opposite of topo sort => see outdegree for nodes of given graph

or, reverse edge direction of whole graph & see for nodes with indegree = 0 ✅

Hence, we reverse the graph to make terminal nodes as the nodes with indegree 0, and then apply topo sort to find non cyclic indegree 0 nodes order in reversed graph
Sort the topo sorted array before returning ans

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

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

3. Alien Dictionary🔥

Read proper ques on GFG

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

Find, if for given set of words, an order of alphabets is possible or not ?

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

OR, if topo sort is possible or not ? 

OR, DAG or not ?

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

Approach:

- create directed graph & do topo sort. If topo is possible (size = no. of nodes) then valid

- The first non-matching character in 2 words gives a directed edge b/w 2 nodes 

- We want order of only k alphabets (present in alien language) from original alphabets. So instead of making nodes of character, we would deal with numbers & at the end convert the ascii values back to characters.

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