# Breadth First Traversal and Depth First Traversal for Graph

## Data Structures and Algorithms Note

The breadth first traversal will go through all vertices level by level. From [level 0] vertex 1 -> [level 1] vertex2, vertex3 -> [level 2] vertex 4, vertex 5 and finally [level 3] vertex6

We could use a queue to implement breadth first traversal, start from vertex1, then we append vertex1’s connected vertices into the queue, then pop the first vertex as well as append its connected vertex into the queue, keep the action till all the vertices are visited.

`from collections import defaultdict # This Graph class using adjacency list representationclass Graph:    def __init__(self):        # default dictionary to store graph        self.graph = defaultdict(list)     # function to add an edge to graph    def add_edge(self,u,v):        self.graph[u].append(v)     # Function to print a BFS of graph    def BFS(self, v):         # Mark all the vertices as not visited        visited = set()         # Create a queue for BFS        queue = []         # Mark the start node as        # visited and enqueue it        queue.append(v)        visited.add(v)         while queue:             # Dequeue a vertex from            # queue and print it            v= queue.pop(0)            print(v)             # Get all adjacent vertices of the dequeued vertex v.            # If a adjacent has not been visited,            # then mark it visited and enqueue it            for i in self.graph[v]:                if i not in visited:                    queue.append(i)                    visited.add(i)`

Time Complexity: O(V+E)
where V is the number of vertices and E is the number of edges in the graph.

result

`# Create a graph given in the above diagramg = Graph()g.add_edge(1, 2)g.add_edge(1, 3)g.add_edge(2, 4)g.add_edge(2, 5)g.add_edge(3, 5)g.add_edge(4, 5)g.add_edge(4, 6)g.add_edge(5, 6) print ("Following is Breadth First Traversal starting from vertex1:")g.BFS(1)-----------------------------------------Following is Breadth First Traversal starting from vertex1:123456`

according to the step of add_edge above, we could get the g will look like:

1->2->3
2->4->5
3->5
4->5->6
5->6

for the breadth first traversal that starts from vertex1, we take the g, append the rest of linked vertices to queue, which is vertex2 and vertex3, then pop current queue that we will get vetex2, take the g, append the rest of linked vertex4 and vertex5 into the queue, and so on. So that we get the result as 1 2 3 4 5 6.

The depth first traversal will go forward to the depth until there is no further vertex to go, then trackback to the previous vertex check if there any other vertex still not be visited. Keep doing the same action until all the vertices are visited. From vertex 1 -> vertex2 -> vertex4 -> vertex5 -> vertex6, and there is no further vertex, so go back to the previous vertex, stop at vertex1 and go to the last vertex, vertex3.

`from collections import defaultdict # This Graph class using adjacency list representationclass Graph:    def __init__(self):        # default dictionary to store graph        self.graph = defaultdict(list)     # function to add an edge to graph    def add_edge(self,u,v):        self.graph[u].append(v)     def DFSUtil(self, v, visited):        # Mark the current node as visited and print it        visited.add(v)        print(v)         # recur for all the vertices adjacent to this vertex        for i in self.graph[v]:            if i not in visited:                self.DFSUtil(i, visited)     def DFS(self, v):        # create a set to store all visited vertices        visited = set()        # call the recursive helper function to print DFS traversal        self.DFSUtil(v, visited)`

Time complexity: O(V + E)
where V is the number of vertices and E is the number of edges in the graph.

Space Complexity: O(V)
since an extra visited array of size V is required.

result

`# Create a graph given in the above diagramg = Graph()g.add_edge(1, 2)g.add_edge(1, 3)g.add_edge(2, 4)g.add_edge(2, 5)g.add_edge(3, 5)g.add_edge(4, 5)g.add_edge(4, 6)g.add_edge(5, 6) print ("Following is Breadth First Traversal starting from vertex1:")g.DFS(1)>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>Following is Breadth First Traversal starting from vertex1:124563`

according to the step of add_edge above, we could get the g will look like:

1->2->3
2->4->5
3->5
4->5->6
5->6

for the depth first traversal that starts from vertex1, we take the g, go to its linked vertex, vertex2, take g, go to its linked vertex, vertex4, for the g, go to the vertex5, for [g5] go to the vertex6, and it is the end, the deepest vertex of the graph, trace back to the previous vertex and find is there any vertex not been visited, we will find all the vertices are visited except the g vertex3, so we print 3 as the last one we visited. That is why we get the result as 1 2 4 5 6 3.

--

--