Data Structure and Algorithm
Introduction to Graph Data Structure with Practical Examples
 Graph Data Structure
 Components of a Graph Data Structure
 Types of Graphs
 Representation of a Graph in Graph Data Structure
 Notable Graph Algorithms
 Applications of Graph Data Structure
 Run C Programming Online Compiler
Have you ever tried to find the quickest way to get somewhere on a map when the streets are busy? And have you noticed how easy it is to see who your friends know on social media? Well, both of these things use something called a graph. It’s like a map that helps computers figure out connections and the best routes. It’s what makes finding friends and navigating streets so smooth.
¶Graph Data Structure
A graph is a collection of nodes
(vertices) interconnected by edges
. This abstraction allows us to represent various relationships between objects or entities. Formally, a graph G is defined as a pair (V, E)
, where V represents the set of vertices or nodes, and E represents the set of edges connecting these nodes.
In computer science and mathematics, the graph data structure stands as a fundamental concept with farreaching applications. From social networks to transportation systems, algorithms leveraging graphs power a wide range of modern technologies.
¶Components of a Graph Data Structure
A graph is comprised of multiple components that work together to define its structure and properties. These components include,

Vertices: Vertices are synonymous with nodes and represent the entities within the graph. They are often associated with attributes or properties that describe the entity they represent.

Edges: Edges define the relationships or connections between vertices. Depending on the type of graph, edges may be directed or undirected, indicating the flow or lack thereof between connected vertices.

Weight: In weighted graphs, edges are assigned numerical values that quantify the strength or distance between connected vertices. These weights are crucial for algorithms that optimize paths or analyze network efficiency.

Degree: The degree of a vertex refers to the number of edges incident to it. In directed graphs, vertices have both an indegree (number of incoming edges) and an outdegree (number of outgoing edges).

Cycle: A cycle in a graph occurs when a sequence of edges forms a closed loop, allowing traversal from a vertex back to itself. Detection of cycles is essential for various graph algorithms and ensures the integrity of certain graph structures.

Connected Components: In undirected graphs, connected components are subsets of vertices where each vertex is reachable from every other vertex within the same subset. Understanding connected components helps analyze the connectivity of a graph.
¶Types of Graphs
Graphs can be categorized in various ways depending on the types of nodes and edges, as well as their relationships.

Directed Graph (Digraph): Directed graphs have edges with a direction, indicating a oneway relationship between vertices. Each edge connects a source vertex to a target vertex, denoting the direction of the relationship. They are commonly used to model scenarios with asymmetric relationships, such as precedence constraints in project scheduling or flow of information in networks.

Undirected Graph: Undirected graphs have edges without a direction, implying a twoway relationship between vertices. Edges connect vertices in both directions, indicating mutual connections or interactions. They are suitable for modeling symmetric relationships, such as friendships in social networks or physical connections in transportation networks.

Weighted Graph: Weighted graphs assign numerical values known as weights to edges, representing additional information about the relationship between vertices. These weights typically denote metrics such as distance, cost, or capacity associated with traversing the edge. Weighted graphs are used in various applications, including route optimization, resource allocation, and network analysis.

Sparse Graph: Sparse graphs have relatively few edges compared to the maximum possible number of edges. They typically have a low edgetovertex ratio, resulting in a sparse representation. Examples include social networks with a large number of users but relatively few connections between them.

Dense Graph: Dense graphs contain a significant number of edges compared to the maximum possible. They have a high edgetovertex ratio, resulting in a dense representation. Examples include fully connected networks or graphs representing complete graphs.

Connected Graph: Connected graphs have a path between every pair of vertices. All vertices are reachable from any other vertex through a series of edges. They are integral in network analysis, communication systems, and transportation networks.

Disconnected Graph: Disconnected graphs consist of two or more connected components, where there is no path between vertices in different components. Disconnected graphs may arise in scenarios where there are isolated clusters of vertices with no connections to other parts of the graph.
Understanding the different types of graphs and their characteristics is essential for effectively modeling realworld scenarios and selecting appropriate algorithms for graph analysis and manipulation.
¶Representation of a Graph in Graph Data Structure
Graphs can be represented in programming using various data structures, each offering unique advantages depending on the specific requirements of the application. Here are some common representations:
¶Adjacency Matrix:
An adjacency matrix is a 2D array where each cell represents the presence or absence of an edge between two vertices. For an unweighted graph, the cell value can be either 0 or 1 to denote absence or presence of an edge respectively. For a weighted graph, the cell value can represent the weight of the edge. This representation is efficient for dense graphs but can be memoryintensive for sparse graphs.
#include <stdio.h>
#define MAX_VERTICES 5
int adjMatrix[MAX_VERTICES][MAX_VERTICES];
// Function to add an edge between vertices u and v with weight w
void addEdge(int u, int v, int w) {
adjMatrix[u][v] = w;
adjMatrix[v][u] = w; // For undirected graph, add this line
}
int main() {
// Initialize adjacency matrix with all zeros
for (int i = 0; i < MAX_VERTICES; i++) {
for (int j = 0; j < MAX_VERTICES; j++) {
adjMatrix[i][j] = 0;
}
}
// Add edges
addEdge(0, 1, 5);
addEdge(0, 2, 3);
addEdge(1, 2, 2);
addEdge(2, 4, 5);
// Add more edges as needed
// Print adjacency matrix
printf("Adjacency Matrix:\n");
for (int i = 0; i < MAX_VERTICES; i++) {
for (int j = 0; j < MAX_VERTICES; j++) {
printf("%d ", adjMatrix[i][j]);
}
printf("\n");
}
return 0;
}
Adjacency Matrix:
0 5 3 0 0
5 0 2 0 0
3 2 0 0 5
0 0 0 0 0
0 0 5 0 0
¶Adjacency List:
An adjacency list is a collection of lists or arrays where each list corresponds to a vertex in the graph. Each list contains the vertices adjacent to the corresponding vertex. This representation is more memoryefficient for sparse graphs compared to adjacency matrices. It allows for fast traversal of neighbors of a vertex.
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTICES 5
typedef struct Node {
int vertex;
int weight;
struct Node* next;
} Node;
Node* adjacencyList[MAX_VERTICES];
// Function to add an edge between vertices u and v with weight w
void addEdge(int u, int v, int w) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode>vertex = v;
newNode>weight = w;
newNode>next = adjacencyList[u];
adjacencyList[u] = newNode;
// For undirected graph, add this line
newNode = (Node*)malloc(sizeof(Node));
newNode>vertex = u;
newNode>weight = w;
newNode>next = adjacencyList[v];
adjacencyList[v] = newNode;
}
int main() {
// Initialize adjacency list with NULL
for (int i = 0; i < MAX_VERTICES; i++) {
adjacencyList[i] = NULL;
}
// Add edges
addEdge(0, 1, 5);
addEdge(0, 2, 3);
addEdge(1, 2, 2);
addEdge(2, 4, 5);
// Add more edges as needed
// Print adjacency list
printf("Adjacency List:\n");
for (int i = 0; i < MAX_VERTICES; i++) {
printf("Vertex %d: ", i);
Node* current = adjacencyList[i];
while (current != NULL) {
printf("(%d, %d) ", current>vertex, current>weight);
current = current>next;
}
printf("\n");
}
return 0;
}
Adjacency List:
Vertex 0: (2, 3) (1, 5)
Vertex 1: (2, 2) (0, 5)
Vertex 2: (4, 5) (1, 2) (0, 3)
Vertex 3:
Vertex 4: (2, 5)
¶Edge List:
An edge list is a list of tuples or objects, where each tuple/object represents an edge in the graph. Each tuple/object contains information about the vertices that the edge connects and, optionally, the weight of the edge. This representation is simple and compact, making it suitable for small graphs.
#include <stdio.h>
#define MAX_EDGES 5
typedef struct Edge {
int src, dest, weight;
} Edge;
Edge edgeList[MAX_EDGES];
int numEdges = 0;
// Function to add an edge between vertices u and v with weight w
void addEdge(int u, int v, int w) {
edgeList[numEdges].src = u;
edgeList[numEdges].dest = v;
edgeList[numEdges].weight = w;
numEdges++;
}
int main() {
// Add edges
addEdge(0, 1, 5);
addEdge(0, 2, 3);
addEdge(1, 2, 2);
addEdge(2, 4, 5);
// Print edge list
printf("Edge List:\n");
for (int i = 0; i < numEdges; i++) {
printf("Edge %d: (%d, %d) Weight: %d\n", i, edgeList[i].src, edgeList[i].dest, edgeList[i].weight);
}
return 0;
}
Edge List:
Edge 0: (0, 1) Weight: 5
Edge 1: (0, 2) Weight: 3
Edge 2: (1, 2) Weight: 2
Edge 3: (2, 4) Weight: 5
¶Notable Graph Algorithms
Graph algorithms are essential tools in computer science and are widely used in various applications. Here are some useful graph algorithms and their common applications:
¶DepthFirst Search (DFS):
 Usage: Traversing or searching a graph deeply, exploring as far as possible along each branch before backtracking.
 Applications: Topological sorting, cycle detection, pathfinding, maze solving, graph connectivity analysis.
¶BreadthFirst Search (BFS):
 Usage: Traversing or searching a graph level by level, exploring neighbors of a vertex before moving to the next level.
 Applications: Shortest path finding in unweighted graphs, connected components, network broadcasting, puzzle solving.
¶Dijkstra’s Algorithm:
 Usage: Finding the shortest path from a single source vertex to all other vertices in a graph with nonnegative edge weights.
 Applications: Navigation systems, network routing protocols, shortest path problems in transportation and logistics.
¶BellmanFord Algorithm:
 Usage: Finding the shortest path from a single source vertex to all other vertices in a graph, even with negative edge weights (but no negative cycles).
 Applications: Network routing algorithms, distributed systems, traffic management.
¶Prim’s Algorithm & Kruskal’s Algorithm:
 Usage: Finding the minimum spanning tree (MST) of a connected, undirected graph.
 Applications: Network design, clustering, sensor networks, electrical circuit design.
¶A* Search Algorithm:
 Usage: Finding the shortest path from a starting node to a target node in a weighted graph, using a heuristic function to guide the search.
 Applications: Pathfinding in video games, route planning in navigation systems, robotics, AI applications.
¶MinCost Flow Algorithm:
 Usage: Finding the flow through a flow network that minimizes the total cost of sending the flow from source to sink, considering both capacities and costs on edges.
 Applications: Transportation and logistics optimization, network routing with costs, resource allocation with variable costs.
¶Applications of Graph Data Structure
The graph data structure finds application in various domains. Here are some notable applications:

Finding Shortest Path in Map: Various graph algorithms can be applied to find the shortest path between two locations on the map..

Network Routing and Optimization: Graphs model communication and transportation networks, such as the internet, road networks, and airline routes. Algorithms like Dijkstra’s algorithm and A* search are used for finding the shortest path, while minimum spanning tree algorithms optimize network connectivity.

Social Network Analysis: Social media platforms utilize graphs to represent connections between users. Graph algorithms help identify influential users, detect communities, and recommend friends or content.

Circuit Design and Verification: Electronic circuits are represented as graphs, with components as vertices and connections as edges. Graph algorithms verify circuit correctness, optimize circuit layouts, and automate circuit design processes.

Computer Networking: Graphs model network topologies, routing tables, and dependencies between network components. Graph algorithms are employed for tasks like routing packets, detecting network anomalies, and optimizing network performance.

Data Mining and Machine Learning: Graphs are used to represent data structures like decision trees, neural networks, and knowledge graphs. Graphbased algorithms are applied in recommendation systems, fraud detection, and pattern recognition.

Semantic Web and Knowledge Representation: Graphs are used to represent semantic relationships between concepts and entities in the Semantic Web. Graphbased languages like RDF and SPARQL enable querying and reasoning over linked data.

Software Engineering: Graphs model software dependencies, control flow, and data flow within software systems. Graph algorithms aid in software analysis, debugging, and optimization.
These applications highlight the versatility and importance of graph data structures in solving complex problems across various domains, making them a fundamental concept in computer science and beyond.
¶Run C Programming Online Compiler
To make your learning more effective, exercise the coding examples in the text editor below.
Introduction to Trie Data Structure with Practical Examples
Depth First Search  DFS Algorithm with Practical Examples
All Tutorials in this playlist
Popular Tutorials
Categories

Artificial Intelligence (AI)
11

Bash Scripting
1

Bootstrap CSS
0

C Programming
14

C#
0

ChatGPT
1

Code Editor
2

Computer Engineering
3

CSS
28

Data Structure and Algorithm
18

Design Pattern in PHP
2

Design Patterns  Clean Code
1

EBook
1

Git Commands
1

HTML
19

Interview Prepration
2

Java Programming
0

JavaScript
12

Laravel PHP Framework
37

Mysql
1

Node JS
1

Online Business
0

PHP
28

Programming
8

Python
12

React Js
19

React Native
1

Redux
2

Rust Programming
15

Tailwind CSS
1

Typescript
10

Uncategorized
0

Vue JS
1

Windows Operating system
1

Woocommerce
1

WordPress Development
2
Tags
 Artificial Intelligence (AI)
 Bash Scripting
 Business
 C
 C Programming
 Csharp programming
 C++
 Code Editor
 Computer Engineering
 CSS
 Data Structure and Algorithm
 Database
 Design pattern
 Express JS
 git
 Git Commands
 github
 HTML
 Java
 JavaScript
 Laravel
 Mathematics
 MongoDB
 Mysql
 Node JS
 PHP
 Programming
 Python
 React Js
 Redux
 Rust Programming Language
 TypeScript
 Vue JS
 Windows terminal
 Woocommerce
 WordPress
 WordPress Plugin Development