# Breadth First Traversal and Depth First Traversal for Graph

## Data Structures and Algorithms Note

## Breadth First Traversal

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 representation

class 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 diagram`

g = 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:

1

2

3

4

5

6

## another way to think

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[1], 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[2], 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.

## Depth First Traversal

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 representation

class 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 diagram`

g = 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:

1

2

4

5

6

3

## another way to think

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[1], go to its linked vertex, vertex2, take g[2], go to its linked vertex, vertex4, for the g[4], 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[1] 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.