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
Data structure
Queue
Stack or recursion
Explores
Level by level
As deep as possible first
Finds shortest path
Yes, in unweighted graphs
Not guaranteed
Uses
Shortest path, web crawling
Cycle detection, topological sort
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
Memory representation
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
Topic 4
Graph traversals: DFS and BFS
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.