## DSA Tutorial

DSA HOME DSA Intro DSA Simple Algorithm

## Arrays

DSA Arrays DSA Bubble Sort DSA Selection Sort DSA Insertion Sort DSA Quick Sort DSA Counting Sort DSA Radix Sort DSA Merge Sort DSA Linear Search DSA Binary Search

## Stacks & Queues

DSA Stacks DSA Queues

## Hash Tables

DSA Hash Tables DSA Hash Sets DSA Hash Maps

## Trees

DSA Trees DSA Binary Trees DSA Pre-order Traversal DSA In-order Traversal DSA Post-order Traversal DSA Array Implementation DSA Binary Search Trees DSA AVL Trees

## Graphs

DSA Graphs Graphs Implementation DSA Graphs Traversal DSA Cycle Detection

## Shortest Path

DSA Shortest Path DSA Dijkstra's DSA Bellman-Ford

## Minimum Spanning Tree

Minimum Spanning Tree DSA Prim's DSA Kruskal's

## Maximum Flow

DSA Maximum Flow DSA Ford-Fulkerson DSA Edmonds-Karp

## Time Complexity

Introduction Bubble Sort Selection Sort Insertion Sort Quick Sort Counting Sort Radix Sort Merge Sort Linear Search Binary Search

## DSA Reference

DSA Euclidean Algorithm DSA Huffman Coding DSA The Traveling Salesman DSA 0/1 Knapsack DSA Memoization DSA Tabulation DSA Dynamic Programming DSA Greedy Algorithms

## DSA Examples

DSA Examples DSA Exercises DSA Quiz DSA Certificate

# DSA Graphs Traversal

## Graphs Traversal

To traverse a Graph means to start in one vertex, and go along the edges to visit other vertices until all vertices, or as many as possible, have been visited.

Result:

Understanding how a Graph can be traversed is important for understanding how algorithms that run on Graphs work.

The two most common ways a Graph can be traversed are:

• Depth First Search (DFS)

DFS is usually implemented using a Stack or by the use of recursion (which utilizes the call stack), while BFS is usually implemented using a Queue.

The Call Stack keeps functions running in the correct order.

If for example FunctionA calls FunctionB, FunctionB is placed on top of the call stack and starts running. Once FunctionB is finished, it is removed from the stack, and then FunctionA resumes its work.

## Depth First Search Traversal

Depth First Search is said to go "deep" because it visits a vertex, then an adjacent vertex, and then that vertex' adjacent vertex, and so on, and in this way the distance from the starting vertex increases for each recursive iteration.

How it works:

1. Start DFS traversal on a vertex.
2. Do a recursive DFS traversal on each of the adjacent vertices as long as they are not already visited.

Run the animation below to see how Depth First Search (DFS) traversal runs on a specific Graph, starting in vertex D (it is the same as the previous animation).

Result:

The DFS traversal starts in vertex D, marks vertex D as visited. Then, for every new vertex visited, the traversal method is called recursively on all adjacent vertices that have not been visited yet. So when vertex A is visited in the animation above, vertex C or vertex E (depending on the implementation) is the next vertex where the traversal continues.

### Example

Python:

``````class Graph:
def __init__(self, size):
self.adj_matrix = [[0] * size for _ in range(size)]
self.size = size
self.vertex_data = [''] * size

if 0 <= u < self.size and 0 <= v < self.size:

if 0 <= vertex < self.size:
self.vertex_data[vertex] = data

def print_graph(self):
print(' '.join(map(str, row)))
print("\nVertex Data:")
for vertex, data in enumerate(self.vertex_data):
print(f"Vertex {vertex}: {data}")

def dfs_util(self, v, visited):
visited[v] = True
print(self.vertex_data[v], end=' ')

for i in range(self.size):
if self.adj_matrix[v][i] == 1 and not visited[i]:
self.dfs_util(i, visited)

def dfs(self, start_vertex_data):
visited = [False] * self.size
start_vertex = self.vertex_data.index(start_vertex_data)
self.dfs_util(start_vertex, visited)

g = Graph(7)

g.add_edge(3, 0)  # D - A
g.add_edge(0, 2)  # A - C
g.add_edge(0, 3)  # A - D
g.add_edge(0, 4)  # A - E
g.add_edge(4, 2)  # E - C
g.add_edge(2, 5)  # C - F
g.add_edge(2, 1)  # C - B
g.add_edge(2, 6)  # C - G
g.add_edge(1, 5)  # B - F

g.print_graph()

print("\nDepth First Search starting from vertex D:")
g.dfs('D')
``````
Run Example »

Line 60: The DFS traversal starts when the `dfs()` method is called.

Line 33: The `visited` array is first set to `false` for all vertices, because no vertices are visited yet at this point.

Line 35: The `visited` array is sent as an argument to the `dfs_util()` method. When the `visited` array is sent as an argument like this, it is actually just a reference to the `visited` array that is sent to the `dfs_util()` method, and not the actual array with the values inside. So there is always just one `visited` array in our program, and the `dfs_util()` method can make changes to it as nodes are visited (line 25).

Line 28-30: For the current vertex `v`, all adjacent nodes are called recursively if they are not already visited.

Breadth First Search visits all adjacent vertices of a vertex before visiting neighboring vertices to the adjacent vertices. This means that vertices with the same distance from the starting vertex are visited before vertices further away from the starting vertex are visited.

How it works:

1. Put the starting vertex into the queue.
2. For each vertex taken from the queue, visit the vertex, then put all unvisited adjacent vertices into the queue.
3. Continue as long as there are vertices in the queue.

Run the animation below to see how Breadth First Search (BFS) traversal runs on a specific Graph, starting in vertex D.

Result:

As you can see in the animation above, BFS traversal visits vertices the same distance from the starting vertex, before visiting vertices further away. So for example, after visiting vertex A, vertex E and C are visited before visiting B, F and G because those vertices are further away.

Breadth First Search traversal works this way by putting all adjacent vertices in a queue (if they are not already visited), and then using the queue to visit the next vertex.

This code example for Breadth First Search traversal is the same as for the Depth First Search code example above, except for the `bfs()` method:

### Example

Python:

``````def bfs(self, start_vertex_data):
queue = [self.vertex_data.index(start_vertex_data)]
visited = [False] * self.size
visited[queue[0]] = True

while queue:
current_vertex = queue.pop(0)
print(self.vertex_data[current_vertex], end=' ')

for i in range(self.size):
if self.adj_matrix[current_vertex][i] == 1 and not visited[i]:
queue.append(i)
visited[i] = True``````
Run Example »

Line 2-4: The `bfs()` method starts by creating a queue with the start vertex inside, creating a `visited` array, and setting the start vertex as visited.

Line 6-13: The BFS traversal works by taking a vertex from the queue, printing it, and adding adjacent vertices to the queue if they are not visited yet, and then continue to take vertices from the queue in this way. The traversal finishes when the last element in the queue has no unvisited adjacent vertices.

## DFS and BFS Traversal of a Directed Graph

Depth first and breadth first traversals can actually be implemented to work on directed Graphs (instead of undirected) with just very few changes.

Run the animation below to see how a directed Graph can be traversed using DFS or BFS.

Result:

To go from traversing a directed Graph instead of an undirected Graph, we just need to remove the last line in the `add_edge()` method:

``````def add_edge(self, u, v):
if 0 <= u < self.size and 0 <= v < self.size:
``````

We must also take care when we build our Graph because the edges are now directed.

The code example below contains both BFS and DFS traversal of the directed Graph from the animation above:

### Example

Python:

``````class Graph:
def __init__(self, size):
self.adj_matrix = [[0] * size for _ in range(size)]
self.size = size
self.vertex_data = [''] * size

if 0 <= u < self.size and 0 <= v < self.size:

if 0 <= vertex < self.size:
self.vertex_data[vertex] = data

def print_graph(self):
print(' '.join(map(str, row)))
print("\nVertex Data:")
for vertex, data in enumerate(self.vertex_data):
print(f"Vertex {vertex}: {data}")

def dfs_util(self, v, visited):
visited[v] = True
print(self.vertex_data[v], end=' ')

for i in range(self.size):
if self.adj_matrix[v][i] == 1 and not visited[i]:
self.dfs_util(i, visited)

def dfs(self, start_vertex_data):
visited = [False] * self.size

start_vertex = self.vertex_data.index(start_vertex_data)
self.dfs_util(start_vertex, visited)

def bfs(self, start_vertex_data):
queue = [self.vertex_data.index(start_vertex_data)]
visited = [False] * self.size
visited[queue[0]] = True

while queue:
current_vertex = queue.pop(0)
print(self.vertex_data[current_vertex], end=' ')

for i in range(self.size):
if self.adj_matrix[current_vertex][i] == 1 and not visited[i]:
queue.append(i)
visited[i] = True

g = Graph(7)

g.add_edge(3, 0)  # D -> A
g.add_edge(3, 4)  # D -> E
g.add_edge(4, 0)  # E -> A
g.add_edge(0, 2)  # A -> C
g.add_edge(2, 5)  # C -> F
g.add_edge(2, 6)  # C -> G
g.add_edge(5, 1)  # F -> B
g.add_edge(1, 2)  # B -> C

g.print_graph()

print("\nDepth First Search starting from vertex D:")
g.dfs('D')

print("\n\nBreadth First Search starting from vertex D:")
g.bfs('D')
``````
Run Example »

Now that we have looked at two basic algorithms for how to traverse Graphs, we will use the next pages to see how other algorithms can run on the Graph data structure.

×

## Contact Sales

If you want to use W3Schools services as an educational institution, team or enterprise, send us an e-mail:
sales@w3schools.com