Breadth First Search
1. Which of the following policies does a queue follow?
2. Which of the following best describes the main purpose of a standard graph traversal algorithm?
3. Consider the following undirected graph:
Vertices, V = [1, 2, 3, 4, 5, 6]
Edges, E = [[1, 2], [1, 3], [2, 4], [2, 5], [3, 5], [3, 6]]
Where each array within E signifies an edge between the two mentioned vertices.
Which of the following best describes the above graph?
Vertices, V = [1, 2, 3, 4, 5, 6]
Edges, E = [[1, 2], [1, 3], [2, 4], [2, 5], [3, 5], [3, 6]]
Where each array within E signifies an edge between the two mentioned vertices.
Which of the following best describes the above graph?
4. Consider the following undirected graph:
Vertices, V = [a, b, c, d, e, f]
Edges, E = [[a, b], [a, c], [b, d], [b, e], [c, e], [c, f]]
Where each array within E signifies an edge between the two mentioned vertices.
If we store the vertices in a queue in top-to-bottom (parent-to-child) order and left-to-right order, where edges appearing earlier in the edge list are considered first, with 'a' as the root, at which index will vertex 'e' be stored? Assume 0-based indexing and no deletions from the queue.
Vertices, V = [a, b, c, d, e, f]
Edges, E = [[a, b], [a, c], [b, d], [b, e], [c, e], [c, f]]
Where each array within E signifies an edge between the two mentioned vertices.
If we store the vertices in a queue in top-to-bottom (parent-to-child) order and left-to-right order, where edges appearing earlier in the edge list are considered first, with 'a' as the root, at which index will vertex 'e' be stored? Assume 0-based indexing and no deletions from the queue.
5. In Breadth First Search (BFS), which data structure is primarily used to determine the order in which vertices are processed?
6. Starting from a source vertex, BFS visits vertices level by level. If a vertex is discovered for the first time, when is it normally marked as visited?
7. For a graph represented using an adjacency list, what is the usual time complexity of BFS when all vertices reachable from the source are traversed?
8. Suppose BFS starts from vertex A in an unweighted graph and reaches vertex B for the first time after traversing three edges. What does this first discovery tell us about the shortest distance from A to B?
9. Consider a connected undirected graph with vertices. If BFS starts from one vertex and reaches every other vertex, how many edges will the BFS traversal tree contain?