Unit 3: Graphs
Data Structures-II notes · PTU syllabus (UGCC2510)
On this page
Unit summary
A graph models connections: roads between cities, friendships in a social network, links between web pages. This unit covers graph terminology, types of graphs, how graphs are stored in memory, the two traversal methods (DFS and BFS), and Dijkstra's shortest path algorithm.
After this unit you can
- Define graph terminology and types of graphs
- Represent a graph using an adjacency matrix and an adjacency list
- Perform depth-first and breadth-first traversals
- Find shortest paths using Dijkstra's algorithm
PTU syllabus topics
- Definition and terminology
- types of graphs
- memory representation
- depth-first and breadth-first traversal
- Dijkstra's shortest path algorithm
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
Example
Degrees in a graph: with vertices A, B, C, D and edges A–B, A–C, B–C, C–D, the degrees are A = 2, B = 2, C = 3, D = 1. The sum is 8, twice the number of edges (4). A–B–C–D is a path and A–B–C–A is a cycle.
Exam tip
Handshaking lemma: the sum of all degrees equals twice the number of edges.
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.
Example
Everyday graphs: friendships on a social network form an undirected graph. "Follows" on a platform form a directed graph. A road map with distances is a weighted graph. A complete graph with n vertices has n(n − 1)/2 edges: 6 edges for 4 vertices.
Topic 3
Memory representation
A graph can be stored in memory in two main ways: an adjacency matrix (a V × V table of 0s and 1s) or an adjacency list (for each vertex, a list of its neighbours). The choice depends on how many edges the graph has.
Structure
V × V matrix; A[i][j] = 1 (or weight) if an edge exists
Each vertex has a linked list of its neighbours
Space
O(V²)
O(V + E)
Check edge (i, j)
O(1)
O(degree)
Best for
Dense graphs
Sparse graphs
Example
A graph with 4 vertices and edges A–B, A–C, B–D: the matrix needs 4 × 4 = 16 cells, with 1 in cells AB, BA, AC, CA, BD and DB. The adjacency list is A → B, C; B → A, D; C → A; D → B, which is 6 entries. For a sparse graph the list saves memory.
Exam tip
Matrix: O(V²) space, O(1) time to check an edge. List: O(V + E) space, good for sparse graphs.
Topic 4
Graph traversals: DFS and BFS
BFS (queue): A B C D E F — level by level. DFS (stack/recursion): A B D E F C — deep first, then backtrack
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 5
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
- Graph
- A set of vertices connected by edges
- Directed graph
- A graph whose edges have direction
- Adjacency matrix
- A V × V table showing which vertices are connected
- DFS
- Traversal going deep first, using a stack
- BFS
- Traversal going level by level, using a queue
Quick revision
- Matrix: O(V²) space, good for dense graphs; list: O(V + E), good for sparse.
- DFS uses a stack; BFS uses a queue; both O(V + E).
- BFS gives shortest paths in unweighted graphs.
- Dijkstra needs non-negative weights; relax edges from the nearest vertex.
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.Define a graph and a weighted graph.
- Q2.Differentiate between directed and undirected graphs.
- Q3.Compare adjacency matrix and adjacency list representations.
- Q4.Which data structures are used in DFS and BFS?
- Q5.What is the limitation of Dijkstra's algorithm?
Long-answer questions
- Q1.Explain the memory representations of graphs with an example.
- Q2.Explain DFS and BFS with algorithms and a worked example.
- Q3.Find the shortest paths from a source vertex using Dijkstra's algorithm for a graph of your choice.
Stuck on this unit?
Message SBS on WhatsApp for help with Data Structures-II, or to ask about studying BCA at Synetic.
