Dr.

Mohammed Hussein
Analysis of Algorithms

Graph Traversals
Breadth and Depth First
Search
DR. MOHAMMED AL-HUBAISHI

1
 2

► Introduction to Graph Traversals

► Breadth First Search
► Depth First Search
► Comparing BFS and DFS
► Applications of Graph Traversals
► Conclusion

Dr. Mohammed Hussein

 3
Introduction to Graph Traversals

Graph traversal refers to the process of visiting all the

vertices in a graph. It is an essential operation in graph
theory and has numerous applications in computer science.
► The two most common graph traversal algorithms are
Breadth First Search (BFS) and Depth First Search (DFS).
These algorithms differ in their approach to traversing the
graph and have different use cases.

Dr. Mohammed Hussein

 4
Remember: Graphs

► graph: A data structure containing:

► a set of vertices V, (sometimes called nodes)
► a set of edges E, where an edge
represents a connection between 2 vertices.
► Graph G = (V, E)
► an edge is a pair (v, w) where v, w are in V

a b
► the graph at right:
► V = {a, b, c, d}
► E = {(a, c), (b, c), (b, d), (c, d)} c d

► degree: number of edges touching a given vertex.

► at right: a=1, b=2, c=3, d=2
 5
Graph examples

► For each, what are the vertices and what are the edges?
► Paths through a network
► Web pages with links
► Methods in a program that call each other
► Road maps (e.g., Google maps)
► Airline routes
► Facebook friends
► Family trees
 6
Example family tree represented as a graph:

In this family tree, Tommy is the root node and has two children nodes:
Alice and Bob. Bob, in turn, has three children nodes: Carol, Dave, and
Eve.
a traversal of the family tree using depth-first search:
1. 1. Start at the root node, Tommy.
2. 2. Visit Tommy's first child, Alice.
3. 3. Since Alice has no children, backtrack to Tommy and then visit
Tommy's second child, Bob.
4. 4. Visit Bob's first child, Carol.
5. 5. Since Carol has no children, backtrack to Bob and then visit
Bob's second child, Dave.
6. 6. Since Dave has no children, backtrack to Bob and then visit
Bob's third child, Eve.
7. 7. Since Eve has no children, backtrack to Bob and then
backtrack to Tommy.
8. 8. Since Tommy has no other children, the traversal is complete.

Dr. Mohammed Hussein

 Web pages with links in graph 7
traversal: some examples

1. Wikipedia: Wikipedia is a prime example of a webpage with links in graph traversal.

Each page on Wikipedia has multiple internal links to other pages on the site, allowing
users to traverse the network of pages and explore related topics.
2. BuzzFeed: BuzzFeed is another website with links in graph traversal. The site's
homepage includes links to different categories of content, such as news, quizzes,
and videos, which lead users down different paths of content discovery.
3. Amazon: Amazon is a popular e-commerce site that uses links in graph traversal to
help users navigate its vast product catalog. Users can browse through categories
and subcategories of products, narrowing down their search until they find the
specific item they're looking for.
4. Reddit: Reddit is a social news and discussion site that also utilizes links in graph
traversal. Users can navigate through various subreddits, each with its own community
and set of topics, or follow links to related threads within a single subreddit.
5. Yelp: Yelp is a site that helps users find and review local businesses. Its interface
includes links to different categories of businesses, such as restaurants, bars, and
shopping, allowing users to explore different types of businesses in their area.
Dr. Mohammed Hussein
 8
Facebook friendship graph

One example of traversing a Facebook friendship graph would be to start at a

particular user's node (e.g. their Facebook profile), and then explore all of their
immediate friends (i.e. the nodes directly connected to their node).
From there, you could continue to traverse the graph by exploring the friends of those
immediate friends, and so on, until you have visited all of the nodes in the graph that
are within a certain number of degrees of separation from the original user.
This type of traversal could be useful in a variety of scenarios, such as:
- Finding mutual friends between two users
- Exploring potential business connections or job opportunities through shared
network connections
- Analyzing the structure and density of social networks to identify influencers and key
players.
Note that this type of traversal must be done in accordance with Facebook's terms of
service and any privacy restrictions that are in place for individual users or groups.

Dr. Mohammed Hussein

 9
Breadth First Search

► Breadth First Search is a graph traversal algorithm that starts at

the root node and explores all the neighboring nodes before
moving on to the next level of nodes. This means that BFS visits
all the nodes at the same level before moving on to the next
level.
► BFS is particularly useful for finding the shortest path between
two nodes in an unweighted graph. It can also be used to find
all the nodes that are reachable from a given node.

Dr. Mohammed Hussein

 10
Breadth-first search

breadth-first search (BFS): Finds a path between two nodes by taking one
step down all paths and then immediately backtracking.
► Often implemented by maintaining a queue of vertices to visit.

1. visiting a vertex (select the node).

2. the exploration of vertex (visit its neighbors).

► BFS always returns the shortest path (the one with the fewest edges) between the start and the end
vertices.
► to b: {a, b}
► to c: {a, e, f, c} a b c
► to d: {a, d}
► to e: {a, e} d e f
► to f: {a, e, f}
► to g: {a, d, g} g h
► to h: {a, d, h}
 11
Algorithm of Breadth-First Search:

• Step 1: Consider the graph you want to navigate.

• Step 2: Select any vertex in your graph (say v1), from which you want to traverse the
graph.
• Step 3: Utilize the following two data structures for traversing the graph.
• Visited array(size of the graph)
• Queue data structure
• Step 4: Add the starting vertex to the visited array, and afterward, you add v1’s
adjacent vertices to the queue data structure.
• Step 5: Now using the FIFO concept, remove the first element from the queue, put it
into the visited array, and then add the adjacent vertices of the removed element to
the queue.
• Step 6: Repeat step 5 until the queue is not empty and no vertex is left to be visited.

Dr. Mohammed Hussein

 12
BFS pseudocode

► // Here, Graph is the graph X is the source node

Breadth_First_Search( Graph, X ):
Let Q be the queue
Q.enqueue( X ) // Inserting source node X into the queue
Mark X node as visited.
► While ( Q is not empty )
Y = Q.dequeue( ) // Removing the front node from the queue
► Process all the neighbors of Y, For all the neighbors Z of Y
If Z is not visited:
Q. enqueue( Z ) // Stores Z in Q
Mark Z as visited

Dr. Mohammed Hussein

 13
BFS example

► BFS : 1,2,4,5,3,6,7
1. select the node. 5 4 7 6

2. visit its neighbors in any order.

1 2 3

it explores the graph level-by-level starting from the root node

until it reaches the desired depth or finds the desired node.
 14
BFS example

0,1,2,4,3,6,5,8,7
 15
Code example

https://onlinegdb.com/45JdEWQVC

Dr. Mohammed Hussein

 16
BFS observations

a b c
► optimality:
► always finds the shortest path (fewest edges). d e f
► in unweighted graphs, finds optimal cost path.
► In weighted graphs, not always optimal cost. g h

► retrieval: harder to reconstruct the actual sequence of vertices or edges in the path once
you find it
► conceptually, BFS is exploring many possible paths in parallel, so it's not easy to store a path
array/list in progress
► solution: We can keep track of the path by storing predecessors for each vertex (each vertex can
store a reference to a previous vertex).

► DFS uses less memory than BFS, easier to reconstruct the path once found; but DFS does
not always find shortest path. BFS does.
 17
Depth First Search

► Depth First Search is a graph traversal algorithm that starts at the

root node and explores as far as possible along each branch
before backtracking. This means that DFS visits all the nodes in one
branch before moving on to the next branch.
► DFS is particularly useful for detecting cycles in a graph and for
finding a path between two nodes in a weighted graph. It can
also be used to generate a topological sorting of a directed
acyclic graph.

Dr. Mohammed Hussein

 18
Graph traversals for a binary
tree:

1. Breadth-First Traversal: In this method, the nodes of a binary tree

are traversed in a breadth-first manner, i.e., level by level starting
from the root node.
2. Depth-First Traversal: In this method, the nodes of a binary tree
are traversed in a depth-first manner. The forms of depth-first
traversal are:
- Preorder Traversal: In this traversal, the root node is visited first, then
the left subtree is visited, and finally the right subtree is visited.
In both methods, it is important to keep track of visited nodes to
avoid an infinite loop.

Dr. Mohammed Hussein

 19
Comparing BFS and DFS

► BFS and DFS have different strengths and weaknesses, which make
them suitable for different use cases. BFS is better suited for finding
the shortest path between two nodes in an unweighted graph,
while DFS is better suited for detecting cycles in a graph and for
finding a path between two nodes in a weighted graph.
► In terms of time complexity, both BFS and DFS have a worst-case
time complexity of O(V+E), where V is the number of vertices and E
is the number of edges in the graph. However, BFS typically requires
more memory than DFS, as it needs to store all the nodes at the
current level before moving on to the next level.

Dr. Mohammed Hussein

 20
Depth-first search

depth-first search (DFS): Finds a path between two vertices by exploring

each possible path as far as possible before backtracking.
1. Mark the current node as visited and print the node.
2. Traverse all the adjacent and unmarked nodes and call the recursive function with the index of
the adjacent node.
Depth-first paths from a to all vertices (assuming ABC edge order):
► to b: {a, b}
► to c: {a, b, e, f, c} a b c
► to d: {a, d}
► to e: {a, b, e} d e f
► to f: {a, b, e, f}
► to g: {a, d, g} g h
► to h: {a, d, g, h}
 21
DFS example

► DFS : 1,2,3,6,7,4,5
1. visiting a vertex (node). 5 4 7 6

2. the exploration of vertex (neighbor node).

3. When you have visit neighbor node explore it. 1 2 3

it explores the graph by going deep into each branch

before backtracking to explore another branch.
 22
DFS example

0,1,4,8,7,3,2,6,5
 23
DFS

Dr. Mohammed Hussein

 24
BFS

Dr. Mohammed Hussein

 25
homework

11
9 6

5 4 7 8

1 2 3

10
 26

Depth First Search or DFS for a Graph - GeeksforGee

ks
 27
implement DFS traversal

• Step 1: Create a set or array to keep track of visited nodes.

• Step 2: Choose a starting node.
• Step 3: Create an empty stack and push the starting node onto the stack.
• Step 4: Mark the starting node as visited.
• Step 5: While the stack is not empty, do the following:
• Pop a node from the stack.
• Process or perform any necessary operations on the popped node.
• Get all the adjacent neighbors of the popped node.
• For each adjacent neighbor, if it has not been visited, do the following:
• Mark the neighbor as visited.
• Push the neighbor onto the stack.

• Step 6: Repeat step 5 until the stack is empty.

Dr. Mohammed Hussein

 28
DFS code example

https://onlinegdb.com/Gb7rZlkau

Dr. Mohammed Hussein

 29
DFS pseudocode

► procedure DFS(node):
mark node as visited
process(node)

for each neighbor in node.neighbors:

if neighbor is not visited:
DFS(neighbor)
 30
DFS pseudocode
 31
DFS observations

► discovery: DFS is guaranteed to find a path if one exists.

► retrieval: It is easy to retrieve exactly what the path is (the sequence

of edges taken) if we find it

► optimality: not optimal. DFS is guaranteed to find a path, not

necessarily the best/shortest path
► Example: dfs(a, f) returns {a, d, c, f} rather than {a, d, f}.
 32
BFS vs DFS

Feature BFS DFS

Memory Usage More (queue stores all neighbors) Less (stack stores current path)
Trickier (may need backtracking
Path Reconstruction Easier (guaranteed shortest path) logic)
Not guaranteed (may explore deep
Shortest Path Finding Generally better (explores levels) first)
 33
DFS, BFS runtime

► What is the expected runtime of DFS and BFS, in terms of the number of
vertices V and the number of edges E ?

► Answer: O(|V| + |E|)

► where |V| = number of vertices, |E| = number of edges
► Must potentially visit every node and/or examine every edge once.

► why not O(|V| * |E|) ?

► What is the space complexity of each algorithm?

► (How much memory does each algorithm require?)
 34
Example BFS and DFS

► In binary tree, the BFS (level order)= 1,2,3,4,5,6,7

binary tree
► In binary tree, the DFS (pre-order)= 1,2,4,5,3,6,7
► (pre-order)=(Root,L,R) 1

2 3

4 5 6 7
 35
BFS example

0 1 9 6 75 2 8 3 4

Dr. Mohammed Hussein

 36
DFS example

0129347658

Dr. Mohammed Hussein

 37
Examples for BFS and DFS

DFS

BFS
Dr. Mohammed Hussein
 BFS vs DFS 38

Dr. Mohammed Hussein

https://www.geeksforgeeks.org/difference-between-bfs-and-dfs/
 39
BFS vs DFS

Dr. Mohammed Hussein

 40
Applications of Graph
Traversals

► Graph traversals have numerous applications in computer

science, including network routing, social network analysis, and
web crawling. In network routing, BFS is often used to find the
shortest path between two nodes in a network. In social network
analysis, DFS is often used to identify communities or clusters of
nodes in a network. In web crawling, BFS is often used to discover
new pages on a website.
► Graph traversals are also used in various machine learning
algorithms, such as decision trees and random forests. In these
algorithms, BFS and DFS are used to traverse the decision tree
and make predictions based on the features of the input data.

Dr. Mohammed Hussein

 41
BFS shortest path between two
nodes in a network

BFS (Breadth-First Search) algorithm can be used to find the shortest path between two
nodes in a network. Here's how:
1. 1. Start from the source node and mark it as visited.
2. 2. Enqueue the source node in a queue.
3. 3. While the queue is not empty, dequeue a node from the queue.
4. 4. For each adjacent node to the dequeued node that hasn't been visited yet, mark it
as visited, enqueue it in the queue, and set its parent to the dequeued node.
5. 5. If the dequeued node is the target node, then stop the search.
6. 6. Continue until the target node is found or the queue becomes empty.
Once the target node is found, we can find the shortest path by backtracking from the
target node using its parent references until we reach the source node. So, in summary, the
BFS algorithm can be used to explore the nodes of the network in a level-by-level fashion,
starting from the source node, until the target node is found. The shortest path can then be
traced back from the target node to the source node using the parent references.

Dr. Mohammed Hussein

 42
DFS : identify communities or
clusters of nodes in a network

► DFS (Depth-First Search) is a popular graph traversal algorithm that can be used for identifying
clusters or communities of nodes in a network. The algorithm works by exploring a graph or network
starting from a particular node and then visiting all of its neighbors before moving on to the next set
of neighbors. This way, it can "step into" the network and traverse its structure in a depth-first manner.

► To identify clusters or communities of nodes in a network using DFS, we can start by selecting a
random or central node and exploring its neighbors using DFS. As each node is explored, we can
assign it to a particular cluster or community based on its characteristics or attributes (such as its
degree centrality or other network metrics). We can then continue exploring the rest of the network,
visiting each new node that we encounter and assigning it to a cluster or community as we go.

► After the DFS algorithm has finished exploring the entire network, we can have an idea of the
different clusters or communities of nodes that exist in the network. This can be useful for
understanding the structure and organization of complex networks, identifying important nodes or
hubs, and even predicting the behavior or dynamics of the network under different conditions.

Dr. Mohammed Hussein

 43
BFS : to discover new pages on
a website

► Web crawling is the process of automatically discovering and traversing through

web pages to gather information. BFS (Breadth-First Search) is an algorithm that is
often used in web crawling to discover new pages on a website.

► In BFS, the crawler starts at the root page (e.g., the homepage) and gradually
expands its search to neighboring pages. It adds all the child pages of the current
page to a queue, and then visits the pages in the queue one at a time, adding
their child pages to the queue. This process is repeated until the crawler has visited
all the pages it can find.

► BFS is useful for discovering new pages on a website because it ensures that all the
pages at a given depth are visited before proceeding to the next depth. This
makes it effective for discovering pages that are linked to from many other pages
on the website.

Dr. Mohammed Hussein

 44
Graph traversals :machine
learning algorithms

► Graph traversals are used in various machine learning algorithms including decision trees and
random forests to explore and analyze the underlying data structure or relationships among the
data points.

► In decision trees, the graph traversal is used to select the best possible split for each tree node. The
algorithm traverses the features of the dataset, evaluating their impact on the target variable at
each branch. Once a split is made based on a particular feature, the algorithm moves down to
the next level of the tree and repeats the process until a stopping criterion is reached.

► Similarly, in random forests, multiple decision trees are generated based on random subsets of the
input features and training data. The graph traversal is used to learn a set of decision rules which
are combinations of rules learned from each individual decision tree. By traversing these decision
trees, random forest algorithms can identify the most important features for classification,
regression, or clustering tasks.

► Overall, graph traversals are an important component of many machine learning algorithms and
are used to discover patterns, relationships, and correlations within the data.

Dr. Mohammed Hussein

 45
Conclusion

► Graph traversals are an essential operation in graph theory and

have numerous applications in computer science. Breadth First
Search and Depth First Search are the two most common graph
traversal algorithms, each with its own strengths and weaknesses.
► Understanding these algorithms and their use cases is important
for anyone working with graphs or machine learning algorithms
that use graphs. By choosing the right algorithm for the task at
hand, we can optimize our solutions and achieve better results.

Dr. Mohammed Hussein