7.1 Traversal

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 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 ```
 © The University of Hong Kong Algorithms Library - hkual@cs.hku.hk