AI Midterm

What is the space complexity of BFS?

O(V) to store the queue and visited set.

What is Depth First Search (DFS?)

An algorithm for traversing or searching tree or graph data structures. It starts at the root (or an arbitrary node) and explores as far as possible along each branch before backtracking.

What does DFS use?

Uses a Stack to keep track of nodes. Follows LIFO (Last-In, First-Out) logic.

What is the time complexity for DFS?

What is the time complexity of BFS?

O (V+E) where V is vertices and E is edges.

What is the main use of BFS?

Finding the shortest path between two nodes in an unweighted graph (minimum number of edges).

What is Breadth First Search (BFS)?

A graph traversal algorithm that explores nodes layer-by-layer, visiting all neighbors at the current depth before moving to nodes at the next depth level.

How does BFS work?

It uses a Queue (FIFO - First In, First Out) to manage nodes, exploring horizontally across the graph before going deeper.

What are 3 real-world applications of BFS?

1. Social Networking: Finding "friends of friends" (degrees of separation).

2. Web Crawling: Mapping links level-by-level.

3. GPS Navigation: Finding neighboring locations.

Why does BFS use a "visited" set?

To keep track of visited nodes and avoid cycles (infinite loops) in graphs.

BFS vs. DFS: Key Difference

• BFS: Uses a Queue, explores layer-by-layer (horizontal).

• DFS: Uses a Stack (or recursion), explores branch-by-branch (vertical)