Graph Traversal Flashcards
1
Q
DFS, BFS
A
O(V+E)
2
Q
PRE
A
ROOT, LEFT, RIGHT
3
Q
IN
A
LEFT, ROOT, RIGHT
4
Q
POST
A
LEFT, RIGHT, ROOT
5
Q
DFS and BFS always runs O(v^2) on
A
Complete Graph
6
Q
Check Tree or Not
A
- At least one node without income
- Number of edges exactly be n-1
7
Q
Topological order
A
- Shouldn’t have cycles
8
Q
Colors
A
Blue - visited,
Orange - back tracked or end
8
Q
If black edge and next node is visited then cycle
A
First all edges are black, mark as orange after traversal
9
Q
order
A
BFS - level order
DFS - pre order traversal
10
Q
Visit and explore
A
visit the node and explore of each child node
11
Q
DFS and BFS can run in O(V^2)
A
DAG, Bipartite Graph, Complete Graph
12
Q
Topological
A
Graph should be DAG
https://www.youtube.com/watch?v=cIBFEhD77b4
https://www.youtube.com/watch?v=dis_c84ejhQ
13
Q
A graph can have many topological sort orders
A
yes
14
Q
A
