37. Graphs-3 (cycle undir)

Problems on BFS/ DFS (...continued)

• cycle detection undirected✅
• bipartite graph✅ (deeply checking vis array)

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

1. Cycle detection in undirected graphs-

we will start from a node and traverse using adjacency list in 2 direction simultaneously, if we meet at some point then we can say we got a cycle

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

METHOD-1 : using BFS                 (time-N+2E        space-N)

1. insert start node into queue as {node, -1} being {curr, prev} & mark it as visited

2. pop out a node from queue and insert its unvisited non-prev neighbors into the queue marking them visited

4. if u encounter a neighbor node, which is already visited & !=prev node, so we conclude there is a cycle in the graph

for a graph with many components- diby

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

METHOD-2: using DFS                 (time-N+2E+N       space-N)⭐⭐

if it is visited and not prev then, we say a cycle is present and

we return only if its true, else keep on going into depth

if not a parent ==> if vis => cycle
                               if unvis => take it for further traversal

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

2.Bipartite graphs-

A graph is bipartite if the nodes can be partitioned into two independent sets A and B such that every edge in the graph connects a node in set A and a node in set B.

OR

color a graph with 2 colors such that no 2 adjacent nodes have same color

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

here we check already visited wale ko kya value assign hui thi pehle

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

we can color a graph with alternate colors if-

1. either it is linear graph

2. or, it has even length cycles

instead of counting len(cycle), we'll check if we can color graph with alternate colors...

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

1. pop out from queue

2. check its adjacent nodes

3. if adjacent node is already colored check if it is alternately colored of curr node

4. if adjacent node is not colored, then color it with alternate color & push it into queue

5. when u encounter an adjacent node which is already colored but wrongly then return false

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

METHOD-1 : using BFS

1. instead of visited array we will take color array
2. assign a color to q.front node and start iterating on the queue
3. every time assign alternate color

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

METHOD-2: using DFS

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