Data Structure - Unit IV - Graph

 

Graph – IV

 

Definition of Graph

A graph is a non-linear data structure consisting of a set of vertices (nodes) and a set of edges (links) that connect pairs of vertices.

 Standard Definition:

 A graph is defined as G = (V, E)
where:

• V = set of vertices
• E = set of edges

Simple Explanation:

• Vertices = points (like A, B, C)
• Edges = connections between them

Example:

If V = {A, B, C}
E = {(A, B), (B, C)}

Then the graph connects:
 A — B — C

---

Graph Representation in Data Structure

Graphs can be represented in a computer mainly in two ways:

1. Adjacency Matrix

 A graph is represented using a 2D array (matrix)

 Idea:

·         Rows and columns represent vertices

·         Value = 1 (or weight) if edge exists, otherwise 0

 

Example:

Graph:
A — B, A — C, B — C

Matrix:

	A	B	C
A	0	1	1
B	1	0	1
C	1	1	0

✔Advantages:

·         Easy to implement

·         Quick to check if edge exists

❌ Disadvantages:

·         Uses more memory (especially for large graphs)

 

2. Adjacency List

 Each vertex stores a list of its adjacent vertices

Example:

Graph:
A — B, A — C, B — C

List Representation:

·         A → B, C

·         B → A, C

·         C → A, B

✔ Advantages:

·         Saves memory

·         Efficient for sparse graphs

❌ Disadvantages:

·         Slightly complex

·         Edge checking takes more time

---

TYPES OF GRAPHS WITH EXAMPLES

1. Undirected Graph

            Edges have no direction

Example:
A — B, B — C

✔ You can travel both ways
✔ (A, B) = (B, A)

 

2. Directed Graph (Digraph)

            Edges have direction

Example:
A → B, B → C

✔ One-way connection
✔ (A → B) ≠ (B → A)

 

3. Weighted Graph

            Each edge has a weight (cost/distance)

Example:
A —(5)— B
B —(3)— C

✔ Used in shortest path problems

 

4. Unweighted Graph

 No weights on edges

Example:
A — B — C

✔ All edges are equal

 

5. Cyclic Graph

            Contains at least one cycle

Example:
A → B → C → A

✔ Forms a loop

 

6. Acyclic Graph

            No cycles

Example:
A → B → C

✔ No looping

 

7. Complete Graph

            Every vertex is connected to every other vertex

Example (3 nodes):
A — B
A — C
B — C

✔ Maximum number of edges

 

8. Connected Graph

            There is a path between every pair of vertices

Example:
A — B — C

✔ All nodes are reachable

 

9. Disconnected Graph

            Some vertices are not connected

Example:
A — B C — D

✔ Two separate components

 

10. Simple Graph

            No loops and no multiple edges

Example:
A — B — C

✔ Clean structure

 

11. Multigraph

            Multiple edges between same vertices

Example:
A == B (two edges)

✔ Parallel edges allowed

 

12. Pseudograph

            Contains self-loop

Example:
A → A

✔ Node connects to itself

 

Breadth First Traversal (BFT)

 BFS is a graph traversal method where we visit nodes level by level (one layer at a time).

·         Start from a node

·         Visit all its neighbors first

·         Then move to next level neighbors

Uses Queue (FIFO)

 First In → First Out

BFS Algorithm (Using Queue)

1.      Create an empty queue

2.      Insert (enqueue) the starting node

3.      Mark it as visited

4.      Repeat until queue is empty:

o    Remove (dequeue) a node

o    Print (visit) the node

o    Add all unvisited neighbors to queue

o    Mark them as visited

Example:

Graph:
A → B, C
B → D
C → E

Steps:

·         Enqueue A → Queue: [A]

·         Dequeue A → Visit A → Enqueue B, C → [B, C]

·         Dequeue B → Visit B → Enqueue D → [C, D]

·         Dequeue C → Visit C → Enqueue E → [D, E]

·         Dequeue D → Visit D → [E]

·         Dequeue E → Visit E

 BFS Order:

 A, B, C, D, E

---

Depth First Traversal (DFT)

 DFS is a graph traversal method where we go as deep as possible first, then backtrack.

·         Start from a node

·         Visit one neighbor

·         Keep going deeper

·         If no more nodes → go back (backtracking)

Uses Stack (LIFO)

 Last In → First Out

DFS Algorithm (Using Stack)

1.      Create an empty stack

2.      Push the starting node into stack

3.      Mark it as visited

4.      Repeat until stack is empty:

o    Pop a node from stack

o    Print (visit) the node

o    Push all unvisited neighbors into stack

o    Mark them as visited

Example:

Graph:
A → B, C
B → D
C → E

Steps:

·         Push A → Stack: [A]

·         Pop A → Visit A → Push B, C → Stack: [B, C]

·         Pop C → Visit C → Push E → Stack: [B, E]

·         Pop E → Visit E → Stack: [B]

·         Pop B → Visit B → Push D → Stack: [D]

·         Pop D → Visit D

 DFS Order:

 A, C, E, B, D

 

DFS vs BFS (Quick Difference)

Feature	DFS	BFS
Data Structure	Stack	Queue
Approach	Deep first	Level wise
Order	A, C, E...	A, B, C...

---

Topological Sort

Topological sorting can be done by repeatedly selecting vertices whose indegree = 0.

If at any step no vertex has indegree = 0 but graph still has nodes →
 Cycle exists → Topological sort not possible

Always pick nodes with indegree = 0, remove them, and update the graph

 

What is Indegree?

 Indegree of a vertex = Number of incoming edges to that vertex.

Example:
If A → B, then indegree(B) = 1

Algorithm:

1. Find indegree of all vertices.
2. Select all vertices with indegree = 0.
3. Add them to the result (ordering).
4. Remove that vertex and its outgoing edges from the graph.
5. Update indegrees of remaining vertices.
6. Repeat steps 2–5 until all vertices are processed.

Example:

Graph:
A → B
A → C
B → D
C → D

Step 1: Indegree

Vertex	Indegree
A	0
B	1
C	1
D	2

Step 2: Process vertices with indegree = 0

• Pick A → Result: A
• Remove A → update indegree

Vertex	Indegree
B	0
C	0
D	2

Step 3:

• Pick B → Result: A, B
• Remove B → update

Vertex	Indegree
C	0
D	1

Step 4:

• Pick C → Result: A, B, C
• Remove C → update

Vertex	Indegree
D	0

Step 5:

• Pick D → Result: A, B, C, D

 Final Topological Order:

 A, B, C, D

---

Biconnectivity in Graph

A graph is said to be biconnected if it remains connected after the removal of any one vertex and its associated edges.

 It is also called a 2-connected graph.

Biconnectivity ensures that a graph remains connected even after the removal of any single vertex, making it highly useful in designing stable and fault-tolerant systems.

Key Concept

·         A vertex whose removal disconnects the graph is called an Articulation Point (Cut Vertex)

·         A graph is biconnected if it has no articulation points

Properties of Biconnected Graph

·         The graph must be connected

·         There should be at least two disjoint paths between every pair of vertices

·         Removing any single vertex will not disconnect the graph

Example

Biconnected Graph:

A — B
| |
C — D

·         Removing any one vertex still keeps the graph connected
 Hence, it is biconnected

❌ Not Biconnected Graph:

A — B — C

·         Removing vertex B disconnects the graph
 B is an articulation point
 Hence, not biconnected

Advantages

·         Improves network reliability

·         Prevents single point of failure

---

Cut Vertex (Articulation Point)

A cut vertex (or articulation point) is a vertex in a graph whose removal increases the number of connected components.

 If removing a vertex breaks the graph into separate parts, that vertex is a cut vertex.

A graph with no articulation points is called a biconnected graph.

Simple Idea:

 “Remove the vertex → graph becomes disconnected”

Example:

Graph:
A — B — C

• Remove B → A and C become separate
   So, B is a cut vertex

❌ Non Example:

Graph:
A — B
| |
C — D

• Remove any one vertex → graph is still connected
   No cut vertex

Key Points:

• Cut vertex exists only in connected graphs
• It is a critical point in the graph
• Also called articulation point

How to Find :

1. Perform DFS traversal
2. Track:
• Discovery time (disc)
• Low value (low)
3. A vertex is cut vertex if:
• Root node has more than one child
• For non-root:
   if low[child] ≥ disc[parent]

 Applications:

• Network design (identify weak points)
• Communication systems
• Road/transport networks

 

---

Euler Circuit

 An Euler Circuit is a closed path in a graph that:

 Visits every edge exactly once
 Starts and ends at the same vertex

Simple Idea:

 “Travel through all edges one time and come back to start”

Conditions for Euler Circuit

A graph has an Euler circuit if:

✔ The graph is connected
✔ All vertices have even degree

Example

Graph:
A — B
| |
D — C

Degrees:

• A = 2, B = 2, C = 2, D = 2 (all even)

 Euler Circuit exists

One possible circuit:
 A → B → C → D → A

❌ Non Example

Graph:
A — B — C

Degrees:

• A = 1, B = 2, C = 1

 Not all vertices are even
 No Euler circuit

Euler Path vs Euler Circuit

Feature	Euler Path	Euler Circuit
Start & End	Different	Same
Edge Visit	Once	Once
Condition	2 odd vertices	All even vertices

Applications

• Route planning
• Network traversal
• Puzzle solving (like bridge problems)

---

Applications of Graphs

Graphs are widely used to represent real-world relationships and connections.

Graphs are used to represent and solve problems involving connections between objects.

1. Computer Networks

 Graphs represent connections between computers

• Nodes = Computers
• Edges = Network connections

2. Social Networks

 Used in apps like Facebook and Instagram

• Nodes = People
• Edges = Friend relationships

3. Transportation Systems

 Used in maps and navigation

• Nodes = Cities
• Edges = Roads
  ✔ Helps find shortest path (like Google Maps)

4. Web Page Linking

 Search engines like Google use graphs

• Nodes = Web pages
• Edges = Links between pages

5. Project Scheduling

 Used in task planning (PERT/CPM)

• Nodes = Tasks
• Edges = Dependencies

---