Unit 4: Graphs
Data Structures notes · PTU syllabus (PGCA1913)
On this page
Unit summary
Graphs model networks of roads, computers and relationships. This unit covers graph representations — adjacency matrix, adjacency list and adjacency multilist — depth-first and breadth-first traversal, minimum spanning trees with Kruskal's algorithm, and shortest paths with Dijkstra's algorithm.
After this unit you can
- Represent graphs in memory
- Traverse graphs with DFS and BFS
- Find minimum spanning trees with Kruskal's algorithm
- Find shortest paths with Dijkstra's algorithm
PTU syllabus topics
- Graph representations (adjacency matrix, adjacency list, adjacency multilist)
- depth-first and breadth-first traversal
- minimum spanning tree
- shortest path algorithms — Kruskal's and Dijkstra's
Uses
Queue
Stack or recursion
Explores
Level by level
As deep as possible first
Finds
Shortest path in unweighted graphs
Cycles, topological order
Memory
Can be high for wide graphs
Lower for wide graphs
Topic 1
Graph terminology
A graph G = (V, E) is a set of vertices (nodes) V and a set of edges E connecting pairs of vertices.
- Adjacent vertices
- Vertices joined by an edge
- Degree
- Number of edges at a vertex; in-degree and out-degree for directed graphs
- Path
- A sequence of vertices joined by edges
- Cycle
- A path that starts and ends at the same vertex
- Connected graph
- A path exists between every pair of vertices
- Weighted graph
- Edges carry values such as distance or cost
Topic 2
Types of graphs
| Type | Meaning |
|---|---|
| Undirected | Edges have no direction (A–B same as B–A) |
| Directed (digraph) | Edges have direction (A → B) |
| Weighted | Edges have weights or costs |
| Complete | Every vertex is joined to every other vertex |
| Cyclic / acyclic | Contains a cycle / contains no cycle |
| Simple / multigraph | No loops or parallel edges / allows parallel edges |
A tree is a connected acyclic graph.
Topic 3
Adjacency matrix and adjacency list
Structure
V × V array; A[i][j] = 1 or the weight if an edge exists
Array of V lists of neighbours
Space
O(V²)
O(V + E)
Edge check
O(1)
O(degree)
Suits
Dense graphs
Sparse graphs
Example
Undirected graph with edges A–B, A–C, B–D, C–D: matrix rows A: 0 1 1 0, B: 1 0 0 1, C: 1 0 0 1, D: 0 1 1 0; lists A → B, C; B → A, D; C → A, D; D → B, C.
Topic 4
Adjacency multilist
- In an adjacency list of an undirected graph each edge appears twice. An adjacency multilist stores each edge once as a node shared by both vertex lists.
- Mark bit
- Whether the edge has been visited
- Vertex 1 and vertex 2
- The two endpoints
- Link 1
- Next edge incident on vertex 1
- Link 2
- Next edge incident on vertex 2
- Weight (optional)
- Cost of the edge
- Useful when edges must be marked or deleted once — e.g., in algorithms that process each edge a single time.
Topic 5
Depth-first and breadth-first traversal
Data structure
Stack (or recursion)
Queue
Explores
As deep as possible before backtracking
Level by level, nearest first
Finds
Cycles, connected components, topological order
Shortest path in an unweighted graph
Time
O(V + E)
O(V + E)
Example
Graph edges A–B, A–C, B–D, C–E. Starting from A: DFS visits A, B, D, C, E; BFS visits A, B, C, D, E.
Exam tip
Mark each vertex as visited when you first reach it; otherwise cycles cause infinite loops.
Topic 6
Minimum spanning trees and Kruskal's algorithm
- A spanning tree of a connected graph contains all V vertices and V − 1 edges without cycles; a minimum spanning tree (MST) has the least total weight.
- 1Sort all edges by increasing weight
- 2Take the smallest remaining edge
- 3Add it if it does not form a cycle (union–find check)
- 4Repeat until V − 1 edges are chosen
Example
Edges A–B 1, B–C 2, A–C 3, C–D 4, B–D 5: choose A–B (1), B–C (2), skip A–C (cycle), choose C–D (4). MST weight = 7.
- Complexity O(E log E). Prim's algorithm grows the tree from a start vertex, always adding the cheapest edge to a new vertex.
Topic 7
Dijkstra's shortest path algorithm
Dijkstra's algorithm finds the shortest distance from a source vertex to all other vertices in a weighted graph with non-negative edge weights.
- 1Initialise
dist[source] = 0, all others ∞
- 2Pick the unvisited vertex u with the smallest dist
- 3Relax each neighbour v
If dist[u] + w(u, v) < dist[v], update dist[v]
- 4Mark u visited
- 5Repeat until all vertices are visited
Example
From A: A–B = 4, A–C = 1, C–B = 2, B–D = 1. dist: A = 0, C = 1, then B = min(4, 1 + 2) = 3, then D = 3 + 1 = 4.
With a simple array the algorithm takes O(V²); with a priority queue (heap), O((V + E) log V).
Key terms
- Adjacency multilist
- Representation storing each undirected edge once
- DFS
- Traversal going deep before backtracking, using a stack
- BFS
- Level-by-level traversal using a queue
- Minimum spanning tree
- Spanning tree of least total weight
- Dijkstra's algorithm
- Single-source shortest paths with non-negative weights
Quick revision
- Vertices, edges, degree, path, cycle, connected; directed, weighted, complete graphs.
- Matrix O(V²), list O(V + E), multilist edges stored once.
- DFS with a stack; BFS with a queue.
- Kruskal: sort edges, union–find; Prim.
- Dijkstra: greedy, non-negative weights, O(V²) or O((V + E) log V) with a heap.
Important exam questions
Practice questions written to the PTU exam pattern for this unit's syllabus: short answers (Section A style) and long answers (Sections B and C style).
Short-answer questions
- Q1.Compare adjacency matrix and adjacency list storage.
- Q2.What is an adjacency multilist?
- Q3.Which data structure is used in BFS?
- Q4.How many edges does a spanning tree of 8 vertices have?
- Q5.How does Kruskal's algorithm avoid cycles?
- Q6.Why can't Dijkstra's algorithm handle negative weights?
Long-answer questions
- Q1.Explain graph representations with an example.
- Q2.Explain DFS and BFS with an example.
- Q3.Find the minimum spanning tree of a graph using Kruskal's algorithm.
- Q4.Find shortest paths using Dijkstra's algorithm (numerical).
Stuck on this unit?
Message SBS on WhatsApp for help with Data Structures, or to ask about studying M.Sc IT at Synetic.