Introduction to graph

Published by: Anil K. Panta

What is a Graph?

A Graph is a non-linear data structure used to represent connections or relationships between different items (called nodes or vertices).

Real-Life Example:

Think of a football match:

Players are nodes (vertices)
Passes between players are edges (connections)

This entire web of player interactions is a graph!

Formal Definition:

A graph is defined as:

G(V, E)
Where:

V is a set of vertices (nodes)
E is a set of edges (connections) between the nodes

Components of a Graph:

Vertices (Nodes)

Represent entities (e.g., cities, users, web pages)
Can be labeled or unlabelled

Edges (Connections)

Connect two vertices
Can be directed (one-way) or undirected (two-way)
Can have weights (distance, cost, etc.)

Types of Graphs in Data Structures:

Below are the most common types of graphs, each with an easy definition and image-based idea:

1. Null Graph

A graph with no edges — just isolated nodes.

Use Case: Represents isolated data points.

2. Trivial Graph

A graph with only one vertex and no edges.

Use Case: Smallest possible graph.

3. Undirected Graph

Edges don’t have direction. Connection goes both ways.

Use Case: Friendship on Facebook – if A is B’s friend, then B is A’s friend.

4. Directed Graph (Digraph)

Edges have a direction (from one node to another).

Use Case: Instagram following – you can follow someone, but they may not follow back.

5. Connected Graph

Every node is reachable from any other node.

Use Case: Internet routers forming a single working network.

6. Disconnected Graph

At least one node is not connected to others.

Use Case: Two separate groups of people who don’t talk to each other.

7. Regular Graph

Every node has the same number of edges.

Use Case: In a board game, every tile is connected to the same number of others.

8. Complete Graph

Every node is connected to every other node.

Use Case: A small group where everyone knows everyone.

9. Cycle Graph

Nodes form a closed loop (cycle). Each node connects to two others.

Use Case: Round-robin tournament structure.

10. Cyclic Graph

Any graph that contains at least one cycle (loop).

Use Case: Circular links between websites.

11. Directed Acyclic Graph (DAG)

A directed graph with no cycles.

Use Case: Task scheduling or dependency graphs in project management.

12. Bipartite Graph

Vertices can be split into two groups where no nodes inside a group connect to each other.

Use Case: Students and courses — students only connect to courses, not to each other.

13. Weighted Graph

A graph where edges have weights (e.g., cost, distance, time).

Use Case: Google Maps – roads have distances (weights).

Why Are Graphs Important?

Used in maps (GPS navigation)
Powering social networks (friends, followers)
Search engines, network routing, AI, and games
Great for representing relationships and paths

Summary Table

Graph Type	Description	Real Example
Null Graph	No edges	Isolated data
Trivial Graph	One vertex only	Basic test case
Undirected Graph	Two-way connection	Facebook friendships
Directed Graph	One-way connection	Instagram follow system
Connected Graph	All nodes are reachable	Wi-Fi or computer network
Disconnected Graph	Some nodes can’t be reached	Disconnected servers
Regular Graph	All nodes have the same degree	Board game design
Complete Graph	Every node connects to every other node	Fully connected team
Cycle Graph	Forms a circular path	Round-robin tournament
Cyclic Graph	Has at least one loop	Navigation loops
DAG	Directed, no loops	Task scheduling, compiler flow
Bipartite Graph	Two groups, no internal edges	Students & subjects
Weighted Graph	Edges have weights (distance, cost, etc.)	Google Maps, airline routes

Final Thought:

A graph data structure helps us understand how different items are connected. Whether it’s people, places, or web pages — graphs help model and solve real-world problems efficiently.