CODEWITHSUNDEEP
algorithmtime-complexitybreadth-first-search
Gary
Gary

Reputation: 2167

Understanding the Running Time Complexity of BFS

I am having a tough time understanding one element of the time complexity of the BFS algorithm.

For an undirected graph, my professor says that each edge (u,v) is traversed twice. Once from the direction of u, and once from the direction of v. Therefore, the step of finding all of the unlabeled vertices adjacent to at least one vertex is O(|E|).

Can someone explain how each edge is traversed once in a directed graph and twice in an undirected graph? I thought, that with BFS, we're simply going from the root vertex (s), outwards? Where is this second traversal coming from?

Upvotes: 2

Views: 508

Answers (1)

Saeid
Saeid

Reputation: 4255

Assuming that you are using an adjacency list for storing your graph.

Breadth-First-Search(Graph, root):
 2 
 3     for each node n in Graph:            
 4         n.distance = INFINITY        
 5         n.parent = NIL
 6 
 7     create empty queue Q      
 8 
 9     root.distance = 0
10     Q.enqueue(root)                      
11 
12     while Q is not empty:        
13     
14         current = Q.dequeue()
15     
16         for each node n that is adjacent to current:
17             if n.distance == INFINITY:
18                 n.distance = current.distance + 1
19                 n.parent = current
20                 Q.enqueue(n)

In a undirected graph v and u are in each others adjacency lists. So in line 16 when we check for the adjacent nodes, when the current node is u we check the adjacent node v and when the current node is u we check the adjacent node v. But it doesn't mean we push v in the queue again. We simply check it.

However in an undirected graph only v is in u 's adjacency list. So each edge u->v is getting checked once.

I assume that your professor meant we check each edge twice instead of traverse.

Upvotes: 1

Related Questions