Graph is one of the most powerful non-linear data structures used in computer science. It is designed to represent relationships between different objects. Unlike arrays, linked lists, stacks, and queues that organize data in a sequential manner, graphs focus on connections among data elements.
Graphs are widely used in social media platforms, computer networks, navigation systems, recommendation engines, search engines, transportation systems, and artificial intelligence applications. Whenever relationships between entities need to be represented, graphs become an ideal solution.
For example, in a social networking website, users are connected through friendships. Each user can be represented as a node, and friendships can be represented as connections between nodes. This structure naturally forms a graph.
A Graph is a non-linear data structure consisting of a set of vertices (nodes) and edges (connections). Vertices represent entities, while edges represent relationships between those entities.
A Graph is a collection of vertices and edges where vertices store data and edges define the relationships between vertices.
A
/ \
B---C
\
D
In this graph:
Many real-world problems involve relationships rather than simple sequences. Linear data structures cannot efficiently represent such relationships.
Graphs provide a flexible structure that can model complex systems involving multiple connections.
Every graph consists of two fundamental components:
A Vertex is a basic unit of a graph used to represent an object or entity.
An Edge is a connection between two vertices.
Before learning graph algorithms, it is important to understand the terminology used in graph theory.
A Vertex is an individual element in a graph.
A, B, C, D
These are vertices of a graph.
An Edge connects two vertices and represents a relationship.
A ----- B
The line connecting A and B is called an edge.
Two vertices connected directly by an edge are called adjacent vertices.
A ----- B
A and B are adjacent vertices.
The number of edges connected to a vertex is called the degree of that vertex.
A
/|\
B C D
Degree of A = 3
A Path is a sequence of vertices connected through edges.
A → B → C → D
This sequence represents a path.
A Cycle occurs when a path starts and ends at the same vertex.
A → B → C → A
This forms a cycle.
A graph is called connected if every vertex can be reached from every other vertex.
A ----- B | | C ----- D
All vertices are connected to each other.
A graph is called disconnected if some vertices cannot be reached from others.
A ----- B C ----- D
The graph contains separate components.
Graphs can be classified into different categories based on edge directions and weights.
In an Undirected Graph, edges do not have any direction.
A ----- B
The connection can be traversed in both directions.
A ↔ B
In a Directed Graph, edges have a specific direction.
A -----> B
Movement is allowed only in the specified direction.
A Weighted Graph assigns a value or cost to each edge.
A --5-- B
The value 5 may represent distance, cost, or time.
An Unweighted Graph contains edges without any associated cost.
A ----- B
A graph containing one or more cycles is called a Cyclic Graph.
A → B → C → A
A graph without cycles is called an Acyclic Graph.
A → B → C → D
Graphs are used extensively in modern technology because many systems involve interconnected data.
Users are represented as vertices, and friendships are represented as edges.
Computers and devices are represented as nodes connected through communication links.
Cities and roads are represented using graph structures to find optimal routes.
Web pages are connected through hyperlinks, forming large web graphs.
E-commerce and streaming platforms use graphs to suggest products and content.
Airports and flight routes can be modeled using graphs.
Graphs help determine the best communication path between devices.
After understanding the basic concepts and terminology of graphs, the next important topic is graph representation. Graph representation refers to the method used to store a graph in computer memory. Since graphs may contain a large number of vertices and edges, choosing an efficient representation technique is important for performance and memory management.
The two most common methods used to represent graphs are:
Computers cannot directly understand diagrams or graphical structures. Therefore, graphs must be converted into a format that can be stored and processed efficiently.
Graph representation helps perform operations such as insertion, deletion, searching, traversal, and path finding efficiently.
An Adjacency Matrix is a two-dimensional array used to represent a graph. If a graph contains N vertices, an N × N matrix is created.
Each row and column represents a vertex. If an edge exists between two vertices, the corresponding matrix cell contains 1; otherwise, it contains 0.
Consider the following graph:
A
/ \
B---C
| A | B | C | |
|---|---|---|---|
| A | 0 | 1 | 1 |
| B | 1 | 0 | 1 |
| C | 1 | 1 | 0 |
The value 1 indicates that an edge exists between the corresponding vertices.
An Adjacency List stores graph information using linked lists or dynamic lists. Each vertex maintains a list of its adjacent vertices.
This method is memory efficient because only existing edges are stored.
Consider the same graph:
A
/ \
B---C
A → B → C B → A → C C → A → B
Each vertex stores only its neighboring vertices.
| Adjacency Matrix | Adjacency List |
|---|---|
| Uses 2D Array | Uses Linked Lists |
| Consumes More Memory | Consumes Less Memory |
| Fast Edge Lookup | Slower Edge Lookup |
| Best for Dense Graphs | Best for Sparse Graphs |
| Simple Implementation | Flexible Structure |
Several operations can be performed on graphs to manipulate and analyze graph data.
Graph Traversal is the process of visiting every vertex of a graph exactly once. Traversal is important for searching, path finding, connectivity checking, and network analysis.
The two most common graph traversal techniques are:
Breadth First Search explores all neighboring vertices before moving to the next level. BFS uses a Queue data structure for traversal.
It visits vertices level by level.
A
/ \
B C
/ \ \
D E F
Starting Vertex: A
A → B → C → D → E → F
Vertices are visited level by level from left to right.
Step 1: Insert starting vertex into queue. Step 2: Mark vertex as visited. Step 3: Remove vertex from queue. Step 4: Visit all adjacent unvisited vertices. Step 5: Insert adjacent vertices into queue. Step 6: Repeat until queue becomes empty.
Depth First Search explores a path completely before moving to another branch.
DFS uses a Stack data structure or recursion.
A
/ \
B C
/ \ \
D E F
Starting Vertex: A
A → B → D → E → C → F
DFS explores deeper levels first before backtracking.
Step 1: Visit starting vertex. Step 2: Mark vertex as visited. Step 3: Move to an unvisited adjacent vertex. Step 4: Repeat recursively. Step 5: Backtrack when no unvisited vertex exists.
| BFS | DFS |
|---|---|
| Uses Queue | Uses Stack |
| Level-by-Level Traversal | Depth-Based Traversal |
| Finds Shortest Path | Does Not Guarantee Shortest Path |
| Higher Memory Usage | Lower Memory Usage |
| Suitable for Wide Graphs | Suitable for Deep Graphs |
| Algorithm | Time Complexity |
|---|---|
| BFS | O(V + E) |
| DFS | O(V + E) |
Where:
Both algorithms visit every vertex and edge at most once.
Suppose a social media platform wants to find friends within one, two, or three connection levels. BFS can efficiently explore users level by level and identify nearby connections.
Suppose a maze-solving application needs to find a path from the entrance to the exit. DFS can explore one path completely before trying alternative routes.
Graph Representation is a method of storing graph data in computer memory.
Adjacency Matrix and Adjacency List.
Adjacency List uses less memory.
Adjacency Matrix.
Breadth First Search is a graph traversal technique that explores vertices level by level.
Queue.
Depth First Search is a graph traversal technique that explores depth before breadth.
Stack or Recursion.
O(V + E)
O(V + E)
A Spanning Tree is a subgraph of a connected graph that contains all the vertices of the original graph and the minimum number of edges required to connect them.
A spanning tree does not contain any cycles and ensures that every vertex remains reachable from every other vertex.
Original Graph
A
/|\
B | C
\|/
D
One possible spanning tree:
A
/ \
B C
\
D
All vertices are connected and no cycle exists.
A Minimum Spanning Tree is a spanning tree whose total edge weight is minimum among all possible spanning trees of a weighted graph.
MST is commonly used in network design, communication systems, road planning, and optimization problems.
In many real-world applications, connecting all nodes with minimum cost is required. Minimum Spanning Trees help reduce expenses while maintaining connectivity.
Prim's Algorithm is a greedy algorithm used to find the Minimum Spanning Tree of a weighted graph.
The algorithm starts with a single vertex and continuously adds the minimum-weight edge that connects a new vertex to the growing tree.
Step 1: Select any starting vertex. Step 2: Find the minimum weight edge. Step 3: Add the connected vertex. Step 4: Repeat until all vertices are included. Step 5: Stop when MST is complete.
Kruskal's Algorithm is another popular greedy algorithm used for finding the Minimum Spanning Tree.
Instead of starting from a vertex, it starts by selecting the smallest weighted edge and gradually builds the spanning tree.
Step 1: Sort all edges by weight. Step 2: Select the smallest edge. Step 3: Check for cycle formation. Step 4: Add edge if no cycle exists. Step 5: Repeat until MST contains V-1 edges.
| Prim's Algorithm | Kruskal's Algorithm |
|---|---|
| Starts with a vertex | Starts with an edge |
| Suitable for dense graphs | Suitable for sparse graphs |
| Builds one tree continuously | Builds multiple components first |
| Uses priority-based selection | Uses edge sorting |
| Generally faster for dense graphs | Generally faster for sparse graphs |
Graphs are among the most useful data structures because relationships between objects exist in almost every modern application.
Users are represented as vertices and friendships or followers are represented as edges.
Routers, switches, and computers are connected using graph structures.
Cities are vertices and roads are edges. Graph algorithms help determine the shortest route.
Web pages are connected through hyperlinks, forming large-scale web graphs.
Streaming and shopping platforms use graph relationships to recommend content and products.
Airports are represented as vertices and flight routes are represented as edges.
Knowledge graphs and search algorithms are widely used in AI applications.
Graph algorithms help determine optimal communication paths and improve network performance.
| Graph | Tree |
|---|---|
| Can contain cycles. | No cycles allowed. |
| May be disconnected. | Always connected. |
| No root node required. | Contains one root node. |
| General network structure. | Hierarchical structure. |
| Can have any number of edges. | Contains V−1 edges. |
| Graph | Linked List |
|---|---|
| Non-linear structure. | Linear structure. |
| Multiple relationships. | Sequential relationships. |
| Complex traversal. | Simple traversal. |
| Suitable for networks. | Suitable for dynamic lists. |
| Uses vertices and edges. | Uses nodes and pointers. |
A graph is a non-linear data structure consisting of vertices and edges.
A vertex is a node representing an entity in a graph.
An edge is a connection between two vertices.
Breadth First Search is a traversal technique that visits vertices level by level.
Depth First Search is a traversal technique that explores depth before breadth.
Queue.
Stack or recursion.
A graph whose edges have a specific direction.
A graph whose edges do not have directions.
A graph whose edges contain weights or costs.
A path that starts and ends at the same vertex.
A graph where every vertex is reachable from every other vertex.
A subgraph that connects all vertices without cycles.
A spanning tree with the minimum possible total edge weight.
Prim's Algorithm and Kruskal's Algorithm.
They efficiently represent relationships among data.
A matrix-based graph representation technique.
A list-based graph representation technique.
O(V + E)
O(V + E)
Graph Data Structure is one of the most important non-linear data structures used in modern computing. It provides an efficient way to represent and analyze relationships among objects. Concepts such as graph representation, BFS, DFS, spanning trees, and minimum spanning trees form the foundation of many advanced algorithms used in networking, artificial intelligence, transportation systems, search engines, and database management. A strong understanding of graphs is essential for academic success, competitive programming, technical interviews, and software development careers.