BFS traversal
Given a graph, print all the nodes by performing BFS traversal
Code
class GraphNode
label = ''
edges = []
end
def bfs_traversal(start_node)
return nil if start_node.nil?
q = [start_node]
while !q.empty?
// Examine edges of q
x = q.remove_front
x.edges.each do |e|
puts e.label
q.add_back(e)
end
end
end
Time complexity
- Time: O(E+V) where e is the number of edges and V is the number of vertices
- In other words BFS operates in linear time
- Space: O(V) since we are storing the vertices to be parsed in a queue