Rice: /* Analysis */

2024-03-20T17:34:49Z

Analysis

← Older revision		Revision as of 17:34, 20 March 2024
Line 37:		Line 37:

	Therefore, the overall runtime complexity would be O(V + E).		Therefore, the overall runtime complexity would be O(V + E).

			= Application =
			BFS is one solution to the [[Shortest Path Problem\|shortest path problem]]. Given an ''unweighted'' graph, BFS can find the ''shortest number of jumps'' from one node to every other node (the distance array being kept track of). Notably, BFS does not work for weighted graphs due to each edge not being valued the same.
	[[Category:Algorithms]]		[[Category:Algorithms]]

Rice: Created page with "{{Infobox Algorithm|runtime=O(V+E)|class=Graph Algorithm}} '''Breadth-first search (BFS)''' is a graph traversal algorithm. = Approach = At the core of BFS is a ''priority queue'' of unvisited nodes''.'' # At the start, the source node has a distance of 0, whereas the rest has infinite distance. The source node is pushed into the queue. # The queue is popped as the first node in the queue is visited. # Upon visiting a node, if the node's distance is infinity (i.e...."

2024-03-20T17:24:38Z

Created page with "{{Infobox Algorithm|runtime=O(V+E)|class=Graph Algorithm}} '''Breadth-first search (BFS)''' is a graph traversal algorithm. = Approach = At the core of BFS is a ''priority queue'' of unvisited nodes''.'' # At the start, the source node has a distance of 0, whereas the rest has infinite distance. The source node is pushed into the queue. # The queue is popped as the first node in the queue is visited. # Upon visiting a node, if the node's distance is infinity (i.e...."

New page

{{Infobox Algorithm|runtime=O(V+E)|class=[[Graph Algorithm]]}}

'''Breadth-first search (BFS)''' is a graph traversal algorithm.

= Approach =
At the core of BFS is a ''priority queue'' of unvisited nodes''.''

# At the start, the source node has a distance of 0, whereas the rest has infinite distance. The source node is pushed into the queue.
# The queue is popped as the first node in the queue is visited.
# Upon visiting a node, if the node's distance is infinity (i.e. it hasn't been visited and isn't in the queue), BFS adds the node to the queue.
# The next node is popped and visited until no nodes remain.

= Implementation =
<pre>
BFS(G, s):
# Initialize
n = len(V)
let Q be a FIFO queue
let d be distance array of length n
for each vertex u in V:
d[u] = infty
d[s] = 0
Q.enqueue(s);

while Q is not empty:
visiting = Q.pop();
for each node in adj[visiting]:
if d[node] = infty:
d[node] = d[visiting] + 1
Q.enqueue(node)
</pre>

= Analysis =
Since the nodes only enter the queue when their distance is infinity, and their distance gets updated as they enter the queue, ''each node only enters the queue once''. O(V).

Inside each iteration, the adjacency list of each node is looked at, which takes O(E).

Therefore, the overall runtime complexity would be O(V + E).
[[Category:Algorithms]]

BFS - Revision history

Rice: /* Analysis */