A Graph is a non-linear data structure used to represent relationships and connections between different objects. Unlike arrays, stacks, queues, and linked lists, which mainly organize elements in a linear sequence, a graph focuses on how individual elements are connected to one another.
Graphs are particularly useful for representing systems in which one object can have relationships with several other objects. Social networks, road maps, computer networks, airline routes, recommendation systems, and website links are common examples of graph-based structures.
For example, in a social networking application, each person can be treated as a vertex and a friendship or following relationship can be represented by an edge. The resulting structure forms a graph that can be analyzed using different graph algorithms.
A Graph is a non-linear data structure made up of a collection of vertices and edges. A vertex represents an individual object or entity, while an edge represents a relationship or connection between two vertices.
A Graph is a collection of vertices connected by edges that represents relationships between different entities.
A graph can be represented mathematically as:
G = (V, E)
Here, V represents the set of vertices and E represents the set of edges.
A
/ \
B---C
\
D
In this example:
Many real-world problems are based on relationships rather than simple sequences. A linear data structure can store individual objects, but it does not naturally describe multiple connections between those objects.
Graphs provide a flexible way to model these relationships. Depending on the problem, edges may also contain directions, weights, or other information.
The two basic components of a graph are vertices and edges.
A Vertex, also called a node, represents an individual object or entity in the graph.
For example:
A B C D
Here A, B, C, and D are vertices.
An Edge represents a connection between two vertices.
A -------- B
The connection between A and B is an edge.
Before studying graph traversal and algorithms, it is important to understand the basic terminology used with graphs.
A vertex is an individual node or object present in a graph.
An edge connects two vertices and represents a relationship between them.
Two vertices are called adjacent when an edge directly connects them.
A -------- B
A and B are adjacent vertices.
An edge is said to be incident on a vertex when that edge is connected to the vertex.
In an undirected graph, the degree of a vertex is the number of edges directly connected to that vertex.
A
/ | \
B C D
Degree of A = 3.
A path is a sequence of vertices in which consecutive vertices are connected by edges.
A → B → C → D
The sequence represents a path from A to D.
A cycle is a closed path in which the starting vertex can be reached again after following a sequence of edges.
A → B → C → A
An undirected graph is connected when every pair of vertices has a path between them.
A ----- B | | | | C ----- D
A graph is disconnected when at least two groups of vertices cannot be reached from one another.
A ----- B C ----- D
A self-loop is an edge that starts and ends at the same vertex.
┌───┐ ↓ │ A───┘
Graphs can be classified according to the direction of their edges, the presence of weights, connectivity, and the existence of cycles.
In an Undirected Graph, an edge does not have a specific direction. If A is connected to B, the relationship can normally be followed from A to B as well as from B to A.
A -------- B
The relationship can be represented as:
A ↔ B
In a Directed Graph, every edge has a direction. A directed edge from A to B does not automatically imply an edge from B to A.
A --------> B
Directed graphs are useful for representing one-way relationships such as following systems, web links, and directed routes.
A Weighted Graph assigns a numerical value to its edges. The value may represent distance, cost, time, capacity, or another measurable quantity.
A ---- 10 ---- B
Here, 10 is the weight of the edge.
An Unweighted Graph treats its edges without assigning numerical weights to them.
A -------- B
A Cyclic Graph contains at least one cycle.
A → B ↑ ↓ C ←
The vertices form a closed route.
An Acyclic Graph contains no cycles.
A → B → C → D
A directed acyclic graph is commonly called a DAG.
A Complete Graph is a graph in which every pair of distinct vertices has a direct edge between them.
For a complete undirected graph containing n vertices, the number of edges is:
n(n - 1) / 2
A Simple Graph is a graph without self-loops and without multiple edges between the same pair of vertices.
A Multigraph may contain multiple edges connecting the same pair of vertices.
A graph diagram is useful for understanding relationships visually, but a computer needs a structured representation to store and process those relationships.
The two most commonly used graph representation techniques are:
An Adjacency Matrix represents a graph using a two-dimensional array. If a graph contains V vertices, the matrix contains V rows and V columns.
For an unweighted graph, a value such as 1 can indicate that an edge exists, while 0 can indicate that no edge exists.
A
/ \
B---C
| A | B | C | |
|---|---|---|---|
| A | 0 | 1 | 1 |
| B | 1 | 0 | 1 |
| C | 1 | 1 | 0 |
The value 1 indicates a direct connection between the corresponding vertices.
An Adjacency List stores, for every vertex, a collection of vertices directly connected to it. Lists, arrays, or linked structures can be used to maintain these neighboring vertices.
A
/ \
B---C
A → B → C B → A → C C → A → B
Only the existing connections are stored, which makes adjacency lists especially useful for sparse graphs.
| Adjacency Matrix | Adjacency List |
|---|---|
| Uses a two-dimensional structure. | Uses a collection of neighbors for each vertex. |
| Requires O(V²) space. | Requires O(V + E) space. |
| Well suited to dense graphs. | Well suited to sparse graphs. |
| Edge existence check is generally O(1). | Edge lookup depends on the neighbor list. |
| Simple representation. | Usually more space efficient. |
Several operations are performed while working with graphs.
Graph Traversal means systematically visiting vertices of a graph. Traversal is required for searching, connectivity analysis, path discovery, cycle detection, and many other graph problems.
The two fundamental traversal techniques are:
Breadth First Search explores vertices according to their distance from the starting vertex. It visits the immediate neighbors first and then proceeds to vertices at the next level.
BFS uses a Queue to maintain the order in which vertices are processed.
A
/ \
B C
/ \ \
D E F
Starting from A, one possible BFS order is:
A → B → C → D → E → F
Step 1: Select a starting vertex. Step 2: Mark the vertex as visited. Step 3: Insert it into the queue. Step 4: Remove a vertex from the queue. Step 5: Add its unvisited neighbors to the queue. Step 6: Continue until the queue becomes empty.
Depth First Search explores one branch as deeply as possible before backtracking and examining another branch.
DFS can be implemented using recursion or an explicit Stack.
A
/ \
B C
/ \ \
D E F
Starting from A, one possible DFS order is:
A → B → D → E → C → F
Step 1: Select a starting vertex. Step 2: Mark it as visited. Step 3: Move to an unvisited neighboring vertex. Step 4: Continue deeper whenever possible. Step 5: Backtrack when no unvisited neighbor remains. Step 6: Continue until all reachable vertices are visited.
| BFS | DFS |
|---|---|
| Uses a Queue. | Uses a Stack or recursion. |
| Explores level by level. | Explores deeply before backtracking. |
| Useful for shortest paths in unweighted graphs. | Useful for deep exploration and cycle-related problems. |
| Can require more memory on very wide graphs. | Memory depends strongly on traversal depth. |
| Processes the nearest undiscovered vertices first. | Follows a branch before trying another branch. |
| Algorithm | Time Complexity |
|---|---|
| BFS | O(V + E) |
| DFS | O(V + E) |
Here, V represents the number of vertices and E represents the number of edges. With an adjacency-list representation, both BFS and DFS can process the graph in O(V + E) time.
A Spanning Tree is a subgraph of a connected undirected graph that contains all of the original graph's vertices and remains connected without creating a cycle.
If a spanning tree contains V vertices, it always contains:
V - 1 edges
A Minimum Spanning Tree is a spanning tree of a connected weighted undirected graph whose total edge weight is as small as possible.
MST algorithms are useful when a system needs to connect all required locations while minimizing the overall connection cost.
Prim's Algorithm is a greedy technique for constructing a Minimum Spanning Tree. It begins with a selected vertex and repeatedly adds the lowest-weight edge that connects the current tree to a vertex outside it.
Step 1: Select a starting vertex.
Step 2: Mark it as part of the tree.
Step 3: Find the minimum-weight edge
connecting the tree to an unvisited vertex.
Step 4: Add that edge and vertex.
Step 5: Repeat until all vertices are included.
Kruskal's Algorithm builds a Minimum Spanning Tree by considering edges in increasing order of their weights. An edge is selected only when adding it does not create a cycle.
Step 1: Sort all edges by increasing weight. Step 2: Select the smallest remaining edge. Step 3: Check whether it creates a cycle. Step 4: Add the edge if it does not create a cycle. Step 5: Continue until V - 1 edges are selected.
| Prim's Algorithm | Kruskal's Algorithm |
|---|---|
| Starts from a vertex. | Starts by considering the smallest edges. |
| Grows a single tree. | Gradually combines separate components. |
| Often convenient for dense graphs. | Often convenient for sparse graphs. |
| Uses the minimum connecting edge. | Processes globally sorted edges. |
Graphs are used in many real-world systems because relationships and connections are present in almost every modern technology platform.
Users can be represented as vertices, while friendships, follows, or connections can be represented as edges.
Computers, routers, and switches can be modeled as vertices, while communication links are represented as edges.
Locations can be treated as vertices and roads can be treated as weighted edges. Graph algorithms can then be used to analyze routes.
Web pages and hyperlinks can be modeled as vertices and directed edges, allowing the relationships among pages to be analyzed.
Products, users, movies, songs, and other entities can be represented as vertices with relationships between them represented by edges.
Airports can be represented as vertices and flight routes can be represented as directed or weighted edges.
Knowledge graphs, state-space searches, and relationship-based AI systems use graph structures to represent interconnected information.
Graph algorithms can be used to determine suitable paths through a network while considering distance, cost, or other constraints.
Tasks and their dependencies can be modeled as a directed graph. When the dependency structure contains no cycles, it can be represented as a Directed Acyclic Graph.
| Graph | Tree |
|---|---|
| May contain cycles. | Does not contain cycles. |
| May be connected or disconnected. | A tree is connected. |
| Does not require a root. | A rooted tree has one root. |
| Can have different numbers of edges. | A tree with V vertices has V - 1 edges. |
| Represents general relationships. | Usually represents hierarchical relationships. |
| Graph | Linked List |
|---|---|
| Non-linear structure. | Linear structure. |
| Can have multiple connections. | Normally follows a sequential relationship. |
| Contains vertices and edges. | Contains nodes and links. |
| Traversal can follow multiple paths. | Traversal is generally sequential. |
| Useful for networks and relationships. | Useful for dynamic sequential collections. |
A graph is a non-linear data structure consisting of vertices and edges that represent objects and their relationships.
A vertex is an individual node or entity represented within a graph.
An edge is a connection between two vertices.
A directed graph is a graph in which edges have a specified direction.
An undirected graph contains edges without a specified direction.
A weighted graph assigns a numerical value such as cost, distance, or time to its edges.
Breadth First Search is a graph traversal method that explores vertices level by level using a queue.
Depth First Search explores a branch deeply before backtracking and can be implemented using recursion or a stack.
BFS uses a Queue.
DFS uses a Stack or recursion.
An adjacency matrix represents graph connections using a two-dimensional matrix.
An adjacency list stores the neighboring vertices for each vertex.
An adjacency list is generally more space efficient for sparse graphs.
A spanning tree is a connected, cycle-free subgraph containing every vertex of the original connected graph.
It contains exactly V - 1 edges.
A Minimum Spanning Tree is a spanning tree with the minimum possible total edge weight.
Prim's Algorithm and Kruskal's Algorithm.
Using an adjacency-list representation, BFS runs in O(V + E) time.
Using an adjacency-list representation, DFS runs in O(V + E) time.
Graphs are used in social networks, navigation systems, computer networks, search engines, recommendation systems, airline routes, artificial intelligence, and many other applications.
Graph Data Structure is an important non-linear data structure for modeling relationships between objects. Instead of arranging information only in a sequence, graphs allow a single entity to connect with many other entities.
The fundamental concepts of graphs include vertices, edges, adjacency, degree, paths, cycles, connectivity, and graph types. Graphs may be directed, undirected, weighted, unweighted, cyclic, acyclic, complete, or simple, depending on the characteristics of their connections.
For storing graphs in computer memory, adjacency matrices and adjacency lists are the two most common approaches. The choice between them depends on factors such as the number of vertices, number of edges, and operations that need to be performed.
BFS and DFS provide the basic techniques for exploring graph structures, while spanning-tree algorithms such as Prim's and Kruskal's help solve minimum-cost connectivity problems.
A strong understanding of Graph Data Structure is important for students learning data structures and algorithms because graphs form the foundation of many practical systems, including navigation, networking, recommendation engines, search systems, artificial intelligence, and dependency analysis.