Skip to content
CampusPrep
CS-303 · Data Structure/Quick Revision Short Notes

Data Structure (CS-303) - Unit 4 Short Notes

How unit 4 is examined

This unit covers graph terms, representations, DFS and BFS, MST (Kruskal, Prim) and Dijkstra; MST, DFS/BFS and their comparison carry most of the marks.

Graphs: Introduction

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Not asked since 2022</span>

Definition. A graph $G=(V,E)$ is a set of vertices $V$ (nodes) joined by a set of edges $E$ (links between pairs of vertices); <mark>a graph models pairwise relationships between objects</mark>.

Key points.

  1. Two vertices joined by an edge are called adjacent, and the edge is incident on both of them.
  2. An edge may carry a weight (cost, distance), which makes the graph weighted.
  3. A path is a sequence of vertices joined by edges; a cycle is a path that returns to its start.
  4. A graph is connected if a path exists between every pair of vertices; a maximal connected part is a connected component.

Classification of graph: Directed and Undirected graphs

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">High weight</span>

Definition. In an undirected graph each edge $(u,v)$ is an unordered pair and can be travelled both ways; in a directed graph (digraph) each edge $\langle u,v\rangle$ is an ordered pair pointing from $u$ to $v$.

Diagram. <figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u4-01" viewBox="0 0 338 252" width="338" height="252" role="img" aria-label="Undirected graph: edges have no direction"><style>#dsfig-u4-01 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u4-01 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u4-01 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u4-01 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u4-01 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u4-01 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u4-01 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u4-01 .t{fill:#16181D;font-weight:500}#dsfig-u4-01 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u4-01 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u4-01 .dot{fill:#16181D}#dsfig-u4-01 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u4-01 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u4-01 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u4-01 .ah{fill:#454C5A}#dsfig-u4-01 .ah.hi{fill:#2340B8}#dsfig-u4-01 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u4-01 .wl .t{font-size:12px;font-weight:700}#dsfig-u4-01 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u4-01 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u4-01 .e{stroke:#B1B7C3}html.dark #dsfig-u4-01 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u4-01 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u4-01 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u4-01 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u4-01 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u4-01 .t{fill:#E6E8ED}html.dark #dsfig-u4-01 .t.inv{fill:#0F1115}html.dark #dsfig-u4-01 .kd{stroke:#E6E8ED}html.dark #dsfig-u4-01 .dot{fill:#E6E8ED}html.dark #dsfig-u4-01 .ann{fill:#8FA3FF}html.dark #dsfig-u4-01 .lbl{fill:#858D9C}html.dark #dsfig-u4-01 .ptr{fill:#8FA3FF}html.dark #dsfig-u4-01 .ah{fill:#B1B7C3}html.dark #dsfig-u4-01 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u4-01 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u4-01 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u4-01 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah20" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah" d="M0,1 L9,5 L0,9 z"/></marker><marker id="ahh20" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah hi" d="M0,1 L9,5 L0,9 z"/></marker></defs><path class="e" d="M55.8,115.5 L153.2,50.5"/><path class="e" d="M55.8,136.5 L153.2,201.5"/><path class="e" d="M184.8,50.5 L282.2,115.5"/><path class="e" d="M184.8,201.5 L282.2,136.5"/><circle class="n" cx="40" cy="126" r="18"/><text class="t" x="40" y="126" dy=".35em" text-anchor="middle">A</text><circle class="n" cx="169" cy="40" r="18"/><text class="t" x="169" y="40" dy=".35em" text-anchor="middle">B</text><circle class="n" cx="169" cy="212" r="18"/><text class="t" x="169" y="212" dy=".35em" text-anchor="middle">C</text><circle class="n" cx="298" cy="126" r="18"/><text class="t" x="298" y="126" dy=".35em" text-anchor="middle">D</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">Undirected graph: edges have no direction</figcaption></figure> <figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u4-02" viewBox="0 0 338 252" width="338" height="252" role="img" aria-label="Directed acyclic graph (DAG): arrows, no cycle"><style>#dsfig-u4-02 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u4-02 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u4-02 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u4-02 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u4-02 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u4-02 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u4-02 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u4-02 .t{fill:#16181D;font-weight:500}#dsfig-u4-02 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u4-02 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u4-02 .dot{fill:#16181D}#dsfig-u4-02 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u4-02 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u4-02 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u4-02 .ah{fill:#454C5A}#dsfig-u4-02 .ah.hi{fill:#2340B8}#dsfig-u4-02 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u4-02 .wl .t{font-size:12px;font-weight:700}#dsfig-u4-02 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u4-02 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u4-02 .e{stroke:#B1B7C3}html.dark #dsfig-u4-02 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u4-02 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u4-02 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u4-02 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u4-02 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u4-02 .t{fill:#E6E8ED}html.dark #dsfig-u4-02 .t.inv{fill:#0F1115}html.dark #dsfig-u4-02 .kd{stroke:#E6E8ED}html.dark #dsfig-u4-02 .dot{fill:#E6E8ED}html.dark #dsfig-u4-02 .ann{fill:#8FA3FF}html.dark #dsfig-u4-02 .lbl{fill:#858D9C}html.dark #dsfig-u4-02 .ptr{fill:#8FA3FF}html.dark #dsfig-u4-02 .ah{fill:#B1B7C3}html.dark #dsfig-u4-02 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u4-02 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u4-02 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u4-02 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah21" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah" d="M0,1 L9,5 L0,9 z"/></marker><marker id="ahh21" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah hi" d="M0,1 L9,5 L0,9 z"/></marker></defs><path class="e" d="M55.8,115.5 L151.5,51.6" marker-end="url(#ah21)"/><path class="e" d="M55.8,136.5 L151.5,200.4" marker-end="url(#ah21)"/><path class="e" d="M184.8,50.5 L280.5,114.4" marker-end="url(#ah21)"/><path class="e" d="M184.8,201.5 L280.5,137.6" marker-end="url(#ah21)"/><circle class="n" cx="40" cy="126" r="18"/><text class="t" x="40" y="126" dy=".35em" text-anchor="middle">A</text><circle class="n" cx="169" cy="40" r="18"/><text class="t" x="169" y="40" dy=".35em" text-anchor="middle">B</text><circle class="n" cx="169" cy="212" r="18"/><text class="t" x="169" y="212" dy=".35em" text-anchor="middle">C</text><circle class="n" cx="298" cy="126" r="18"/><text class="t" x="298" y="126" dy=".35em" text-anchor="middle">D</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">Directed acyclic graph (DAG): arrows, no cycle</figcaption></figure>

Key points.

  1. Directed graph: every edge has a direction, so $A\to B$ does not imply $B\to A$; example: web links, one-way roads.
  2. Undirected graph: edges are two-way, so $(A,B)$ and $(B,A)$ are the same edge; example: a friendship network.
  3. Degree of a vertex is the number of edges incident on it; in an undirected graph $\sum \deg(v)=2E$.
  4. In a directed graph the indegree is the number of edges entering a vertex and the outdegree the number leaving it; degree = indegree + outdegree.
  5. An acyclic graph has no cycle; a tree is a connected undirected acyclic graph.
  6. A Directed Acyclic Graph (DAG) is a directed graph with no directed cycle; it has a topological order and is used for task scheduling and expression trees.
  7. A tournament tree is a complete binary tree in which each internal node holds the winner (winner tree) or loser (loser tree) of its two children, so the root gives the overall winner in $O(n)$ build time; it is used for external merge sort and selection.
  8. Common data-structure operations are traverse (visit every item), insert, delete, search and sort; each is used to access or organise stored data.

Answer frame. Open with the definition of each type in one line; draw one small undirected and one directed graph; define degree with indegree/outdegree, then acyclic; for the 14-mark note give DAG (with example), tournament tree, then list the five operations with one use each; close with one application per type.

Pitfall: Do not say degree of a vertex "is the number of vertices"; it counts edges, and a self-loop counts twice.

Asked: [14 marks] (Nov 2019) Write short notes on: a) Directed Acyclic graph b) Tournament Tree c) Common operation in data structure Asked: [7 marks] (Dec 2020) Discuss with reference to graphs: i) Directed graph ii) Undirected graph iii) Degree of vertex iv) Acyclic graph

Representation

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Medium weight</span>

Definition. A graph is stored in memory mainly as an adjacency matrix ($V\times V$ array), an adjacency list (array of linked lists) or an adjacency multilist (one record per edge); <mark>an adjacency matrix costs $O(V^2)$ space, an adjacency list $O(V+E)$</mark>.

Example. Graph of Dec 2023: vertices A-F, edges AB, AC, AD, AE, BD, BE, CD, DF, EF.

<figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u4-03" viewBox="0 0 467 252" width="467" height="252" role="img" aria-label="Graph of Dec 2023 (undirected, 6 vertices, 9 edges)"><style>#dsfig-u4-03 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u4-03 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u4-03 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u4-03 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u4-03 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u4-03 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u4-03 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u4-03 .t{fill:#16181D;font-weight:500}#dsfig-u4-03 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u4-03 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u4-03 .dot{fill:#16181D}#dsfig-u4-03 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u4-03 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u4-03 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u4-03 .ah{fill:#454C5A}#dsfig-u4-03 .ah.hi{fill:#2340B8}#dsfig-u4-03 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u4-03 .wl .t{font-size:12px;font-weight:700}#dsfig-u4-03 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u4-03 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u4-03 .e{stroke:#B1B7C3}html.dark #dsfig-u4-03 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u4-03 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u4-03 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u4-03 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u4-03 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u4-03 .t{fill:#E6E8ED}html.dark #dsfig-u4-03 .t.inv{fill:#0F1115}html.dark #dsfig-u4-03 .kd{stroke:#E6E8ED}html.dark #dsfig-u4-03 .dot{fill:#E6E8ED}html.dark #dsfig-u4-03 .ann{fill:#8FA3FF}html.dark #dsfig-u4-03 .lbl{fill:#858D9C}html.dark #dsfig-u4-03 .ptr{fill:#8FA3FF}html.dark #dsfig-u4-03 .ah{fill:#B1B7C3}html.dark #dsfig-u4-03 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u4-03 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u4-03 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u4-03 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah22" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah" d="M0,1 L9,5 L0,9 z"/></marker><marker id="ahh22" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah hi" d="M0,1 L9,5 L0,9 z"/></marker></defs><path class="e" d="M55.8,115.5 L153.2,50.5"/><path class="e" d="M55.8,136.5 L153.2,201.5"/><path class="e" d="M58.7,129.1 L279.3,165.9"/><path class="e" d="M58,120 L280,46"/><path class="e" d="M182.4,53.4 L284.6,155.6"/><path class="e" d="M188,40 L279,40"/><path class="e" d="M187,206 L280,175"/><path class="e" d="M316,163 L409,132"/><path class="e" d="M313.8,50.5 L411.2,115.5"/><circle class="n" cx="40" cy="126" r="18"/><text class="t" x="40" y="126" dy=".35em" text-anchor="middle">A</text><circle class="n" cx="169" cy="40" r="18"/><text class="t" x="169" y="40" dy=".35em" text-anchor="middle">B</text><circle class="n" cx="169" cy="212" r="18"/><text class="t" x="169" y="212" dy=".35em" text-anchor="middle">C</text><circle class="n" cx="298" cy="169" r="18"/><text class="t" x="298" y="169" dy=".35em" text-anchor="middle">D</text><circle class="n" cx="298" cy="40" r="18"/><text class="t" x="298" y="40" dy=".35em" text-anchor="middle">E</text><circle class="n" cx="427" cy="126" r="18"/><text class="t" x="427" y="126" dy=".35em" text-anchor="middle">F</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">Graph of Dec 2023 (undirected, 6 vertices, 9 edges)</figcaption></figure>

Adjacency list:

Vertex List
A B -> C -> D -> E
B A -> D -> E
C A -> D
D A -> B -> C -> F
E A -> B -> F
F D -> E

Adjacency matrix (symmetric):

A B C D E F
A 0 1 1 1 1 0
B 1 0 0 1 1 0
C 1 0 0 1 0 0
D 1 1 1 0 0 1
E 1 1 0 0 0 1
F 0 0 0 1 1 0

Adjacency multilist (edges numbered e1-e9; Marked flag is 0 initially; "-" means no next edge):

Edge Marked V1 V2 Next edge of V1 Next edge of V2
e1 0 A B e2 e5
e2 0 A C e3 e7
e3 0 A D e4 e5
e4 0 A E - e6
e5 0 B D e6 e7
e6 0 B E - e9
e7 0 C D - e8
e8 0 D F - e9
e9 0 E F - -

Key points.

  1. In the matrix, entry $a_{ij}=1$ (or the weight) if an edge joins $i$ and $j$, else 0; an undirected graph gives a symmetric matrix.
  2. The matrix checks "is there an edge $(u,v)$" in $O(1)$ but needs $O(V^2)$ space even for a sparse graph.
  3. The list stores only the real neighbours of each vertex, so it needs $O(V+E)$ space and suits sparse graphs.
  4. Listing all neighbours of a vertex costs $O(V)$ in a matrix but only $O(\deg v)$ in a list.
  5. The multilist stores each undirected edge once and links it into both endpoint lists, which saves space and lets an edge be marked visited once.
  6. Use a matrix for dense graphs and edge queries; use a list for sparse graphs and traversals.

Answer frame. Open by defining a graph (vertices, edges, directed/undirected); draw the small example graph; show matrix, then list (then multilist if asked); close with the space/time comparison.

Asked: [7 marks] (Nov 2019) What do you understand about graph? How the graph represented in memory? Asked: [9 marks] (Dec 2023) For the given graph find: i) adjacency list ii) adjacency matrix iii) adjacency multilist representation Asked: [7 marks] (Dec 2025) Explain the Adjacency Matrix and Adjacency List representations of a graph.

Graph Traversal: Depth First Search (DFS)

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">High weight</span>

Definition. DFS visits a start vertex, then goes as deep as possible along one branch, and backtracks only when no unvisited neighbour remains; <mark>DFS uses a stack (or recursion) and runs in $O(V+E)$ with adjacency lists</mark>.

Algorithm.

Step 1: Mark all vertices unvisited; push the start vertex.
Step 2: Pop u; if u is unvisited, visit it and mark it.
Step 3: Push every unvisited neighbour of u.
Step 4: Repeat Step 2-3 until the stack is empty.

Recursive form: DFS(u): visited[u]=1; for each neighbour v of u: if !visited[v] then DFS(v).

Example (Nov 2022). Edges: 1-2, 1-3, 1-4, 2-5, 3-5, 4-6, 4-7, 5-8, 6-8, 7-8; start at 1, take neighbours in numerical order.

<figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u4-04" viewBox="0 0 398.2 389.6" width="398.2" height="389.6" role="img" aria-label="Graph of Nov 2022 (N1 to N8 are vertices 1 to 8)"><style>#dsfig-u4-04 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u4-04 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u4-04 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u4-04 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u4-04 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u4-04 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u4-04 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u4-04 .t{fill:#16181D;font-weight:500}#dsfig-u4-04 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u4-04 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u4-04 .dot{fill:#16181D}#dsfig-u4-04 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u4-04 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u4-04 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u4-04 .ah{fill:#454C5A}#dsfig-u4-04 .ah.hi{fill:#2340B8}#dsfig-u4-04 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u4-04 .wl .t{font-size:12px;font-weight:700}#dsfig-u4-04 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u4-04 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u4-04 .e{stroke:#B1B7C3}html.dark #dsfig-u4-04 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u4-04 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u4-04 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u4-04 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u4-04 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u4-04 .t{fill:#E6E8ED}html.dark #dsfig-u4-04 .t.inv{fill:#0F1115}html.dark #dsfig-u4-04 .kd{stroke:#E6E8ED}html.dark #dsfig-u4-04 .dot{fill:#E6E8ED}html.dark #dsfig-u4-04 .ann{fill:#8FA3FF}html.dark #dsfig-u4-04 .lbl{fill:#858D9C}html.dark #dsfig-u4-04 .ptr{fill:#8FA3FF}html.dark #dsfig-u4-04 .ah{fill:#B1B7C3}html.dark #dsfig-u4-04 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u4-04 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u4-04 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u4-04 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah23" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah" d="M0,1 L9,5 L0,9 z"/></marker><marker id="ahh23" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah hi" d="M0,1 L9,5 L0,9 z"/></marker></defs><path class="e" d="M154.2,51.9 L54.8,131.3"/><path class="e" d="M169,59 L169,124.2"/><path class="e" d="M183.8,51.9 L283.2,131.3"/><path class="e" d="M47.3,160.7 L75.7,228.9"/><path class="e" d="M156.8,157.8 L95.2,231.8"/><path class="e" d="M290.7,160.7 L262.3,228.9"/><path class="e" d="M307.6,159.6 L348.6,230"/><path class="e" d="M98.2,257.8 L205.4,338.2"/><path class="e" d="M249,264.4 L226.6,331.6"/><path class="e" d="M343,257.8 L235.8,338.2"/><circle class="n" cx="169" cy="40" r="18"/><text class="t" x="169" y="40" dy=".35em" text-anchor="middle">N1</text><circle class="n" cx="40" cy="143.2" r="18"/><text class="t" x="40" y="143.2" dy=".35em" text-anchor="middle">N2</text><circle class="n" cx="169" cy="143.2" r="18"/><text class="t" x="169" y="143.2" dy=".35em" text-anchor="middle">N3</text><circle class="n" cx="298" cy="143.2" r="18"/><text class="t" x="298" y="143.2" dy=".35em" text-anchor="middle">N4</text><circle class="n" cx="83" cy="246.4" r="18"/><text class="t" x="83" y="246.4" dy=".35em" text-anchor="middle">N5</text><circle class="n" cx="255" cy="246.4" r="18"/><text class="t" x="255" y="246.4" dy=".35em" text-anchor="middle">N6</text><circle class="n" cx="358.2" cy="246.4" r="18"/><text class="t" x="358.2" y="246.4" dy=".35em" text-anchor="middle">N7</text><circle class="n" cx="220.6" cy="349.6" r="18"/><text class="t" x="220.6" y="349.6" dy=".35em" text-anchor="middle">N8</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">Graph of Nov 2022 (N1 to N8 are vertices 1 to 8)</figcaption></figure>

Trace: 1, 2, 5, 3 (dead end, backtrack to 5), 8, 6, 4 (via 6), 7.

DFS order: 1, 2, 5, 3, 8, 6, 4, 7.

Key points.

  1. DFS explores one path fully before trying another, so the visited order depends on the neighbour order chosen.
  2. A visited array prevents infinite loops on cycles.
  3. Time is $O(V+E)$ with a list and $O(V^2)$ with a matrix; space is $O(V)$ for the stack and visited array.
  4. Applications are cycle detection, topological sort, connected components, path finding and maze solving.
  5. DFS does not give shortest paths in an unweighted graph.

Counting connected components.

Step 1: count = 0; mark all vertices unvisited.
Step 2: for each vertex v: if v is unvisited then count = count + 1 and DFS(v).
Step 3: return count.

Each DFS call from Step 2 marks one whole component, so the time is $O(V+E)$.

Answer frame. Open with the DFS definition; give the algorithm and the visited array; draw the graph and show the trace table with a stated neighbour order; close with complexity and applications. For "algorithms for DFS and BFS" write both algorithms together, then a two-line complexity note.

Asked: [7 marks] (Nov 2018, Dec 2024) Differentiate between Depth First Search (DFS) and Breadth First Search (BFS). (table under Comparison) Asked: [7 marks] (Dec 2023, Dec 2025) Write algorithms for DFS and BFS traversal on a graph. Asked: [7 marks] (Nov 2022) Solve BFS and DFS traversal of the given graph. Asked: [7 marks] (Dec 2025) Describe the DFS and BFS algorithms for graph traversal with examples. Asked: [7 marks] (Jun 2020) Write an algorithm which counts the number of connected components in a graph.

Breadth First Search (BFS)

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Medium weight</span>

Definition. BFS visits the start vertex, then all its neighbours, then their neighbours, level by level; <mark>BFS uses a FIFO queue and runs in $O(V+E)$</mark>.

Algorithm.

Step 1: Mark all vertices unvisited; mark the start visited and enqueue it.
Step 2: Dequeue u and visit it.
Step 3: Enqueue every unvisited neighbour of u and mark it visited.
Step 4: Repeat Step 2-3 until the queue is empty.

Example (graph of Nov 2022, start 1).

Queue: [1] -> dequeue 1, queue [2,3,4] -> dequeue 2, [3,4,5] -> dequeue 3, [4,5] -> dequeue 4, [5,6,7] -> dequeue 5, [6,7,8] -> dequeue 6, 7, 8.

BFS order: 1, 2, 3, 4, 5, 6, 7, 8.

Key points.

  1. BFS visits all vertices at distance $k$ from the start before any at distance $k+1$.
  2. Marking a vertex when it is enqueued, not when dequeued, stops duplicates in the queue.
  3. Time is $O(V+E)$ with a list and $O(V^2)$ with a matrix; space is $O(V)$ for the queue.
  4. In an unweighted graph BFS finds the shortest path (fewest edges) from the source.
  5. Applications are shortest path in unweighted graphs, level-order traversal, finding connected components and web crawling.

Comparison of DFS and BFS.

Basis DFS BFS
Data structure Stack or recursion Queue
Order Deep along a branch, then backtrack Level by level
Space $O(V)$, depth of the path $O(V)$, widest level
Time $O(V+E)$ $O(V+E)$
Shortest path Not guaranteed Yes, in unweighted graphs
Uses Cycle detection, topological sort Shortest path, level order
Example order (Nov 2022) 1,2,5,3,8,6,4,7 1,2,3,4,5,6,7,8

Answer frame. Open with the BFS definition; give the algorithm; draw the graph and the queue table; close with $O(V+E)$ and uses. For compare-and-contrast, open with one line defining each, give the 7-row table above, and close with one sentence on when to prefer each.

Asked: [7 marks] (Dec 2020) Explain Breadth First Search traversal of Graph using an example. Asked: [7 marks] (Jun 2023) Compare and contrast BFS and DFS.

Graph algorithm: Minimum Spanning Tree (MST) - Kruskal, Prim's algorithms

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">High weight</span>

Definition. A spanning tree of a connected graph is a subgraph that includes all $V$ vertices, is connected and has no cycle, so it has exactly $V-1$ edges; a minimum spanning tree (MST) is the spanning tree of a connected, weighted, undirected graph with the least total edge weight. <mark>Both Kruskal and Prim are greedy algorithms that always add the cheapest safe edge.</mark>

Key points.

  1. A connected graph can have many spanning trees; a spanning tree of $V$ vertices always has $V-1$ edges.
  2. Cut property: the cheapest edge crossing any cut of the vertices belongs to some MST, which is why greedy choice is correct.
  3. Kruskal works on edges: sort all edges by weight, then add each edge unless it makes a cycle, until $V-1$ edges are chosen.
  4. Cycle check in Kruskal uses union-find: an edge is rejected if both ends are already in the same set.
  5. Kruskal takes $O(E\log E)$ time (dominated by sorting) and suits sparse graphs.
  6. Prim works on vertices: start from any vertex and repeatedly add the cheapest edge joining the tree to a vertex outside it.
  7. Prim takes $O(V^2)$ with an adjacency matrix and $O(E\log V)$ with a min-heap, so it suits dense graphs.
  8. Applications: laying cables, pipelines or roads at least cost.

Kruskal algorithm.

Step 1: Sort all edges in non-decreasing order of weight.
Step 2: Put each vertex in its own set.
Step 3: Take the next edge (u,v); if find(u) != find(v), add it to the MST and union the sets; else reject it.
Step 4: Stop when V-1 edges are chosen.

Prim algorithm.

Step 1: Start with any vertex in the tree set T.
Step 2: Among edges with one end in T and one outside, pick the minimum weight edge.
Step 3: Add that edge and its outside vertex to T.
Step 4: Repeat Step 2-3 until T contains all V vertices.

Example: Kruskal (9 vertices, Nov 2019 / Nov 2022 / Jun 2023 / Jun 2024).

<figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u4-05" viewBox="0 0 510 295" width="510" height="295" role="img" aria-label="Weighted graph, vertices 0 to 8 (N0 to N8)"><style>#dsfig-u4-05 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u4-05 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u4-05 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u4-05 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u4-05 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u4-05 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u4-05 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u4-05 .t{fill:#16181D;font-weight:500}#dsfig-u4-05 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u4-05 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u4-05 .dot{fill:#16181D}#dsfig-u4-05 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u4-05 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u4-05 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u4-05 .ah{fill:#454C5A}#dsfig-u4-05 .ah.hi{fill:#2340B8}#dsfig-u4-05 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u4-05 .wl .t{font-size:12px;font-weight:700}#dsfig-u4-05 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u4-05 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u4-05 .e{stroke:#B1B7C3}html.dark #dsfig-u4-05 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u4-05 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u4-05 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u4-05 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u4-05 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u4-05 .t{fill:#E6E8ED}html.dark #dsfig-u4-05 .t.inv{fill:#0F1115}html.dark #dsfig-u4-05 .kd{stroke:#E6E8ED}html.dark #dsfig-u4-05 .dot{fill:#E6E8ED}html.dark #dsfig-u4-05 .ann{fill:#8FA3FF}html.dark #dsfig-u4-05 .lbl{fill:#858D9C}html.dark #dsfig-u4-05 .ptr{fill:#8FA3FF}html.dark #dsfig-u4-05 .ah{fill:#B1B7C3}html.dark #dsfig-u4-05 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u4-05 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u4-05 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u4-05 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah24" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah" d="M0,1 L9,5 L0,9 z"/></marker><marker id="ahh24" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah hi" d="M0,1 L9,5 L0,9 z"/></marker></defs><path class="e" d="M53.4,112.6 L112.6,53.4"/><path class="e" d="M53.4,139.4 L112.6,198.6"/><path class="e" d="M145,40 L236,40"/><path class="e" d="M126,59 L126,193"/><path class="e" d="M274,40 L365,40"/><path class="e" d="M255,59 L255,124.2"/><path class="e" d="M263.5,57 L332.5,195"/><path class="e" d="M397.4,53.4 L456.6,112.6"/><path class="e" d="M379.4,58.4 L345.6,193.6"/><path class="e" d="M454.2,136.5 L356.8,201.5"/><path class="e" d="M323,218 L230,249"/><path class="e" d="M195,246.5 L143,220.5"/><path class="e" d="M218.8,237.3 L248.2,160.9"/><path class="e" d="M142.8,203.1 L238.2,152.1"/><g class="wl"><rect x="73.4" y="74" width="19.2" height="18" rx="9"/><text class="t" x="83" y="83" dy=".35em" text-anchor="middle">4</text></g><g class="wl"><rect x="73.4" y="160" width="19.2" height="18" rx="9"/><text class="t" x="83" y="169" dy=".35em" text-anchor="middle">8</text></g><g class="wl"><rect x="180.9" y="31" width="19.2" height="18" rx="9"/><text class="t" x="190.5" y="40" dy=".35em" text-anchor="middle">8</text></g><g class="wl"><rect x="112.8" y="117" width="26.4" height="18" rx="9"/><text class="t" x="126" y="126" dy=".35em" text-anchor="middle">11</text></g><g class="wl"><rect x="309.9" y="31" width="19.2" height="18" rx="9"/><text class="t" x="319.5" y="40" dy=".35em" text-anchor="middle">7</text></g><g class="wl"><rect x="245.4" y="82.6" width="19.2" height="18" rx="9"/><text class="t" x="255" y="91.6" dy=".35em" text-anchor="middle">2</text></g><g class="wl"><rect x="288.4" y="117" width="19.2" height="18" rx="9"/><text class="t" x="298" y="126" dy=".35em" text-anchor="middle">4</text></g><g class="wl"><rect x="417.4" y="74" width="19.2" height="18" rx="9"/><text class="t" x="427" y="83" dy=".35em" text-anchor="middle">9</text></g><g class="wl"><rect x="349.3" y="117" width="26.4" height="18" rx="9"/><text class="t" x="362.5" y="126" dy=".35em" text-anchor="middle">14</text></g><g class="wl"><rect x="392.3" y="160" width="26.4" height="18" rx="9"/><text class="t" x="405.5" y="169" dy=".35em" text-anchor="middle">10</text></g><g class="wl"><rect x="266.9" y="224.5" width="19.2" height="18" rx="9"/><text class="t" x="276.5" y="233.5" dy=".35em" text-anchor="middle">2</text></g><g class="wl"><rect x="159.4" y="224.5" width="19.2" height="18" rx="9"/><text class="t" x="169" y="233.5" dy=".35em" text-anchor="middle">1</text></g><g class="wl"><rect x="223.9" y="190.1" width="19.2" height="18" rx="9"/><text class="t" x="233.5" y="199.1" dy=".35em" text-anchor="middle">6</text></g><g class="wl"><rect x="180.9" y="168.6" width="19.2" height="18" rx="9"/><text class="t" x="190.5" y="177.6" dy=".35em" text-anchor="middle">7</text></g><circle class="n" cx="40" cy="126" r="18"/><text class="t" x="40" y="126" dy=".35em" text-anchor="middle">N0</text><circle class="n" cx="126" cy="40" r="18"/><text class="t" x="126" y="40" dy=".35em" text-anchor="middle">N1</text><circle class="n" cx="255" cy="40" r="18"/><text class="t" x="255" y="40" dy=".35em" text-anchor="middle">N2</text><circle class="n" cx="384" cy="40" r="18"/><text class="t" x="384" y="40" dy=".35em" text-anchor="middle">N3</text><circle class="n" cx="470" cy="126" r="18"/><text class="t" x="470" y="126" dy=".35em" text-anchor="middle">N4</text><circle class="n" cx="341" cy="212" r="18"/><text class="t" x="341" y="212" dy=".35em" text-anchor="middle">N5</text><circle class="n" cx="212" cy="255" r="18"/><text class="t" x="212" y="255" dy=".35em" text-anchor="middle">N6</text><circle class="n" cx="126" cy="212" r="18"/><text class="t" x="126" y="212" dy=".35em" text-anchor="middle">N7</text><circle class="n" cx="255" cy="143.2" r="18"/><text class="t" x="255" y="143.2" dy=".35em" text-anchor="middle">N8</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">Weighted graph, vertices 0 to 8 (N0 to N8)</figcaption></figure>

Sorted edges in order: take 6-7 (1), 2-8 (2), 5-6 (2), 0-1 (4), 2-5 (4); reject 6-8 (6, cycle); take 2-3 (7); reject 7-8 (7, cycle); take 0-7 (8); reject 1-2 (8, cycle); take 3-4 (9); the rest (4-5, 1-7, 3-5) form cycles.

Eight edges = $V-1$, so stop. MST cost = 1+2+2+4+4+7+8+9 = 37.

Example: Prim (5 vertices, Nov 2022), edges (0,4)=4, (0,1)=8, (4,1)=6, (4,2)=5, (4,3)=7, (1,2)=3, (2,3)=9; start at 0.

Step Tree set Edge added Weight
1 {0} 0-4 4
2 {0,4} 4-2 5
3 {0,4,2} 2-1 3
4 {0,4,2,1} 4-3 7

MST cost = 4+5+3+7 = 19. (Kruskal on the same graph picks 1-2 (3), 0-4 (4), 4-2 (5), rejects 4-1 (6), takes 4-3 (7): also 19.)

Answer frame. Open with the definition of a spanning tree and MST; draw the given graph and, at the end, the MST; state the algorithm steps, then the edge table; close with the total cost and the complexity. For a "spanning tree in detail" question add the $V-1$ edge property, an example with two different spanning trees, and applications.

Pitfall: Kruskal's algorithm finds a minimum spanning tree, not a shortest path between two vertices, even though one paper words it that way.

Asked: [7 marks] (Nov 2019, Nov 2022, Jun 2023, Jun 2024) Explain/discuss Kruskal's algorithm with a suitable example graph. Asked: [7 marks] (Nov 2018, Dec 2023) Explain Prim's algorithm for minimum spanning tree with example. Asked: [7 marks] (Nov 2022) Discuss Prim's algorithm with the given graph. Asked: [7 marks] (Dec 2024, Dec 2025) Define minimum spanning tree. Write down Prim's algorithm to find MST. Asked: [7 marks] (Dec 2025) What is a Minimum Spanning Tree? Explain Kruskal's or Prim's algorithm. Asked: [7 marks] (Dec 2020) What is Spanning Trees? Explain Spanning Tree in detail with example. Asked: [7 marks] (Jun 2020) Explain briefly: i) Minimum Spanning Tree ii) Applications of a graph

Dijkstra's shortest path algorithm

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Medium weight</span>

Definition. Dijkstra's algorithm finds the shortest path from one source vertex to all other vertices in a graph with non-negative edge weights by repeatedly fixing the nearest unfixed vertex; ==the relaxation rule is $dist[v]=\min(dist[v],\,dist[u]+w(u,v))$==.

Algorithm.

Step 1: dist[source]=0, dist[all others]=infinity; no vertex is visited.
Step 2: Pick the unvisited vertex u with the smallest dist and mark it visited.
Step 3: For each neighbour v of u: if dist[u]+w(u,v) < dist[v], set dist[v] to it and parent[v]=u.
Step 4: Repeat Step 2-3 until all vertices are visited.

Example (Nov 2018), source a, edges a-b 3, a-c 4, b-c 7, b-d 6, c-d 5, c-e 8, d-e 3, d-f 4, e-f 7.

<figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u4-06" viewBox="0 0 467 252" width="467" height="252" role="img" aria-label="Weighted graph of Nov 2018, source a"><style>#dsfig-u4-06 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u4-06 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u4-06 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u4-06 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u4-06 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u4-06 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u4-06 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u4-06 .t{fill:#16181D;font-weight:500}#dsfig-u4-06 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u4-06 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u4-06 .dot{fill:#16181D}#dsfig-u4-06 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u4-06 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u4-06 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u4-06 .ah{fill:#454C5A}#dsfig-u4-06 .ah.hi{fill:#2340B8}#dsfig-u4-06 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u4-06 .wl .t{font-size:12px;font-weight:700}#dsfig-u4-06 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u4-06 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u4-06 .e{stroke:#B1B7C3}html.dark #dsfig-u4-06 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u4-06 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u4-06 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u4-06 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u4-06 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u4-06 .t{fill:#E6E8ED}html.dark #dsfig-u4-06 .t.inv{fill:#0F1115}html.dark #dsfig-u4-06 .kd{stroke:#E6E8ED}html.dark #dsfig-u4-06 .dot{fill:#E6E8ED}html.dark #dsfig-u4-06 .ann{fill:#8FA3FF}html.dark #dsfig-u4-06 .lbl{fill:#858D9C}html.dark #dsfig-u4-06 .ptr{fill:#8FA3FF}html.dark #dsfig-u4-06 .ah{fill:#B1B7C3}html.dark #dsfig-u4-06 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u4-06 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u4-06 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u4-06 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah25" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah" d="M0,1 L9,5 L0,9 z"/></marker><marker id="ahh25" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah hi" d="M0,1 L9,5 L0,9 z"/></marker></defs><path class="e" d="M55.8,115.5 L153.2,50.5"/><path class="e" d="M55.8,136.5 L153.2,201.5"/><path class="e" d="M169,59 L169,193"/><path class="e" d="M184.8,50.5 L282.2,115.5"/><path class="e" d="M184.8,201.5 L282.2,136.5"/><path class="e" d="M188,212 L408,212"/><path class="e" d="M313.8,136.5 L411.2,201.5"/><path class="e" d="M313.8,115.5 L411.2,50.5"/><path class="e" d="M427,193 L427,59"/><g class="wl"><rect x="94.9" y="74" width="19.2" height="18" rx="9"/><text class="t" x="104.5" y="83" dy=".35em" text-anchor="middle">3</text></g><g class="wl"><rect x="94.9" y="160" width="19.2" height="18" rx="9"/><text class="t" x="104.5" y="169" dy=".35em" text-anchor="middle">4</text></g><g class="wl"><rect x="159.4" y="117" width="19.2" height="18" rx="9"/><text class="t" x="169" y="126" dy=".35em" text-anchor="middle">7</text></g><g class="wl"><rect x="223.9" y="74" width="19.2" height="18" rx="9"/><text class="t" x="233.5" y="83" dy=".35em" text-anchor="middle">6</text></g><g class="wl"><rect x="223.9" y="160" width="19.2" height="18" rx="9"/><text class="t" x="233.5" y="169" dy=".35em" text-anchor="middle">5</text></g><g class="wl"><rect x="288.4" y="203" width="19.2" height="18" rx="9"/><text class="t" x="298" y="212" dy=".35em" text-anchor="middle">8</text></g><g class="wl"><rect x="352.9" y="160" width="19.2" height="18" rx="9"/><text class="t" x="362.5" y="169" dy=".35em" text-anchor="middle">3</text></g><g class="wl"><rect x="352.9" y="74" width="19.2" height="18" rx="9"/><text class="t" x="362.5" y="83" dy=".35em" text-anchor="middle">4</text></g><g class="wl"><rect x="417.4" y="117" width="19.2" height="18" rx="9"/><text class="t" x="427" y="126" dy=".35em" text-anchor="middle">7</text></g><circle class="n" cx="40" cy="126" r="18"/><text class="t" x="40" y="126" dy=".35em" text-anchor="middle">a</text><circle class="n" cx="169" cy="40" r="18"/><text class="t" x="169" y="40" dy=".35em" text-anchor="middle">b</text><circle class="n" cx="169" cy="212" r="18"/><text class="t" x="169" y="212" dy=".35em" text-anchor="middle">c</text><circle class="n" cx="298" cy="126" r="18"/><text class="t" x="298" y="126" dy=".35em" text-anchor="middle">d</text><circle class="n" cx="427" cy="212" r="18"/><text class="t" x="427" y="212" dy=".35em" text-anchor="middle">e</text><circle class="n" cx="427" cy="40" r="18"/><text class="t" x="427" y="40" dy=".35em" text-anchor="middle">f</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">Weighted graph of Nov 2018, source a</figcaption></figure>

Fixed b c d e f
a (0) 3 4 inf inf inf
b (3) 3 4 9 inf inf
c (4) 3 4 9 12 inf
d (9) 3 4 9 12 13

The last two rows (e fixed at 12, f at 13) change nothing.

Path to f: f came from d, d from b, b from a. Shortest path a-b-d-f, distance 13 (a-c-d-f also costs 13).

Key points.

  1. Dijkstra is greedy: the unvisited vertex with the least distance is final because no negative edge can shorten it later.
  2. It fails with negative edge weights, where Bellman-Ford must be used.
  3. Time is $O(V^2)$ with an array and $O((V+E)\log V)$ with a min-heap.
  4. The parent array rebuilds the actual path by walking back from the target.
  5. Applications are GPS routing and network routing protocols such as OSPF.

Answer frame. Open with the problem and the relaxation formula; draw the graph; give the algorithm, then the distance table with one row per fixed vertex; close with the path, its length and the complexity.

Asked: [7 marks] (Nov 2018) Find shortest path for $a$ to $f$ using Dijkstra's algorithm. Asked: [7 marks] (Jun 2020) Explain Dijkstra's algorithm for finding shortest path with an example.

Comparison between different graph algorithms

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Low weight</span>

Definition. Graph algorithms differ in the problem they solve, the data structure they use and their running time.

Key points.

  1. DFS goes deep with a stack, BFS goes level by level with a queue; both cost $O(V+E)$ with lists (table in the BFS topic).
  2. BFS gives shortest paths only for unweighted graphs; Dijkstra handles non-negative weights in $O((V+E)\log V)$.
  3. Kruskal ($O(E\log E)$) picks edges globally and suits sparse graphs; Prim ($O(V^2)$ or $O(E\log V)$) grows one tree and suits dense graphs.

Asked: [7 marks] (Jun 2020) Differentiate between Depth first search and Breadth first search algorithm?

Application of graphs

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Not asked since 2022</span>

Definition. Graphs model any set of objects with connections between them, so they appear wherever relationships, routes or dependencies must be stored and searched.

Key points.

  1. Networks and maps: cities as vertices and roads as weighted edges give shortest routes (Dijkstra) and cheapest cabling (MST).
  2. Social networks: people are vertices and friendships are edges; BFS finds friends at a given distance.
  3. Scheduling: a DAG of tasks with dependencies is ordered by topological sort.
  4. Other uses are web page links, circuit design and compilers.

Asked: [7 marks] (Jun 2020) Explain briefly: ii) Applications of a graph (asked together with MST)

Last-minute revision

  • A graph is $G=(V,E)$; in an undirected graph $\sum\deg(v)=2E$.
  • Degree in a digraph = indegree + outdegree; a DAG is a directed graph with no directed cycle.
  • Adjacency matrix: $O(V^2)$ space, edge test $O(1)$; adjacency list: $O(V+E)$ space.
  • Multilist: one record per edge with Marked, V1, V2 and two next-edge fields.
  • DFS uses a stack, BFS uses a queue; both are $O(V+E)$ with lists.
  • Nov 2022 graph: BFS 1,2,3,4,5,6,7,8 and DFS 1,2,5,3,8,6,4,7.
  • Connected components = number of fresh DFS/BFS starts from unvisited vertices.
  • A spanning tree has $V-1$ edges, is connected and is acyclic.
  • Kruskal: sort edges, union-find, $O(E\log E)$; 9-vertex graph MST = 37.
  • Prim: grow from a vertex, $O(V^2)$ or $O(E\log V)$; 5-vertex graph MST = 19.
  • Dijkstra: $dist[v]=\min(dist[v],dist[u]+w)$, non-negative weights; Nov 2018 a to f = 13 via a-b-d-f.

Memory hooks

  • DFS = Deep, Stack; BFS = Broad, Queue.
  • Kruskal = sort Knives (edges) and skip cycles; Prim = Plant one tree and grow it.
  • MST edges = $V-1$; "one less than the vertices".
  • Dijkstra = "closest first, then relax".
  • Matrix for Many edges (dense), List for Less (sparse).

Coverage checklist

  • Graphs: Introduction — definition and basic terms (no past questions).
  • Classification of graph: Directed and Undirected graphs — Nov 2019 short notes (DAG, tournament tree, operations); Dec 2020 directed, undirected, degree, acyclic.
  • Representation — Nov 2019 graph and memory; Dec 2023 list, matrix, multilist; Dec 2025 matrix and list.
  • Graph Traversal: Depth First Search (DFS) — Nov 2018/Dec 2024 DFS vs BFS; Dec 2023/Dec 2025 algorithms; Nov 2022 traversal; Dec 2025 describe DFS and BFS; Jun 2020 connected components.
  • Breadth First Search (BFS) — Dec 2020 BFS with example; Jun 2023 BFS vs DFS.
  • Graph algorithm: Minimum Spanning Tree (MST)- Kruskal, Prim’s algorithms — Kruskal (four sessions); Prim (Nov 2018, Dec 2023, Nov 2022, Dec 2024, Dec 2025); MST definition Dec 2025; Dec 2020 spanning trees; Jun 2020 MST and applications.
  • Dijkstra’s shortest path algorithm — Nov 2018 a to f; Jun 2020 algorithm with example.
  • Comparison between different graph algorithms — Jun 2020 DFS vs BFS.
  • Application of graphs — Jun 2020 applications (with MST).
Go to where you left off?

Quick Add to Notes

Save questions, your own notes and screenshots into notes filed by unit. It takes a free account.

Create free account

Have an account? Log in