Graph Data structure
Definition: A graph G=(V,E) where V is the set of vertices and E is the set of edges.
Basic Terminologies
● Vertex (or Node): An individual data element within a graph, often represented as a dot or circle.12.5
● Edge (or Arc): A line segment connecting two vertices, representing a relationship between them.
● Adjacency: Two vertices are adjacent if there's an edge connecting them.
● Degree: The number of edges incident to a vertex. In directed graphs, this is split into:
a. In-degree: The number of edges pointing to a vertex.
b. Out-degree: The number of edges pointing from a vertex.
● Path: A sequence of connected edges and vertices from one point to another.
● Cycle: A path that begins and ends at the same vertex, without repeating any edges or intermediate vertices.
● Loop: A specific type of edge that connects a vertex to itself.
● Connected Graph: An undirected graph where there is a path between every pair of vertices.
● Disconnected Graph: A graph that is not connected, meaning at least two vertices have no path between them.
● Acyclic Graph: A graph containing no cycles.
● Tree: A connected, undirected graph with no cycles.
● Complete Graph: A graph where an edge exists between every distinct pair of vertices.
Different types of graphs are there, some of them are:
Types of graphs
● Undirected Graph: Edges have no direction; connections are bidirectional. If
A is connected to B, B is also connected to A.
● Directed Graph (Digraph): Edges have a specific direction, represented by
arrows. If an edge goes from A to B, it does not necessarily mean an edge
exists from B to A.
● Weighted Graph: Edges have assigned numerical values (weights)
representing cost, distance, time, capacity, etc.
Representations of Graph
Graphs are commonly represented in two ways:
1. Adjacency Matrix
An adjacency matrix is a 2D array of V x V vertices. Each row and column
represent a vertex.
If the value of any element a[i][j] is 1, it represents that there is an edge connecting
vertex i and vertex j.
The adjacency matrix for the graph below is,
Since it is an undirected graph, for edge (0,2), we also need to mark edge (2,0);
making the adjacency matrix symmetric about the diagonal.
2. Adjacency List
An adjacency list represents a graph as an array of linked lists.
The index of the array represents a vertex and each element in its linked list
represents the other vertices that form an edge with the vertex.
The adjacency list for the graph below is as follows:
Applications of Graph
Graph data structures are widely applied in representing and analyzing complex relationships in fields like
social networks (e.g., Facebook), navigation systems (e.g., Google Maps for shortest routes), computer
networks (devices and connections), recommendation engines (e.g., e-commerce), and biology (e.g.,
protein interactions).
Key Applications
● Social Networks: Representing users and their connections (friendships, followers) on platforms
like Facebook and LinkedIn.
● Navigation Systems: Modeling locations as nodes and roads as edges to find the shortest or
fastest path between two points, as seen in Google Maps.
● Recommendation Engines: Suggesting similar products or content to users by analyzing their past
behavior and relationships to other users and items.
● Computer Networks: Depicting the devices in a network (nodes) and the links between them
(edges) to manage and analyze network traffic.
● Biological Systems: Modeling complex interactions like protein folding, DNA sequences, and gene
regulatory networks to understand biological processes and diseases.
● Artificial Intelligence: Used in knowledge graphs to store and query complex information, and in
machine learning for tasks like pattern recognition and predictive modeling.
● Cybersecurity: Analyzing networks to detect patterns of fraud or identify malicious actors by finding
connections and clusters of suspicious activity.
● Logistics and Supply Chains: Optimizing routes and managing complex networks of resources
and transportation to improve efficiency.
● The Internet and World Wide Web: Representing web pages as nodes and hyperlinks as edges,
which is fundamental to how search engines and web crawlers work.