Data Structures (AD-303) - Unit 4 Short Notes

How unit 4 is examined

Graphs: representation, BFS/DFS, MST (Kruskal, Prim) and Dijkstra; MST carries the most marks.

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$ joined by a set of edges $E$, where each edge connects a pair of vertices.==

Key points.

1. A path is a sequence of vertices joined by edges, and a cycle is a path that returns to its starting vertex.
2. A graph is connected if a path exists between every pair of vertices.
3. The degree of a vertex is the number of edges touching it; a directed graph has in-degree and out-degree.
4. A tree is a connected graph with no cycle, so it has exactly $V-1$ edges.

Classification of graph: directed and undirected

<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. <mark>In an undirected graph edges are unordered pairs $\{u,v\}$; in a directed graph (digraph) edges are ordered pairs $(u,v)$ drawn as arrows.</mark>

Key points.

1. A weighted graph attaches a cost to each edge; an unweighted graph does not.
2. A simple graph has no self-loops or parallel edges; a multigraph allows parallel edges.
3. A complete graph has an edge between every pair, so $E=V(V-1)/2$ when undirected.
4. A DAG is a directed acyclic graph; a sparse graph has $E\approx V$ and a dense graph has $E\approx V^2$.

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. <mark>A graph is stored either as a $V\times V$ adjacency matrix or as an adjacency list, an array of $V$ linked lists holding each vertex's neighbours.</mark>

Key points.

1. In the matrix, $A[i][j]=1$ if there is an edge from $i$ to $j$, otherwise 0; for a weighted graph it stores the weight.
2. The matrix of an undirected graph is symmetric, but that of a directed graph generally is not.
3. The matrix needs $O(V^2)$ space and tests whether an edge exists in $O(1)$.
4. The list needs $O(V+E)$ space and lists all neighbours of a vertex in time proportional to its degree.
5. In an undirected graph each edge appears in both endpoints' lists, so the lists hold $2E$ entries; testing an edge costs $O(\deg(u))$.
6. Use the matrix for dense graphs and the list for sparse graphs.
7. To draw a graph from a matrix, read row by row and draw an arrow $V_i\to V_j$ for every 1.

Example. The matrix in the paper has six 1s, giving edges $V_0\to V_1, V_0\to V_2, V_1\to V_2, V_1\to V_3, V_2\to V_3, V_3\to V_0$.

<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 338" width="338" height="338" role="img" aria-label="Directed graph of the given adjacency matrix"><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="ah45" 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="ahh45" 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="M59,40 L277,40" marker-end="url(#ah45)"/><path class="e" d="M40,59 L40,277" marker-end="url(#ah45)"/><path class="e" d="M284.6,53.4 L54.8,283.2" marker-end="url(#ah45)"/><path class="e" d="M298,59 L298,277" marker-end="url(#ah45)"/><path class="e" d="M59,298 L277,298" marker-end="url(#ah45)"/><path class="e" d="M284.6,284.6 L54.8,54.8" marker-end="url(#ah45)"/><circle class="n" cx="40" cy="40" r="18"/><text class="t" x="40" y="40" dy=".35em" text-anchor="middle">V0</text><circle class="n" cx="298" cy="40" r="18"/><text class="t" x="298" y="40" dy=".35em" text-anchor="middle">V1</text><circle class="n" cx="40" cy="298" r="18"/><text class="t" x="40" y="298" dy=".35em" text-anchor="middle">V2</text><circle class="n" cx="298" cy="298" r="18"/><text class="t" x="298" y="298" dy=".35em" text-anchor="middle">V3</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">Directed graph of the given adjacency matrix</figcaption></figure>

Adjacency list of the same graph:

V0 -> V1 -> V2
V1 -> V2 -> V3
V2 -> V3
V3 -> V0

Answer frame. Define both; for the drawing question list the six edges row by row, then draw the arrows; for the explain question draw a small graph with its matrix and list and compare space and edge lookup; close with dense versus sparse.

Asked: [7 marks] (Nov 2022, Jun 2024) Draw the directed graph that corresponds to the given adjacency matrix ($V_0$ to $V_3$). 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">Medium weight</span>

Definition. <mark>Graph traversal visits every reachable vertex exactly once; DFS goes as deep as possible along a branch before backtracking, using a stack or recursion.</mark>

Key points.

1. A visited array stops revisiting, which would loop forever on a cycle.
2. Recursive DFS marks the vertex, visits each unvisited neighbour in order, and backtracks when none remain.
3. Iterative DFS pops a vertex, skips it if visited, else visits it and pushes unvisited neighbours in reverse order.
4. BFS visits level by level using a FIFO queue.
5. Both take $O(V+E)$ time with an adjacency list and $O(V^2)$ with a matrix.
6. Recursive DFS needs $O(V)$ stack; the iterative stack can reach $O(E)$ entries; the BFS queue is $O(V)$.

Example. Graph with edges A-B, A-C, B-D, B-E, C-F, D-E, neighbours taken alphabetically, start A.

<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 338" width="338" height="338" role="img" aria-label="Example graph for BFS and DFS"><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="ah46" 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="ahh46" 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,158.5 L153.2,93.5"/><path class="e" d="M55.8,179.5 L153.2,244.5"/><path class="e" d="M187,77 L280,46"/><path class="e" d="M184.8,93.5 L282.2,158.5"/><path class="e" d="M187,261 L280,292"/><path class="e" d="M298,59 L298,150"/><circle class="n" cx="40" cy="169" r="18"/><text class="t" x="40" y="169" dy=".35em" text-anchor="middle">A</text><circle class="n" cx="169" cy="83" r="18"/><text class="t" x="169" y="83" dy=".35em" text-anchor="middle">B</text><circle class="n" cx="169" cy="255" r="18"/><text class="t" x="169" y="255" dy=".35em" text-anchor="middle">C</text><circle class="n" cx="298" cy="40" r="18"/><text class="t" x="298" y="40" dy=".35em" text-anchor="middle">D</text><circle class="n" cx="298" cy="169" r="18"/><text class="t" x="298" y="169" dy=".35em" text-anchor="middle">E</text><circle class="n" cx="298" cy="298" r="18"/><text class="t" x="298" y="298" dy=".35em" text-anchor="middle">F</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">Example graph for BFS and DFS</figcaption></figure>

DFS order: A B D E C F. BFS order: A B C D E F.

Pitfall: Pushing neighbours alphabetically pops the largest first and gives A C F B E D; push in reverse order to match recursion.

DFS(v): Step 1: visited[v] = true; print v.
Step 2: for each neighbour w of v in order: if not visited[w], DFS(w).
BFS(s): Step 1: visited[s] = true; enqueue s.
Step 2: while queue not empty: v = dequeue; print v;
Step 3: for each unvisited neighbour w of v: mark w visited, enqueue w.

Answer frame. Define traversal; draw the graph; write DFS and BFS algorithms, then the trace table; close with $O(V+E)$ time.

Asked: [7 marks] (Dec 2023, Dec 2025) Explain in detail about the graph traversal techniques with suitable example. Asked: [7 marks] (Dec 2025) Describe the DFS and BFS algorithms for graph traversal with examples.

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">Low weight</span>

Definition. <mark>BFS visits all vertices at distance $k$ from the source before any at distance $k+1$, using a FIFO queue and a visited array.</mark>

Key points.

1. Enqueue and mark the source; repeatedly dequeue a vertex and mark and enqueue its unvisited neighbours.
2. On the example above the queue goes [B C], [C D E], [D E F], [E F], [F], [ ], giving A B C D E F.
3. Time is $O(V+E)$ and space is $O(V)$ for the queue and visited array.
4. In an unweighted graph BFS finds the shortest path in number of edges.

Asked: [7 marks] (Dec 2024) Explain Breadth First Search algorithm with example.

Minimum Spanning Tree: Kruskal and Prim

<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. <mark>A spanning tree of a connected graph is a subgraph containing all $V$ vertices and exactly $V-1$ edges with no cycle; a minimum spanning tree (MST) is the spanning tree with the smallest total edge weight.</mark>

Key points.

1. A spanning tree exists only if the graph is connected; there can be many, found by DFS or BFS, but only the MST is judged by weight.
2. If all edge weights are distinct the MST is unique; equal weights can give several MSTs of the same cost.
3. Kruskal's algorithm is edge based: it sorts all edges and adds the cheapest edge that does not form a cycle, so the partial result is a forest.
4. Kruskal checks cycles with union-find (disjoint sets) and takes $O(E\log E)=O(E\log V)$, suiting sparse graphs.
5. Prim's algorithm is vertex based: it grows one tree from a start vertex by repeatedly adding the cheapest edge leaving the tree, so the partial result is always connected.
6. Prim uses a min-heap and takes $O(E\log V)$, or $O(V^2)$ with a matrix, suiting dense graphs.
7. Both are greedy and correct by the cut property: the lightest edge crossing any cut (split of $V$ into two parts) belongs to some MST.
8. Cycle property: a strictly (uniquely) heaviest edge on any cycle is in no MST, which is why Kruskal may reject it.

Kruskal: Step 1: sort all edges by weight.
Step 2: make each vertex its own set.
Step 3: take the next edge (u,v); if find(u) != find(v), add it and union the sets.
Step 4: stop when V-1 edges are chosen.
Prim: Step 1: start with any vertex in the tree.
Step 2: pick the minimum-weight edge joining a tree vertex to a non-tree vertex.
Step 3: add it; repeat until all V vertices are in the tree.

Example (Dec 2023). Hexagon A-F with centre G. Edges: AB 23, BC 20, CD 15, DE 3, EF 17, FA 28, AG 38, BG 1, CG 4, DG 9, EG 18, FG 25.

Adjacency list:

A -> B(23) F(28) G(38)
B -> A(23) C(20) G(1)
C -> B(20) D(15) G(4)
D -> C(15) E(3) G(9)
E -> D(3) F(17) G(18)
F -> E(17) A(28) G(25)
G -> A(38) B(1) C(4) D(9) E(18) F(25)

Sorted edges: BG 1, DE 3, CG 4, DG 9, CD 15, EF 17, EG 18, BC 20, AB 23, FG 25, FA 28, AG 38.

<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 596 424" width="596" height="424" role="img" aria-label="MST from Kruskal, 6 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="ah47" 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="ahh47" 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,50.5 L153.2,115.5"/><path class="e" d="M184.8,136.5 L282.2,201.5"/><path class="e" d="M313.8,201.5 L411.2,136.5"/><path class="e" d="M317,212 L537,212"/><path class="e" d="M542.6,225.4 L440.4,327.6"/><path class="e" d="M409,347 L316,378"/><g class="wl"><rect x="91.3" y="74" width="26.4" height="18" rx="9"/><text class="t" x="104.5" y="83" dy=".35em" text-anchor="middle">23</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">1</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">4</text></g><g class="wl"><rect x="417.4" y="203" width="19.2" height="18" rx="9"/><text class="t" x="427" y="212" dy=".35em" text-anchor="middle">9</text></g><g class="wl"><rect x="481.9" y="267.5" width="19.2" height="18" rx="9"/><text class="t" x="491.5" y="276.5" dy=".35em" text-anchor="middle">3</text></g><g class="wl"><rect x="349.3" y="353.5" width="26.4" height="18" rx="9"/><text class="t" x="362.5" y="362.5" dy=".35em" text-anchor="middle">17</text></g><circle class="n" cx="40" cy="40" r="18"/><text class="t" x="40" y="40" dy=".35em" text-anchor="middle">A</text><circle class="n" cx="169" cy="126" r="18"/><text class="t" x="169" y="126" dy=".35em" text-anchor="middle">B</text><circle class="n" cx="298" cy="212" r="18"/><text class="t" x="298" y="212" dy=".35em" text-anchor="middle">G</text><circle class="n" cx="427" cy="126" r="18"/><text class="t" x="427" y="126" dy=".35em" text-anchor="middle">C</text><circle class="n" cx="556" cy="212" r="18"/><text class="t" x="556" y="212" dy=".35em" text-anchor="middle">D</text><circle class="n" cx="427" cy="341" r="18"/><text class="t" x="427" y="341" dy=".35em" text-anchor="middle">E</text><circle class="n" cx="298" cy="384" r="18"/><text class="t" x="298" y="384" dy=".35em" text-anchor="middle">F</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">MST from Kruskal, 6 edges</figcaption></figure>

Total cost = 1 + 3 + 4 + 9 + 17 + 23 = 57.

A non-minimum spanning tree of the same graph: AB, BC, CD, DE, EF, AG = 23 + 20 + 15 + 3 + 17 + 38 = 116, against the MST's 57.

Comparison.

Prim vs Kruskal. An MST is a spanning tree of a connected weighted graph: it has $V-1$ edges, no cycle and the minimum total weight; both algorithms below build one.

Negative weights (Nov 2022). The cheapest connecting subgraph may contain cycles, since a negative edge always lowers the total. Adapted Kruskal:

Step 1: Add every negative-weight edge to T (ignoring cycles).
Step 2: Treat each connected component formed so far as one set.
Step 3: Sort the remaining non-negative edges by weight.
Step 4: Add an edge only if it joins two different components.
Step 5: Stop when the graph is connected; T is the answer.

Why it works. Every negative edge lowers the total, so an optimal T has all of them; contracting each component leaves an ordinary MST problem. Time is $O(E\log E)$.

Example. P-Q $-2$, Q-R $-1$, P-R $-3$, R-S 4, Q-S 5, P-S 6. Step 1 takes all three negative edges (cost $-6$), leaving components {P,Q,R} and {S}; R-S 4 joins them; Q-S, P-S are rejected. T = {PQ, QR, PR, RS}, cost $-6+4=-2$, which contains a cycle and is not a tree. The cheapest plain spanning tree is PR, PQ, RS = $-3-2+4=$ $-1$, so the subset (−2) beats every tree (−1).

Answer frame. Algorithm question: define MST, Kruskal steps, graph, edge table, MST drawing and cost. Comparison: MST definition, table, when to use each. Negative weights: the cycle reason, five steps, why it works, example. Spanning tree vs MST: the 116 tree beside the 57 MST, cut and cycle properties.

Asked: [7 marks] (Nov 2022) Compare and Contrast the Spanning tree and Minimum Spanning Tree. Asked: [7 marks] (Jun 2024) Compare and Contrast the Spanning tree and Minimum Spanning Tree. Asked: [7 marks] (Nov 2022) Adapt Kruskal's or Prim's algorithm to a graph that may include negative weights, where the minimum connecting subset need not be a tree. Asked: [7 marks] (Dec 2023) For the given 7-vertex undirected graph, find the adjacency list and a minimum cost spanning tree by Kruskal's algorithm. Asked: [7 marks] (Dec 2024) Compare Prim's algorithm with Kruskal's algorithm for finding minimum spanning trees. Asked: [7 marks] (Dec 2025) What is a Minimum Spanning Tree (MST)? Explain Kruskal's or Prim's algorithm to find the MST of a weighted 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. <mark>Dijkstra's algorithm is a greedy single-source shortest-path algorithm for weighted graphs with non-negative edge weights.</mark>

Key points.

1. Set $d[s]=0$ and $d[v]=\infty$ for all other vertices, keep a visited set and a predecessor array.
2. Repeatedly pick the unvisited vertex $u$ with the smallest $d[u]$ and mark it final.
3. Relax each edge $(u,v)$: if $d[v] > d[u] + w(u,v)$, set $d[v]=d[u]+w(u,v)$ and $pred[v]=u$.
4. It fails with negative edges because a finalised vertex could later be improved: in the directed graph s→a 4, s→b 5, b→a $-3$ it fixes a = 4, but the true distance is 2.
5. Time is $O(V^2)$ with an array and $O((V+E)\log V)$ with a min-heap.

Example. Edges: A-B 4, A-C 2, B-C 1, B-D 5, C-D 8, C-E 10, D-E 2, D-F 6, E-F 3; source A.

<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 596 338" width="596" height="338" role="img" aria-label="Weighted graph for Dijkstra, source A"><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="ah48" 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="ahh48" 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.2,157.6 L196.8,51.4"/><path class="e" d="M55.2,180.4 L196.8,286.6"/><path class="e" d="M212,59 L212,279"/><path class="e" d="M231,40 L365,40"/><path class="e" d="M222.5,282.2 L373.5,55.8"/><path class="e" d="M231,298 L365,298"/><path class="e" d="M384,59 L384,279"/><path class="e" d="M399.2,51.4 L540.8,157.6"/><path class="e" d="M399.2,286.6 L540.8,180.4"/><g class="wl"><rect x="116.4" y="95.5" width="19.2" height="18" rx="9"/><text class="t" x="126" y="104.5" dy=".35em" text-anchor="middle">4</text></g><g class="wl"><rect x="116.4" y="224.5" width="19.2" height="18" rx="9"/><text class="t" x="126" y="233.5" dy=".35em" text-anchor="middle">2</text></g><g class="wl"><rect x="202.4" y="160" width="19.2" height="18" rx="9"/><text class="t" x="212" y="169" dy=".35em" text-anchor="middle">1</text></g><g class="wl"><rect x="288.4" y="31" width="19.2" height="18" rx="9"/><text class="t" x="298" y="40" dy=".35em" text-anchor="middle">5</text></g><g class="wl"><rect x="288.4" y="160" width="19.2" height="18" rx="9"/><text class="t" x="298" y="169" dy=".35em" text-anchor="middle">8</text></g><g class="wl"><rect x="284.8" y="289" width="26.4" height="18" rx="9"/><text class="t" x="298" y="298" dy=".35em" text-anchor="middle">10</text></g><g class="wl"><rect x="374.4" y="160" width="19.2" height="18" rx="9"/><text class="t" x="384" y="169" dy=".35em" text-anchor="middle">2</text></g><g class="wl"><rect x="460.4" y="95.5" width="19.2" height="18" rx="9"/><text class="t" x="470" y="104.5" dy=".35em" text-anchor="middle">6</text></g><g class="wl"><rect x="460.4" y="224.5" width="19.2" height="18" rx="9"/><text class="t" x="470" y="233.5" dy=".35em" text-anchor="middle">3</text></g><circle class="n" cx="40" cy="169" r="18"/><text class="t" x="40" y="169" dy=".35em" text-anchor="middle">A</text><circle class="n" cx="212" cy="40" r="18"/><text class="t" x="212" y="40" dy=".35em" text-anchor="middle">B</text><circle class="n" cx="212" cy="298" r="18"/><text class="t" x="212" y="298" dy=".35em" text-anchor="middle">C</text><circle class="n" cx="384" cy="40" r="18"/><text class="t" x="384" y="40" dy=".35em" text-anchor="middle">D</text><circle class="n" cx="384" cy="298" r="18"/><text class="t" x="384" y="298" dy=".35em" text-anchor="middle">E</text><circle class="n" cx="556" cy="169" r="18"/><text class="t" x="556" y="169" dy=".35em" text-anchor="middle">F</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">Weighted graph for Dijkstra, source A</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-05" viewBox="0 0 596 338" width="596" height="338" role="img" aria-label="Shortest path tree from A, read from the pred row"><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="ah49" 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="ahh49" 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.2,180.4 L196.8,286.6"/><path class="e" d="M212,279 L212,59"/><path class="e" d="M231,40 L365,40"/><path class="e" d="M384,59 L384,279"/><path class="e" d="M399.2,286.6 L540.8,180.4"/><g class="wl"><rect x="116.4" y="224.5" width="19.2" height="18" rx="9"/><text class="t" x="126" y="233.5" dy=".35em" text-anchor="middle">2</text></g><g class="wl"><rect x="202.4" y="160" width="19.2" height="18" rx="9"/><text class="t" x="212" y="169" dy=".35em" text-anchor="middle">1</text></g><g class="wl"><rect x="288.4" y="31" width="19.2" height="18" rx="9"/><text class="t" x="298" y="40" dy=".35em" text-anchor="middle">5</text></g><g class="wl"><rect x="374.4" y="160" width="19.2" height="18" rx="9"/><text class="t" x="384" y="169" dy=".35em" text-anchor="middle">2</text></g><g class="wl"><rect x="460.4" y="224.5" width="19.2" height="18" rx="9"/><text class="t" x="470" y="233.5" dy=".35em" text-anchor="middle">3</text></g><circle class="n" cx="40" cy="169" r="18"/><text class="t" x="40" y="169" dy=".35em" text-anchor="middle">A</text><circle class="n" cx="212" cy="40" r="18"/><text class="t" x="212" y="40" dy=".35em" text-anchor="middle">B</text><circle class="n" cx="212" cy="298" r="18"/><text class="t" x="212" y="298" dy=".35em" text-anchor="middle">C</text><circle class="n" cx="384" cy="40" r="18"/><text class="t" x="384" y="40" dy=".35em" text-anchor="middle">D</text><circle class="n" cx="384" cy="298" r="18"/><text class="t" x="384" y="298" dy=".35em" text-anchor="middle">E</text><circle class="n" cx="556" cy="169" r="18"/><text class="t" x="556" y="169" dy=".35em" text-anchor="middle">F</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">Shortest path tree from A, read from the pred row</figcaption></figure>

Shortest distances from A: C = 2, B = 3, D = 8, E = 10, F = 13 (path A-C-B-D-E-F, read back through pred).

Longest path in a DAG (Nov 2022).

1. Store the graph as a weighted adjacency list, with arrays $dist$ and $pred$ and a stack or queue for the topological sort.
2. Topologically sort: push each vertex on a stack when its DFS finishes, then pop; or Kahn's method, repeatedly removing an in-degree 0 vertex.
3. Set $dist[s]=0$ and all others $-\infty$; in topological order relax each edge $(u,v)$: if $dist[v]<dist[u]+w$, set $dist[v]=dist[u]+w$ and $pred[v]=u$; follow $pred$ back from $t$.
4. Topological order handles every predecessor of $u$ first, so $dist[u]$ is final before its edges are relaxed. Time is $O(V+E)$.

Example. s-a 3, s-b 2, a-b 4, a-t 2, b-t 5; order s, a, b, t gives $dist$: a = 3, b = max(2, 7) = 7, t = max(5, 12) = 12. Longest path s-a-b-t = 12.

Bellman-Ford (Nov 2022).

Step 1: d[s] = 0; d[v] = inf for every other v.
Step 2: repeat V-1 times: for every edge (u,v,w): if d[u] + w < d[v], set d[v] = d[u] + w.
Step 3: for every edge: if d[u] + w < d[v] still, report a negative cycle.

1. Time is $O(VE)$: $V-1$ passes over $E$ edges.
2. Upper-bound property: $d[v]$ is always the length of some real path or $\infty$, so it never drops below the true distance $\delta(s,v)$.
3. Induction: after pass $i$, $d[v]\le$ the shortest distance using at most $i$ edges. Base $i=0$: $d[s]=0$. Step: the best $(i+1)$-edge path to $v$ ends with $(u,v)$, $d[u]$ already meets the $i$-edge bound, and pass $i+1$ relaxes $(u,v)$.
4. With no negative cycle a shortest path is simple, so it has at most $V-1$ edges; after $V-1$ passes $d[v]\le\delta(s,v)$, and with the upper bound, $d[v]=\delta(s,v)$.
5. It handles negative weights because it never finalises a vertex early. Example (directed graph): s→a 4, s→b 5, b→a $-3$; Dijkstra fixes a = 4 and never corrects it, while Bellman-Ford relaxes b-a and gets a = 5 - 3 = 2. An undirected negative edge is itself a negative cycle (a→b→a).
6. Negative-cycle check: with no negative cycle, point 4 means nothing relaxes on the $V$-th check. Conversely, if a negative cycle $v_0,\dots,v_k=v_0$ is reachable from $s$ and no edge relaxes after $V-1$ passes, then $d[v_i]\le d[v_{i-1}]+w(v_{i-1},v_i)$ for each cycle edge; summing round the cycle the $d$ terms cancel, giving $0\le$ cycle weight, contradicting a negative cycle. So the $V$-th check always fires.

Answer frame. Greedy idea; weighted graph; steps with the relaxation rule; distance table; pred table and tree; distances and complexity. For DAG longest path and Bellman-Ford, the numbered points in order, then the example.

Asked: [7 marks] (Dec 2022, Jun 2023) Explain Dijkstra's algorithm for finding shortest path with an example. Asked: [7 marks] (Jun 2023) Explain Dijkstra Algorithm with the help of example. Asked: [7 marks] (Nov 2022) Design an efficient algorithm for the longest directed path from $s$ to $t$ in an acyclic weighted digraph; state representation, data structures and time complexity. Asked: [7 marks] (Nov 2022) Reconstruct the proof of correctness of Bellman-Ford; how does it work with negative weights?

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. <mark>BFS and DFS are the two basic traversals; they differ in the data structure used and the order of visiting.</mark>

Key points. Kruskal and Prim build an MST, Dijkstra gives shortest paths from one source and Bellman-Ford also allows negative edges.

Asked: [7 marks] (Dec 2022) Difference between Breadth First Search and Depth First Search.

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">Low weight</span>

Definition. <mark>Graphs model networks such as roads, computer networks, social links and dependencies, and a connected component is a maximal set of vertices reachable from each other.</mark>

Key points.

1. Shortest routes use Dijkstra, and network wiring cost uses MST.
2. Task scheduling uses topological order of a DAG, and cycle detection uses DFS.
3. Counting connected components runs a traversal from every unvisited vertex.

Step 1: visited[v] = false for all v; count = 0.
Step 2: for each vertex v: if not visited[v], count = count + 1 and run DFS(v) (or BFS).
Step 3: return count.

Example. Graph A-F above plus edge G-H: at A, count = 1 and DFS marks A to F; at G, count = 2. Components = 2: {A,B,C,D,E,F} and {G,H}. Time $O(V+E)$.

Asked: [7 marks] (Dec 2022) Write an algorithm which counts the number of connected components of a graph.

Last-minute revision

• A graph is $G=(V,E)$; a tree has $V-1$ edges and no cycle.
• Matrix space is $O(V^2)$; adjacency list space is $O(V+E)$.
• BFS uses a queue, DFS a stack; both take $O(V+E)$.
• Spanning tree has $V-1$ edges; MST has the least total weight.
• Kruskal: sort edges, union-find, skip cycles; $O(E\log E)$.
• Prim: grow one tree with a min-heap; $O(E\log V)$.
• Dec 2023 hexagon graph MST cost is 57.
• Dijkstra needs non-negative weights; relax if $d[v]>d[u]+w$.
• Bellman-Ford: $V-1$ passes, $O(VE)$; a $V$-th improvement shows a negative cycle.
• DAG longest path: topological order plus relaxation, $O(V+E)$.
• Connected components: count the traversal starts.

Memory hooks

• Kruskal = Kut cycles, sort edges; Prim = Plant one tree and grow it.
• BFS = Big Queue level by level; DFS = Deep Stack.
• Dijkstra: pick the nearest, relax the neighbours, never negative.
• Matrix for dense, list for sparse.

Coverage checklist

• Introduction: definition, path, cycle, degree, tree.
• Classification of graph: Directed and Undirected graphs, etc: directed, weighted, complete, DAG.
• Representation: Nov 2022 / Jun 2024 matrix to digraph, Dec 2025 matrix and list.
• Graph Traversal: Depth First Search (DFS): Dec 2023 / Dec 2025 traversal techniques, Dec 2025 DFS and BFS.
• Breadth First Search (BFS): Dec 2024 BFS with example.
• Graph algorithm: Minimum Spanning Tree (MST)-Kruskal, Prim’s algorithms: Nov 2022 and Jun 2024 spanning tree vs MST, Nov 2022 negative weights, Dec 2023 Kruskal, Dec 2024 Prim vs Kruskal, Dec 2025 MST.
• Dijkstra’s shortest path algorithm: Dec 2022, Jun 2023 (two entries), plus Nov 2022 DAG longest path and Bellman-Ford.
• Comparison between different graph algorithms: Dec 2022 BFS vs DFS.
• Application of graphs: Dec 2022 connected components.