Data Structures and Algorithms · Unit 9
Graphs and Graph Algorithms
Exam-focused notes for Graphs and Graph Algorithms (Data Structures and Algorithms, BIT201): what the TU syllabus asks and how it has actually been tested, with 6 solved past questions from this unit.
What this unit covers
- Graph definition and types
- Graph representation using adjacency matrix
- Graph traversal definition
- Breadth first search (BFS) algorithm
- Depth first search (DFS) algorithm
- BFS and DFS tracing with examples
- Shortest path problem definition
- Dijkstra's algorithm for shortest path
- Spanning tree definition
- Minimum spanning tree (MST) definition
- Prim's algorithm for MST
- Round Robin algorithm for MST
BFS and DFS tracing with examples
Traverse the following graph using BFS and DFS. [5]
The question asks to traverse a graph using BFS and DFS, but the actual graph (the figure/diagram) is not included in the text provided. No adjacency list, adjacency matrix, edge set, or vertex set is given. Missing data: The specific graph (vertices and ed...
Full solved answer →Spanning tree definition
Define spanning tree. Explain minimum spanning tree with example. [5]
A spanning tree of a connected, undirected graph G = (V, E) is a subgraph that: - Includes all vertices of the graph - Is a tree (connected and acyclic) - Has exactly V - 1 edges A graph with n vertices will have a spanning tree with exactly n - 1 edges. --...
Full solved answer →Graph representation using adjacency matrix
Explain adjacency matrix representation of graphs with example. [5]
An adjacency matrix is a 2D square matrix used to represent a graph. For a graph with n vertices, the adjacency matrix is an n × n matrix (usually denoted A), where each entry A[i][j] indicates whether there is an edge between vertex i and vertex j. --- Con...
Full solved answer →Dijkstra's algorithm for shortest path
What is shortest path algorithm? Use Dijkstra's algorithm to find shortest path between the vertices of a and z in the graph given below.[10]
Problem asks for: definition of shortest path algorithm + Dijkstra applied to find shortest path from vertex $a$ to vertex $z$. Critical issue: The actual graph image is NOT provided in the question. Edge weights and connectivity cannot be read. Since the t...
Full solved answer →Graph traversal definition
What is graph traversal? Explain breadth first search. [5]
Graph traversal refers to the process of visiting each vertex (node) in a graph exactly once in a systematic manner. Unlike trees, graphs may contain cycles, so we need to keep track of visited vertices to avoid processing the same vertex more than once. Th...
Full solved answer →Prim's algorithm for MST
Trace Prim's Algorithm to find minimum spanning tree for the following graph. [5]
Given data: - Task: Trace Prim's Algorithm to find the Minimum Spanning Tree. - Graph structure: NOT PROVIDED. The question references "the following graph," but no graph image, adjacency matrix, or edge/weight list was included in the input. Missing data: ...
Full solved answer →Make Unit 9 stick
Practice BIT201 with flashcards & quizzes