Unit 3 of 4 · BCA Sem 3

Unit 3: Graphs

Data Structures-II notes · PTU syllabus (UGCC2510)

3 min read5 topics8 exam questions
On this page
  1. Unit summary
  2. Graph terminology
  3. Types of graphs
  4. Memory representation
  5. Graph traversals: DFS and BFS
  6. Dijkstra's shortest path algorithm
  7. Key terms
  8. Quick revision
  9. Important questions

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
1

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.

Key termsGraph vocabulary
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.

2

Topic 2

Types of graphs

TypeMeaning
UndirectedEdges have no direction (A–B same as B–A)
Directed (digraph)Edges have direction (A → B)
WeightedEdges have weights or costs
CompleteEvery vertex is joined to every other vertex
Cyclic / acyclicContains a cycle / contains no cycle
Simple / multigraphNo 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.

3

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.

ComparisonAdjacency matrix vs adjacency list
Adjacency matrix
Adjacency list

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.

4

Topic 4

Graph traversals: DFS and BFS

GraphSample graph for BFS and DFS (start at A)
ABCDEF

BFS (queue): A B C D E F — level by level. DFS (stack/recursion): A B D E F C — deep first, then backtrack

ComparisonDFS vs BFS
Depth-first search
Breadth-first search

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.

5

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.

ProcessDijkstra's algorithm
  1. 1Initialise

    dist[source] = 0, all others ∞

  2. 2Pick the unvisited vertex u with the smallest dist
  3. 3Relax each neighbour v

    If dist[u] + w(u, v) < dist[v], update dist[v]

  4. 4Mark u visited
  5. 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

  1. Q1.Define a graph and a weighted graph.
  2. Q2.Differentiate between directed and undirected graphs.
  3. Q3.Compare adjacency matrix and adjacency list representations.
  4. Q4.Which data structures are used in DFS and BFS?
  5. Q5.What is the limitation of Dijkstra's algorithm?

Long-answer questions

  1. Q1.Explain the memory representations of graphs with an example.
  2. Q2.Explain DFS and BFS with algorithms and a worked example.
  3. 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.

WhatsApp us