Data Structures — Graphs BFS | DFS | Adjacency Matrix | Adjacency List
Data Structures
Chapter: Graphs
Adjacency Matrix | Adjacency List | BFS | DFS
Topics Covered
• Graph Basics & Terminology
• Adjacency Matrix Representation
• Adjacency List Representation
• BFS Traversal Algorithm
• DFS Traversal Algorithm
• Comparison Tables
• Real Life Applications
• Viva Questions
1. Introduction to Graphs
Graphs are one of the most important non-linear data structures in Computer Science. They
are used to represent relationships between objects. Unlike arrays, linked lists, stacks, and
queues which store data linearly, graphs represent complex connections among multiple
entities.
1.1 Real-World Applications
• Social Networks (Facebook friends, Instagram followers)
• Google Maps and Navigation Systems
• Computer Networks
• Airline Route Systems
• Web Page Linking
• Artificial Intelligence
• Operating Systems
• Compiler Design
Mathematical Definition: G = (V, E) where G = Graph, V = Set of Vertices, E = Set of
Edges
CS Notes Page 1
, Data Structures — Graphs BFS | DFS | Adjacency Matrix | Adjacency List
2. Basic Terminology
2.1 Vertex (Node)
A vertex is an individual point in a graph. Example: Cities like Lahore, Karachi, Islamabad.
2.2 Edge
An edge is a connection between two vertices.
Example: E = (Lahore, Karachi)
2.3 Directed Graph (Digraph)
Edges have direction. Example: A follows B on Twitter does not mean B follows A.
Representation: A → B
2.4 Undirected Graph
Edges do not have direction. If A is connected to B, then B is automatically connected to A.
Representation: A — B
2.5 Weighted Graph
A graph in which edges contain weights or costs.
Example: Lahore → Karachi = 1200 km
2.6 Degree of Vertex
The number of edges connected to a vertex is called its degree.
Formula: Degree(A) = 3 (if 3 edges are connected)
2.7 Path
A sequence of vertices connected through edges.
Example: A → B → C → D
2.8 Cycle
A path that starts and ends at the same vertex.
Example: A → B → C → A
CS Notes Page 2
Data Structures
Chapter: Graphs
Adjacency Matrix | Adjacency List | BFS | DFS
Topics Covered
• Graph Basics & Terminology
• Adjacency Matrix Representation
• Adjacency List Representation
• BFS Traversal Algorithm
• DFS Traversal Algorithm
• Comparison Tables
• Real Life Applications
• Viva Questions
1. Introduction to Graphs
Graphs are one of the most important non-linear data structures in Computer Science. They
are used to represent relationships between objects. Unlike arrays, linked lists, stacks, and
queues which store data linearly, graphs represent complex connections among multiple
entities.
1.1 Real-World Applications
• Social Networks (Facebook friends, Instagram followers)
• Google Maps and Navigation Systems
• Computer Networks
• Airline Route Systems
• Web Page Linking
• Artificial Intelligence
• Operating Systems
• Compiler Design
Mathematical Definition: G = (V, E) where G = Graph, V = Set of Vertices, E = Set of
Edges
CS Notes Page 1
, Data Structures — Graphs BFS | DFS | Adjacency Matrix | Adjacency List
2. Basic Terminology
2.1 Vertex (Node)
A vertex is an individual point in a graph. Example: Cities like Lahore, Karachi, Islamabad.
2.2 Edge
An edge is a connection between two vertices.
Example: E = (Lahore, Karachi)
2.3 Directed Graph (Digraph)
Edges have direction. Example: A follows B on Twitter does not mean B follows A.
Representation: A → B
2.4 Undirected Graph
Edges do not have direction. If A is connected to B, then B is automatically connected to A.
Representation: A — B
2.5 Weighted Graph
A graph in which edges contain weights or costs.
Example: Lahore → Karachi = 1200 km
2.6 Degree of Vertex
The number of edges connected to a vertex is called its degree.
Formula: Degree(A) = 3 (if 3 edges are connected)
2.7 Path
A sequence of vertices connected through edges.
Example: A → B → C → D
2.8 Cycle
A path that starts and ends at the same vertex.
Example: A → B → C → A
CS Notes Page 2
