[Coding test] 1. Graph Undirected and Directed traversal for cycle detection

context

To detect cycle
There are 2 types of graphs - directed (with arrows) and undirected (no specific direction). There is specific way to traverse for each graph

directed graph

If there are directions you can either

1) use recursive dfs (more complex)

https://velog.io/@whitehousechef/Detecting-cycle-in-graph-via-DFS

2) use topological sort (simpler by putting nodes with 0 indegree to queue)

https://velog.io/@whitehousechef/Topological-sort

undirected graph

1) There is 2 very impt assumptions to detect cycle
1.1) edges = n - 1
1.2) graph nodes are all connected

https://velog.io/@whitehousechef/Leetcode-Graph-Valid-Tree

2) besides those assumptions, u can also use Union Find to detect cycle in undirected graphs
https://velog.io/@whitehousechef/Union-Find-deadly-mistake