Graph_Traversals_Breadth_First_Search_Flashcards
Define graph traversal.
It is the process of visiting each node in a graph at most once by following edges.
How does Breadth-First Search (BFS) operate?
It explores nodes level-by-level, visiting all immediate neighbors before moving deeper.
Which data structure powers BFS?
A FIFO (First-In-First-Out) queue.
Name three key node attributes used in BFS.
visited (boolean), π (parent), d (depth from start).
What is the function of the π (parent) attribute?
It records the node from which the current node was discovered.
What does the d (depth) attribute track?
The number of edges from the start node to the current node.
What’s the first step in running BFS?
Mark the start node as visited, set its depth to 0, and enqueue it.
When do you enqueue a node in BFS?
You have discovered the node, but haven’t explored its neighbors yet.
1. Mark it as visited
2. Set its distance from the source
3. Record its parent in the traversal (e.g., π[v] = u).
4. Add it to the queue (e.g., queue.append(v)).
How does BFS ensure shortest paths?
By visiting nodes in increasing order of distance, it guarantees the shortest path in edge count.
How do you reconstruct a path using BFS?
Follow the parent pointers (π) from the target node back to the start.
What is the time complexity of BFS?
O(V + E), where V is vertices and E is edges.
What is the space complexity of BFS?
O(V), due to storage of visited markers, parents, depths, and the queue.
Can BFS be used on both directed and undirected graphs?
Yes, it works on both types.
Does BFS revisit nodes?
No, each node is visited only once.
What real-world task is similar to BFS?
Web crawling, such as Google indexing pages by following hyperlinks.
What traversal strategy does BFS represent?
Breadth-wise exploration—visiting all neighbors before going deeper.
