Graph-traversal：練習問題

In the context of graph-traversal, which algorithm is best suited for finding the shortest path between two nodes in an unweighted graph?

In an unweighted graph, a student needs to find the shortest path between two nodes. Which graph-traversal algorithm should they use, and which primary data structure is used to manage the nodes that are discovered but not yet visited to ensure this shortest path property is maintained?

Consider a directed graph where a Depth-First Search (DFS) is implemented. During the traversal, an edge is encountered that points from the current node to an ancestor currently in the recursion stack. What property of the graph does this specific edge identify?

In the context of graph-traversal, which algorithm is typically used to find the shortest path between two nodes in an unweighted graph?

A developer is using graph-traversal to solve a puzzle. The search space is modeled as a tree where the target node is known to be very close to the root, but the tree itself is infinitely deep. Which algorithm is guaranteed to find the target, and why?

In an undirected, unweighted graph, which specific traversal algorithm is most suitable for finding the shortest path between two given vertices?

A depth-first search (DFS) is applied to a graph. Describe a specific real-world scenario mentioned in the syllabus where this traversal method is commonly used.

During a Breadth-first search on an unweighted graph, a queue is used to manage vertices. Explain the relationship between the distance from the start node and the order in which vertices are added to this queue.

A graph contains 5 nodes (A, B, C, D, E) and the following undirected edges: (A,B), (A,C), (B,D), (C,E).

(a) Trace a Breadth-First Search (BFS) starting at node A. Assume nodes are visited in alphabetical order where a choice exists.
(b) Identify a typical application for a Breadth-First Search in an unweighted graph.

A Depth-First Search (DFS) and Breadth-First Search (BFS) are used to explore a graph representing a set of connected islands.

(a) Describe the specific application for BFS in an unweighted graph and why it is more suitable than DFS for this purpose.

(b) Explain the role of stack frames in a recursive implementation of DFS.

(c) Compare the space complexity of BFS and DFS when traversing a graph that is very 'wide' (high branching factor) but has a shallow depth.