|
Graph traversal is the method of visiting all the nodes in a connected graph.
Depth-first Search (DFS)
Depth-first Search is an algorithm for visiting every node in a connected graph once. It travels by a path and go as far as possible. When the path reaches an end point, it will return to the last branch it meet and go through that branch.
Algorithm
- Mark the root node as current node.
- Mark current node as visited
- For each neighbor node of the current node,
If it is not visited before, mark this node as current node and repeat process from step 2
|
Time Complexity
It have to visited every node and edges once, so time complexity is O (| V | + | E |)
SpaceComplexity
It will need to go forward alll nodes in the worst case, so the space complexity is O (| V |)
Pseudo Code
Function DFS (Graph, Node)
Mark Node as visited
For each neighbor n of N do
If n is not visited then
Mark n as visited
DFS (Graph, n)
|
Breadth-first Search (BFS)
Breadth-first Search is an algorithm for visiting every node in a connected graph. It travels the graph by the order of the distance from the root node.
Algorithm
- Enqueue the root node into a Queue
- Dequeue the first node from the Queue and mark it as visited.
- For each connected node of top node, check is it visited. If no, enqueue it into the Queue
- If the Queue is not empty, repeat the process from step 2, else, the algorithm is finish
It will be a DFS when change the Queue to Stack |
Time Complexity
It have to visited every node and edges once, so time complexity is O (| V | + | E |)
SpaceComplexity
It will need to save all nodes into the stack in the worst case, so the space complexity is O (| V |)
Pseudo Code
Function BFS (Graph, RootNode)
Create a Queue Q
Enqueue RootNode into Q
Mark RootNode as visited
Do
Get the first node from Q as N
Dequeue out the top node from Q
For each neighbor n of N do
If n is not visited then
Mark n as visited
Push n into S
While Q is not empty
|
|