DSA · Lecture notes · Unit 5

Graphs

GRAPHS

Terminologies • Matrix & List Representation • DFS • BFS • Applications

Undergraduate Computer Science

Learning Objectives

  • Define graphs and explain fundamental graph terminology.
  • Represent graphs using adjacency matrices and adjacency lists.
  • Compare graph representations and select an appropriate one.
  • Understand and implement Depth First Search (DFS) and Breadth First Search (BFS).
  • Trace DFS and BFS step-by-step.
  • Explain graph applications and analyze traversal complexity.
  1. Introduction to Graphs A graph is a non-linear data structure consisting of vertices (nodes) and edges connecting pairs of vertices. It is commonly represented as G = (V, E), where V is the set of vertices and E is the set of edges.
A
B---C
|
D
V = {A, B, C, D}
E = {(A,B), (A,C), (B,C), (B,D)}
  1. Applications of Graphs in Computer Science
ApplicationUse
Computer networksDevices are vertices; communication links are edges.
Social networksUsers are vertices; relationships are edges.
Maps/navigationLocations are vertices; roads are weighted edges.
Web searchWeb pages are vertices; hyperlinks are directed edges.
Operating systemsProcess-resource relationships and deadlock models.
Artificial intelligenceKnowledge graphs, state-space search and planning.
Compiler designControl-flow, dependency and data-flow graphs.
Recommendation systemsUsers/items and relationships can be modeled as graphs.
  1. Graph Terminology
TermMeaning
VertexAn individual node in a graph.
EdgeA connection between two vertices.
Adjacent verticesVertices directly connected by an edge.
Incident edgeAn edge connected to a particular vertex.
DegreeNumber of edges incident on a vertex in an undirected graph.
PathA sequence of vertices connected by edges.
CycleA path that starts and ends at the same vertex.
Connected graphA graph where every pair of vertices has a path between them.
Disconnected graphA graph containing separate components.
Complete graphA graph in which every pair of distinct vertices is connected.

3.1 Directed and Undirected Graphs

Directed: A → B → C
Undirected: A ---- B

Directed edges have direction; undirected edges do not.

3.2 Weighted Graph

A ----- B
| |
10 3
| |
D ----- C

Weights may represent distance, cost, time, bandwidth or risk.

  1. Graph Representation The two fundamental representations are adjacency matrix and adjacency list.

  2. Adjacency Matrix An adjacency matrix is a two-dimensional array in which matrix[i][j] indicates whether an edge exists from vertex i to vertex j.

A ---- B
| |
| |
D ---- C
A B C D
A 0 1 0 1
B 1 0 1 0
C 0 1 0 1
D 1 0 1 0

For an undirected graph, the matrix is symmetric: matrix[i][j] = matrix[j][i].

5.1 Weighted Matrix

A B C D
A 0 5 ∞ 10
B 5 0 3 ∞
C ∞ 3 0 7
D 10 ∞ 7 0
  • Edge lookup takes O(1).
  • Space requirement is O(V²).
  • Excellent for dense graphs.
  • Can waste space for sparse graphs.
  1. Adjacency List An adjacency list stores the neighbors of each vertex in a separate list.
A → B → D
B → A → C
C → B → D
D → A → C

A linked-list node may be defined as:

struct Node
{
int vertex;
struct Node *next;
};
  • Typical storage is O(V + E).
  • Efficient for sparse graphs.
  • Finding neighbors is efficient.
  • A particular edge may require searching a neighbor list.
  1. Matrix vs List
FeatureMatrixList
Structure2D arrayNeighbor list per vertex
SpaceO(V²)O(V + E)
Edge lookupO(1)O(degree) basic list
Find neighborsO(V)O(degree)
Dense graphsGoodLess advantageous
Sparse graphsWastefulExcellent
  1. Elementary Graph Operations
  • Add vertex
  • Add edge
  • Delete vertex
  • Delete edge
  • Search vertex
  • Find adjacent vertices
  • Traverse graph

The two fundamental traversal methods are DFS and BFS.

  1. Graph Traversal Graph traversal visits vertices systematically. Since graphs can contain cycles and multiple paths, a visited array or set is required to prevent repeated processing.

  2. Depth First Search (DFS)

DFS explores as far as possible along one path before backtracking. It uses recursion or an explicit stack.

A
B C
/ \ \
D E F
One DFS order from A:
A B D E C F

10.1 Recursive DFS Pseudocode

DFS(vertex)
mark vertex as VISITED
visit(vertex)
for each neighbor of vertex
if neighbor is NOT VISITED
DFS(neighbor)

10.2 DFS for Disconnected Graph

DFS_GRAPH(G)
mark all vertices as NOT VISITED
for each vertex v in G
if v is NOT VISITED
DFS(v)

10.3 Iterative DFS Using Stack

DFS_ITERATIVE(G, start)
create empty STACK
create VISITED array
push start into STACK
while STACK is not empty
vertex = pop(STACK)
if vertex is not VISITED
mark vertex as VISITED
visit(vertex)
for each neighbor of vertex
if neighbor is not VISITED
push neighbor into STACK

A stack follows LIFO (Last In, First Out), supporting depth-first behavior.

  1. DFS Step-by-Step Example

  2. Visit A.

  3. Move to B.

  4. Move to D; D has no unvisited neighbor, so backtrack.

  5. Visit E.

  6. Backtrack to A and visit C.

  7. Visit F.

Result: A B D E C F. The exact order depends on the order of neighbors.

  1. Breadth First Search (BFS)

BFS explores a graph level by level and normally uses a queue.

A
B C
/ \ \
D E F
Level 0: A
Level 1: B C
Level 2: D E F
BFS = A B C D E F

12.1 BFS Pseudocode

BFS(G, start)
create empty QUEUE
create VISITED array
mark start as VISITED
enqueue(start)
while QUEUE is not empty
vertex = dequeue()
visit(vertex)
for each neighbor of vertex
if neighbor is NOT VISITED
mark neighbor as VISITED
enqueue(neighbor)

12.2 BFS Step-by-Step

  1. Enqueue A.

  2. Remove A and enqueue B,C.

  3. Remove B and enqueue D,E.

  4. Remove C and enqueue F.

  5. Visit D, E and F.

Result: A B C D E F.

  1. DFS vs BFS
FeatureDFSBFS
StrategyGo deep, then backtrackVisit level by level
Data structureStack / recursionQueue
Shortest path in unweighted graphNot guaranteedYes, from source
Typical usesBacktracking, cycle detection,Shortest paths, levels, broadcasting

components

  1. Applications of DFS
  • Maze solving and backtracking.
  • Cycle detection.
  • Connected-component identification.
  • Topological sorting in appropriate DAGs.
  • State-space and puzzle exploration.
  • Dependency analysis.
  1. Applications of BFS
  • Shortest path in an unweighted graph.
  • Friends-of-friends in social networks.
  • Network broadcasting.
  • Level-order exploration.
  • Web crawling by levels.
  • Minimum number of edges from a source.
  1. Disconnected Graphs
A ---- B C ---- D

A traversal starting at A visits only A and B. To traverse the complete graph, another traversal must begin from an unvisited vertex such as C.

TRAVERSE_GRAPH(G)
mark all vertices as NOT VISITED
for each vertex v in G
if v is NOT VISITED
DFS(v) // or BFS(v)
  1. Complexity of DFS and BFS Let V be the number of vertices and E the number of edges.
RepresentationDFS TimeBFS Time
Adjacency ListO(V + E)O(V + E)
Adjacency MatrixO(V²)O(V²)

Auxiliary traversal space is O(V) for visited information and the stack/queue, excluding graph storage.

  1. Worked Example
A
B C
/ \ \
D E F
\
G
Edges:
A-B, A-C, B-D, B-E, C-F, E-G
TraversalResult
DFS from AA B D E G C F
BFS from AA B C D E F G

These orders assume neighbors are processed left-to-right.

  1. Graph vs Tree
FeatureTreeGraph
StructureHierarchicalGeneral network
CyclesNo cyclesMay contain cycles
RootUsually has a rootNo root required
Path between two verticesExactly oneMay be multiple
ConnectivityConnectedMay be disconnected
Edges for n verticesn − 1Variable
TraversalDFS/BFS and tree traversalsDFS/BFS
  1. Common Student Mistakes

  2. Forgetting the visited array/set.

  3. Confusing DFS with BFS: DFS → stack/recursion; BFS → queue.

  4. Assuming DFS always finds the shortest path.

  5. Forgetting disconnected components.

  6. Assuming traversal order is unique; it depends on neighbor order.

  7. Quick Revision Sheet

ConceptRemember
GraphG = (V,E)
VSet of vertices
ESet of edges
Directed graphEdges have direction
Undirected graphEdges have no direction
Weighted graphEdges have weights
PathSequence of connected vertices
CycleReturns to starting vertex
Adjacency MatrixO(V²) space
Adjacency ListO(V+E) space
DFSStack / recursion
BFSQueue
DFS/BFS with listO(V+E)
  1. Exam-Oriented Questions

Short Answer Questions

  1. Define a graph.

  2. What are vertices and edges?

  3. Differentiate directed and undirected graphs.

  4. Define a weighted graph.

  5. What is the degree of a vertex?

  6. What is a path?

  7. What is a cycle?

  8. Define a connected graph.

  9. What is an adjacency matrix?

  10. What is an adjacency list?

  11. What is DFS?

  12. What is BFS?

  13. Which data structure is used by DFS?

  14. Which data structure is used by BFS?

  15. What is the time complexity of DFS using an adjacency list?

  16. Why is a visited array required?

  17. Give two applications of graphs.

  18. Give two applications of DFS.

  19. Give two applications of BFS.

Long Answer Questions

  1. Explain graph terminology with suitable examples.

  2. Explain adjacency matrix representation with an example.

  3. Explain adjacency list representation with an example.

  4. Compare adjacency matrix and adjacency list.

  5. Explain DFS with pseudocode and a suitable graph.

  6. Explain BFS with pseudocode and a suitable graph.

  7. Compare DFS and BFS.

  8. Explain traversal of disconnected graphs.

  9. Discuss applications of graphs in computer science.

  10. Analyze the time and space complexity of DFS and BFS.

  11. Key Takeaways

  • Graphs model relationships using vertices and edges.
  • Matrices are convenient for dense graphs; lists are efficient for sparse graphs.
  • DFS explores deeply and uses recursion or a stack.
  • BFS explores level by level and uses a queue.
  • A visited mechanism is essential for general graph traversal.
  • With an adjacency list, DFS and BFS run in O(V + E).