We all know graphs are strong data structures that describe real-world entity relationships. Graphs are utilised everywhere, from social networks and Google Maps to blockchains and neural networks. They are employed in various practical challenges due to their capacity to provide abstractions to real-life problems. In this post, we'll go over what graphs are in data structures and their kinds, terminologies, operations, representation, and applications.
Basics of Graph
A graph is a famous data structure used to describe the relationship between items. An entity is any object with a distinct and autonomous existence. It could be a tangible object or an abstract concept. An entity, for example, can be a person, location, or organisation about which data can be maintained.
Graphs have grown familiar in the computing world due to their ability to provide abstractions to real life and depict complicated relationships easily. As a result, graphs can be used to represent a wide range of actual situations. For example, A graph can represent a linked structure of web pages.
Every network is made up of points called vertices or nodes that are connected by lines called edges. In a network, the vertices represent entities. Edges, on the other hand, represent the relationships that exist between entities.
As a result, while nodes represent entities, edges represent relationships in a network graph. G= (V, E) illustrates a graph G with V vertices and E edges. Additional properties can be assigned to vertices and edges to describe entities and relationships. Figure 1 shows a basic graph with five nodes and six edges.
An edge in a graph may reflect a professional link between persons on LinkedIn or a personal friendship on a social networking platform such as Facebook or Instagram.
Graphs are classified as either undirected, as mentioned in (Fig 2a) or directed, as shown in (Fig 2b). An undirected graph has no direction. This signifies that there are no directions on the edges. In other words, the partnership is a two-way street—a Facebook or LinkedIn relationship, for example.
Edges of directed graphs, on the other hand, have directions associated with them. In the data structure, an asymmetric relationship between a manager and an employee or a teacher and a pupil can be represented as a directed graph.
Weighted graphs (Fig 2c) indicate actual values connected with the edges. Depending on the graph's intended application, edge weights may reflect quantities such as distance, cost, similarity, and so on.
Graph Representations
The following are the two most frequent graph formats.
Adjacency List
Other representations include the Incidence Matrix and the Incidence List. The type of graph representation used depends on the situation. It depends entirely on the procedures to be performed and the convenience of use.
Adjacency List
Now moving on towards the Adjacency list. An adjacency list is a straightforward approach to representing a graph as a list of vertices, with each vertex having a list of its adjacent vertices. A simple example of an adjacency list for an undirected graph is shown below.
Four vertices:
makefile
Copy code
0: 1 3
1: 0 2
2: 1 3
3: 0 2
Here, vertex 0 is adjacent to vertices 1 and 3, followed by vertex one is adjacent to vertices 0 and 2, and this goes on in this example.
Adjacency Matrix
Here in an adjacency matrix is a two-dimensional array that depicts a graph by storing a one at position (i,j) if an edge exists between vertex i and vertex j and 0 otherwise. In the following section, an adjacency matrix for the same undirected graph is shown below:
Copy code
0 1 2 3
0 0 1 0 1
1 1 0 1 0
2 0 1 0 1
3 1 0 1 0
Here, you will see an edge from vertex 0 to vertex one followed by an edge from vertex 1 to vertex 0, represented by a 1 in position (1,0), and so on in this example.
Incidence Matrix
Moving on towards incidence matric an incidence matrix is a two-dimensional array that stores a one at point (i,j) if vertex i is incident on edge j and 0 otherwise. An incidence matrix for the same undirected graph is shown below:
Copy code
0 1 2 3
0 1 1 0 1
1 1 0 1 0
2 0 1 1 0
3 1 0 0 1
Vertex 0 is incident on edges 0, 1, and 3 (represented by a 1 in locations (0,0), (0,1), and (0,3) in this example), vertex 1 is incident on edges 0, 2 (represented by a 1 in positions (1,0) and (1,2)), and so on.
Depending on the application, each representation has advantages and disadvantages, and selecting the proper representation can considerably impact the performance of graph algorithms.
The Adjacency Matrix
An adjacency Matrix is a popular two-dimensional array with the dimensions V x V. In this position, V is the number of vertices in a graph. Let adj[][ be the 2D array, and a slot adj[i][j] = 1 indicates that an edge exists from vertex i to vertex j. An undirected graph's adjacency matrix is always symmetric.
Weighted graphs are also represented using the Adjacency Matrix. If adj[i][j] = w, then there is an edge with weight w from vertex i to vertex j.
To use the adjacency matrix in code, we follow the approach below:
In the case of an undirected graph, we must demonstrate that an edge exists from vertex i to vertex j and vice versa. We assign adj[i][j] = 1 and adj[j][i] = 1 in code.
If an edge is from vertex i to vertex j in a directed graph, we assign adj[i][j]=1.
Look at the undirected graph below:
The adjacency matrix for the sample graph above is:
The Benefits of the Adjacency Matrix
The adjacency matrix is a data structure used in graph theory to represent the connections between graph vertices. It is a square matrix with rows and columns representing vertices and entries representing the presence or absence of edges between vertices. Here are some specific benefits of utilising an adjacency matrix:
Simple and Natural Representation: The adjacency matrix is a simple and natural way to represent a graph. By inspecting the matching entry in the Matrix, the existence or absence of an edge can be easily identified. It depicts the connectedness between vertices in a straightforward visual manner.
Edge Queries Are Efficient: The adjacency matrix enables efficient queries concerning the existence of edges between vertices. Because it only needs accessing a single element in the Matrix, determining whether an edge exists between two vertices can be done in constant time (O(1)).
Efficient Storage: In many circumstances, the adjacency matrix can be more space-efficient than other graph representations. If the graph is dense (with many edges), the Matrix will have a lot of non-zero entries, resulting in efficient storage. Furthermore, if the graph is undirected, the Matrix is symmetric, allowing additional storage optimisations.
Support for Edge Weights: The adjacency matrix can be expanded to support weighted graphs. Instead of only recording a binary number for the existence or absence of an edge, matrix entries can also hold the edge's weight. This is very beneficial when working with edge-weighted algorithms, such as shortest-path algorithms.
Efficient Neighbourhood: Efficient Neighbourhood Queries are possible thanks to the adjacency matrix. Finding all of a vertex's nearby vertices (i.e., neighbours) in linear time (O(V)), where V is the number of vertices, is possible. This is accomplished by scanning the row or column corresponding to the specified vertex.
Matrix Operations: The adjacency matrix facilitates matrix operations. Matrix multiplication can compute graph composition or the number of pathways between vertices of interest. These operations can be widely used in graph algorithms and studies.
Algorithmic Compatibility: The adjacency matrix model lends nicely to various graph algorithms and analytics. The adjacency matrix, for example, can be used to quickly implement algorithms such as depth-first search (DFS) and breadth-first search (BFS). The matrix representation is also well suited for linear algebra-based methods and graph spectral analysis.
Graph Isomorphism Testing: The adjacency matrix is frequently used in graph isomorphism testing. If two graphs have the same structure but different vertex labels, they are said to be isomorphic. It is relatively simple to establish whether two graphs are isomorphic by comparing their adjacency matrices.
Adjacency Matrix Implementation:
C++ Code
#include <bits/stdc++.h>using namespace std; int main(){ // a is the number of vertices // b is the number of edges int a, b; cin >> a >> b; int adjMat[b + 1][b + 1]; for (int i = 0; i < a; i++) { int x, y; cin >> x >> y; adjMat[x][y] = 1; adjMat[y][x] = 1; // It is for a directed graph with an edge pointing from x // to y,we just assign adjMat[x][y] as 1 } return 0;}
Java Code
import java.util.*;public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); // a is the number of vertices // b is the number of edges int b = sc.nextInt(); int a = sc.nextInt(); int[][] adjMat = new int[b + 1][b + 1]; for (int i = 0; i < a; i++) { int x = sc.nextInt(); int y = sc.nextInt(); adjMat[x][y] = 1; adjMat[y][x] = 1; // It is for a directed graph with an edge pointing // from x to y,we just assign adjMat[u][v] as 1 } }}
Adjacency List
A linked list array is employed. The array's size is equal to the number of vertices. Allow the array to be an array[]. A linked list of vertices adjacent to the ith vertex is represented by an entry array[i].
A weighted graph can also be represented using this representation. Edge weights can be described as lists of pairs.
Consider the graph below:
In the following, the adjacency list representation of the above graph is shown below.
The Benefits of Adjacency List
The adjacency list is another typical data structure used in graph theory to represent the links between vertices in a graph. Unlike the adjacency matrix, which stores graph information in a matrix, the adjacency list holds it in a collection of lists or arrays. Here are some specific benefits of utilising an adjacency list:
Better Memory Usage for Sparse Graphs: The adjacency list is extremely memory-efficient, especially for sparse graphs with substantially fewer edges than the maximum feasible number of edges. Each vertex in an adjacency list maintains a list of its neighbouring vertices, with only the essential relationships explicitly indicated. Compared to the adjacency matrix, this results in a considerable reduction in memory use.
Edge Insertion and Removal: The adjacency list performs admirably in dynamic graph circumstances where edges are often added and removed. Adding or removing an edge from an adjacency list often necessitates updating only a tiny part of the data structure, similar to adding or deleting a list entry. Compared to the adjacency matrix, which requires resizing the entire Matrix, this makes edge operations faster and more efficient.
Small Representation: Adjacency lists can be represented compactly using data structures like arrays, linked lists, or hash tables. These data structures can be optimised for memory utilisation and traversal efficiency, resulting in a compact graph representation.
Efficient Neighbourhood searches: Given a vertex, the adjacency list enables efficient searches to locate the vertex's neighbouring vertices (i.e., neighbours). A vertex's neighbours are readily available via the appropriate list in the adjacency list representation. This operation is highly efficient because it takes an average constant time (O(1)) for each neighbour.
Edge Types and Attributes Flexibility: The adjacency list may easily support different edge types and attributes. The adjacency list can store additional information for each edge, such as edge weight, direction, or any other property connected with the edge, in addition to the neighbouring vertices. Because of this adaptability, the adjacency list is ideal for a wide range of graph applications that require additional edge information.
Simple Graph Traversal: The adjacency list representation makes it simple to traverse a graph using popular algorithms such as depth-first search (DFS) and breadth-first search (BFS). The adjacency list allows direct access to a vertex's neighbours, allowing for a more efficient study of the graph structure.
Variable Vertex Degree Graphs: The adjacency list is handy for graphs with varied vertex degrees, where each vertex can have a different amount of connections. Storing such graphs in an adjacency matrix would waste memory because the Matrix would have to be fully populated, even if the vertices had few or no connections.
Efficient Graph Algorithms: The adjacency list structure allows for the efficient implementation of several graph algorithms. For example, algorithms such as Dijkstra's shortest path method and Prim's minimal spanning tree algorithm might benefit from the adjacency list's efficient neighbour queries and dynamic nature.
Adjacency List Implementation:
C++ Code
// A simple representation of graph using STL#include <bits/stdc++.h>using namespace std; // A utility function to add an edge in an// undirected graph.void addEdge(vector<int> adj[], int u, int v){ adj[u].push_back(v); adj[v].push_back(u);} // A utility function to print the adjacency list// representation of the graphvoid printGraph(vector<int> adj[], int V){ for (int v = 0; v < V; ++v) { cout << "\n Adjacency list of vertex " << v << "\n head "; for (auto x : adj[v]) cout << "-> " << x; cout << endl; }} // Driver codeint main(){ int V = 5; vector<int> adj[V]; addEdge(adj, 0, 1); addEdge(adj, 0, 4); addEdge(adj, 1, 2); addEdge(adj, 1, 3); addEdge(adj, 1, 4); addEdge(adj, 2, 3); addEdge(adj, 3, 4); printGraph(adj, V); return 0;}
Java Code
import java.util.*; class Graph { // A utility function to add an edge in an // undirected graph static void addEdge(ArrayList<ArrayList<Integer> > adj, int u, int v) { adj.get(u).add(v); adj.get(v).add(u); // for a directed graph with an edge pointing from u // to v, adj.get(u).add(v); } // A utility function to print the adjacency list // representation of the graph static void printGraph(ArrayList<ArrayList<Integer> > adj) { for (int i = 0; i < adj.size(); i++) { System.out.println("\nAdjacency list of vertex" + i); System.out.print("head"); for (int j = 0; j < adj.get(i).size(); j++) { System.out.print(" -> " + adj.get(i).get(j)); } System.out.println(); } } // Driver Code public static void main(String[] args) { // Creating a graph with five vertices int V = 5; ArrayList<ArrayList<Integer> > adj = new ArrayList<ArrayList<Integer> >(V); for (int i = 0; i < V; i++) adj.add(new ArrayList<Integer>()); // Adding edges one by one addEdge(adj, 0, 1); addEdge(adj, 0, 4); addEdge(adj, 1, 2); addEdge(adj, 1, 3); addEdge(adj, 1, 4); addEdge(adj, 2, 3); addEdge(adj, 3, 4); printGraph(adj); }}
Applications of Graphs in Real-Life
Graph data structures have numerous applications. Below are the following most popular applications:
Aids in defining the computation flow of software programs.
Google Maps is used to create transportation systems. Also, the intersection of two or more roads represents a node in Google Maps, whereas the road connecting two nodes represents an edge. The Google Maps algorithm calculates the shortest distance between two vertices using graphs.
They are used on social media sites like Facebook and LinkedIn.
Operating systems employ a Resource Allocation Graph in which each process and resource serves as a node. At the same time, we draw boundaries from resources to the assigned function.
They are used on the internet, where web pages represent nodes.
Graphs are also used in blockchains. The nodes are blocks that store several transactions, and the edges connect them.
They are used in data modelling.
Conclusion
As a fundamental data structure, graphs offer a powerful method for representing and analysing intricate interactions between items. They can represent a variety of systems, including social networks, transportation networks, and computer networks, as they are made up of nodes or vertices connected by edges.
When it comes to data analysis and problem-solving, graphs have many benefits. They make it possible to efficiently traverse and explore connected data networks, making it easier to do tasks like pathfinding, cycle detection, and connectivity determination. Graph algorithms, including breadth-first search, depth-first search, and Dijkstra's algorithm, are crucial to resolving various graph-related issues.
Understanding graph operations in data structures might help you better understand programming principles and ace your coding interview. Today's article has given you a good knowledge of a graph in a data structure, its nomenclature, types, graph operations in a data structure, representation, and applications. Read our articles on Tree data structure and Queue data structure for further information.
Comments