Graphic Theory(2

Depth-First and Breadth-First Traversal Algorithms
There are two techniques that we will examine that accomplish this traversal. In depth-first, our traversal will go as far as possible down a path before considering another, and in breadth-first, our traversal will go evenly in many directions.

Depth-First Traversal
In depth-first traversal, we visit the starting node and then proceed to follow links through the graph until we reach a dead end.
In an undirected graph, a node is a dead end if all of the nodes adjacent to it have already been visited.
In a directed graph, if a node has no outgoing edges, we also have a dead end. When we reach a dead end, we back up along our path until we find an unvisited adjacent node and then continue in that new direction.
Consider the following graph.



Using the depth-first traversal we visit nodes in this order 1, 2, 3, 4, 7, 5, 6 , 8 and 9. We then continue to back up until we reach the starting node, and because all nodes adjacent to it have been visited, we are done.




The recursive algorithm for depth-first traversal is




Breadth-First Traversal
In a breadth-first traversal, we visit the starting node and then on the first pass visit all of the nodes directly connected to it. In the second pass, we visit nodes that are two edges “away” from the starting node. With each new pass, we visit nodes that are one more edge away.
Because we will visit that node for the first time along the shortest path from the starting node, we will not need to consider it again. We will, therefore, either need to keep a list of the nodes we have visited .
Consider again the graph above , If we begin our traversal at node 1, we will visit
First pass : nodes 2 and 8 .
Second pass: nodes 3 and 7.
Third pass: nodes 4 and 5.
Last pass: nodes 6 and 9.
Where the depth-first traversal depended on a stack, our breadth-first traversal is based on a queue. The algorithm for breadth-first traversal is:



This algorithm will add the root of the breadth-first traversal tree to the
queue but then immediately remove it




Exercises3
1. For the following graphs, give the order that the nodes will be first
visited when doing a breadth-first traversal starting at the node
labeled with a 1.
2-For the graphs in question 1, give the order that the nodes will be
first visited when doing a depth-first traversal starting at the node
labeled with a 1.
3.Write a detailed algorithm for depth-first traversal using an
adjacency matrix that just prints the node label as the visit operation.
4.Write a detailed algorithm for breadth-first traversal using an
adjacency matrix that just prints the node label as the visit operation.
5.Write a detailed algorithm for depth-first traversal using an
adjacency list that just prints the node label as the visit operation.
6.Write a detailed algorithm for breadth-first traversal using an
adjacency list that just prints the node label as the visit operation.