CS2004_Graph_Traversal_Flashcards

Question 1

What is Depth-First Search (DFS)?

Answer 1

DFS is a graph traversal algorithm that explores as far as possible along each branch before backtracking.

✅ Uses a stack (or recursion) to track the path.

Question 2

What is Breadth-First Search (BFS)?

Answer 2

BFS is a graph traversal algorithm that explores all neighbours of a node before moving to the next level.

✅ Uses a queue to maintain the order of exploration.

Question 3

What is the time complexity of BFS and DFS?

Answer 3

Both BFS and DFS run in O(V + E), where V is the number of vertices and E is the number of edges.

Question 4

What is Dijkstra’s Algorithm used for?

Answer 4

Dijkstra’s algorithm finds the shortest path from a starting node to all other nodes in a weighted graph with non-negative edge weights.

Question 5

How does Dijkstra’s algorithm work?

Answer 5

It uses a priority queue to explore the lowest-cost node first and updates distances to neighbours based on cumulative cost.

Question 6

What is A* search?

Answer 6

A* is a pathfinding algorithm that uses both actual cost from the start and estimated cost to the goal (via a heuristic).

Question 7

What is the key difference between A* and Dijkstra’s Algorithm?

Answer 7

A* uses a heuristic to guide the search, making it more efficient for goal-directed searches.

✅ Dijkstra is uninformed; A* is informed.

Question 8

What is a Minimum Spanning Tree (MST)?

Answer 8

An MST is a subset of edges in a connected, weighted graph that connects all vertices with the minimum total edge weight and no cycles.

Question 9

What is Prim’s Algorithm?

Answer 9

Prim’s algorithm builds the MST by starting from one node and repeatedly adding the smallest edge connecting the tree to a new node.

Question 10

What is Kruskal’s Algorithm?

Answer 10

Kruskal’s algorithm builds the MST by sorting all edges by weight and adding them one by one, avoiding cycles using disjoint sets.