Graph traversal BFS and DFS study guide

Definition of a graph

A graph is a collection of nodes (vertices) connected by edges. Examples: social networks, transportation systems.

True or False: A graph can have multiple edges between the same nodes.

True. This is known as a multigraph, where multiple edges can exist between any two vertices.

Vertices vs. Edges

Vertices: the fundamental units of a graph. Edges: the connections between vertices.

What is an undirected graph?

An undirected graph has edges that do not have a direction. Example: a friendship relation.

Directed vs. Undirected

Directed: edges have a direction. Undirected: edges have no direction. - Example: Twitter (directed), Facebook (undirected).

Fill in the blank: A ______ graph has no cycles.

A forest graph has no cycles. It is a disjoint union of trees.

What is a weighted graph?

A weighted graph assigns a weight or cost to each edge, enabling analysis of shortest paths.

Degree of a vertex

The degree of a vertex is the number of edges connected to it. For directed graphs, consider in-degree and out-degree.

Cause → Effect: Adding an edge to a graph

Adding an edge increases the graph's connectivity and can create new paths between vertices.

Adjacency list vs. Adjacency matrix

Adjacency list uses lists to represent connections. Adjacency matrix uses a 2D array. - Space: matrix O(V^2), list O(V + E).

Connected graph definition

A connected graph has a path between every pair of vertices. If disconnected, it has multiple components.

What is a cyclic graph?

A cyclic graph contains at least one cycle, a path that starts and ends at the same vertex.

What does BFS stand for?

BFS stands for Breadth-First Search, a graph traversal algorithm.

BFS explores nodes based on which principle?

BFS explores all neighbors of a node before moving to the next level.

True or False: BFS can find the shortest path in unweighted graphs.

True. BFS guarantees the shortest path in unweighted graphs by exploring all nodes at the present depth before moving on.

What data structure is primarily used in BFS?

BFS uses a queue to keep track of nodes to explore next.

Fill in the blank: BFS processes nodes in order of their __________.

distance from the starting node.

How does BFS handle cycles in graphs?

BFS keeps track of visited nodes to prevent infinite loops.

List three applications of BFS.

- Shortest path in unweighted graphs - Finding connected components - Web crawling

What is the time complexity of BFS?

The time complexity of BFS is $\displaystyle O(V + E)$ where $\displaystyle V$ is vertices and $\displaystyle E$ is edges.

Describe the process of BFS in one sentence.

BFS starts at the source node, explores all neighboring nodes, and continues level by level.

Why is BFS not ideal for weighted graphs?

BFS does not account for edge weights, potentially missing the shortest path.

How do you implement BFS?

1. Initialize a queue with the starting node. 2. Mark it as visited. 3. While the queue is not empty: dequeue, process, enqueue unvisited neighbors.

BFS produces which type of tree?

BFS produces a breadth-first tree or level order tree representing the traversal.

In BFS, what role do visited nodes play?

Visited nodes prevent re-exploration, ensuring efficient traversal.

What is the space complexity of BFS?

The space complexity of BFS is $\displaystyle O(V)$, since it stores all vertices in memory.

Depth-First Search (DFS) definition

DFS is an algorithm for traversing or searching tree or graph data structures. It explores as far as possible along each branch before backtracking.

What data structure is primarily used for DFS?

DFS uses a stack data structure, either explicitly or through recursion.

True or False: DFS can get stuck in loops.

True. If cycles are present in a graph without proper checks, DFS may revisit nodes indefinitely.

DFS traversal order

DFS visits nodes in a depthward motion before moving laterally: - Start at root - Explore child nodes until leaf - Backtrack

Applications of DFS

- Pathfinding in mazes - Topological sorting - Cycle detection - Solving puzzles like Sudoku

What is backtracking in DFS?

Backtracking in DFS refers to the process of returning to the previous node when no further exploration is possible.

Fill in the blank: DFS is typically implemented using __________.

recursion or an explicit stack.

Difference between DFS and BFS

DFS explores deeper into one branch first, while BFS explores all neighbors at the present depth prior to moving on.

Complexity of DFS in terms of time

The time complexity of DFS is $\displaystyle O(V + E)$, where $\displaystyle V$ is the number of vertices and $\displaystyle E$ is the number of edges.

True or False: DFS is less memory efficient than BFS.

False. DFS can be more memory efficient, especially in sparse graphs, due to its depth-first nature.

Example of DFS in action

Given a graph with nodes A, B, C, and D: Starting at A, DFS visits A, then recursively visits B, C, then backtracks to A before visiting D.

What happens when DFS hits a dead end?

When DFS hits a dead end, it backtracks to the last node with unexplored neighbors and continues the search.

Cause of stack overflow in DFS

A stack overflow can occur in DFS when the recursion goes too deep, particularly in very deep or infinitely branching graphs.

How does DFS handle disconnected graphs?

DFS can handle disconnected graphs by initiating a new DFS from each unvisited node to ensure all components are explored.

BFS vs. DFS: Memory Usage

BFS requires more memory due to storing all nodes at the current level. - Queue-based storage - Space complexity: O(b^d) - b = branching factor, d = depth

True or False: BFS can find the shortest path.

True. BFS explores nodes level by level, guaranteeing the shortest path in unweighted graphs.

DFS: Advantage over BFS

DFS uses less memory in deep graphs because it explores as far as possible along each branch before backtracking.

BFS traversal order

BFS visits all neighbors before moving to the next level, resulting in a layer-wise traversal.

Fill in the blank: DFS is more suitable for __________.

DFS is more suitable for scenarios with deep and narrow search spaces, like puzzle solving.

Comparison: Backtracking in DFS vs. BFS

DFS utilizes backtracking to find solutions in complex paths. - Efficient for maze problems - BFS does not backtrack.

Disadvantage of BFS

BFS can be less efficient in terms of time if the solution is located deep in the graph. - High time complexity in wide graphs.

Question: Which algorithm is better for large graphs?

Neither is universally better. - BFS is better for shortest paths. - DFS is better for memory usage.