LAB-10

Question 1

Connected Components CCs

Answer 1

ilands

Question 2

Use flag visited and CC number

Question 3

DFS backtracks but BFS don’t backtrack

Question 4

Cycle Check - starts and ends at the same

Blue - explored
Orange - Visted
While - unvisited

Question 5

In traversal . go in ascending order

Question 6

Find what is topological sort?
can’t be done for undirected..

Question 7

If you come across blue again in traversal then there is a cycle

Question 8

Mark BLUE when you visit first. Mark as Orange when backtrack and no more paths.

Question 9

zero in-degree. no incoming. Number of incoming are called in-degree

Question 10

Explore Kahns method -> Topological sort (u should be smaller than v)

Question 11

kahn’s algorithm for toposort

Question 12

Kahn, delete edge and of no more incoming then duque that and enque next one onto queue

Question 13

Use Graph for state modelling. Vertex is stage and edge is state transition. So, we can find any cyclic

Question 14

In transport if price is different from A to B then it is directed as each direction has different price. If price is same then undirected

Question 15

debrief