A graph data structure is a powerful tool for modeling complex relationships and can be used in a variety of applications, including computer networks, social networks, and recommendation systems. In this article, we will learn about what is Graph Data Structure in detail.
Table of content
What is a Graph?
Graph Terminology
Graph Representation
Types of Graph Data Structure
Algorithm working with Graph Data Structure
What is a Graph?
A graph is a non-linear data structure that consists of a finite set of vertices (also called nodes) and edges connecting these vertices. The edges represent relationships or connections between the vertices.
The vertices in a graph can represent a variety of things, such as people in a social network, cities in a map, or tasks in a project. Each vertex is identified by a unique identifier, such as a label or number.
The edges in a graph can be either directed or undirected. In a directed graph, also known as a digraph, the edges have a direction and connect one vertex to another. Directed edges are often represented as arrows pointing from the starting vertex to the ending vertex. In an undirected graph, the edges have no direction and connect vertices in pairs.
Graph Terminology
Mathematical graphs can be represented in data structure. We can represent a graph using an array of vertices and a two-dimensional array of edges. Before we proceed further, let's familiarize ourselves with some important terms −
Vertex − Each node of the graph is represented as a vertex. In the following example, the labeled circle represents vertices. Thus, A to G are vertices. We can represent them using an array as shown in the following image. Here A can be identified by index 0. B can be identified using index 1 and so on.
Edge − Edge represents a path between two vertices or a line between two vertices. In the following example, the lines from A to B, B to C, and so on represents edges. We can use a two-dimensional array to represent an array as shown in the following image. Here AB can be represented as 1 at row 0, column 1, BC as 1 at row 1, column 2 and so on, keeping other combinations as 0.
Adjacency − Two node or vertices are adjacent if they are connected to each other through an edge. In the following example, B is adjacent to A, C is adjacent to B, and so on.
Path − Path represents a sequence of edges between the two vertices. In the following example, ABCD represents a path from A to D.
Graph Representation
The following two are the most commonly used representations of a graph.
Adjacency Matrix
Adjacency List
There are other representations also like, Incidence Matrix and Incidence List. The choice of graph representation is situation-specific. It totally depends on the type of operations to be performed and ease of use.
Adjacency Matrix:
An adjacency matrix is a way of representing a graph as a matrix of booleans (0's and 1's). A finite graph can be represented in the form of a square matrix on a computer, where the boolean value of the matrix indicates if there is a direct path between two vertices.
The adjacency matrix for the above example graph is:
Pros
The basic operations like adding an edge, removing an edge, and checking whether there is an edge from vertex i to vertex j are extremely time efficient, constant time operations.
If the graph is dense and the number of edges is large, an adjacency matrix should be the first choice. Even if the graph and the adjacency matrix is sparse, we can represent it using data structures for sparse matrices.
The biggest advantage, however, comes from the use of matrices. The recent advances in hardware enable us to perform even expensive matrix operations on the GPU.
By performing operations on the adjacent matrix, we can get important insights into the nature of the graph and the relationship between its vertices.
Cons
The VxV space requirement of the adjacency matrix makes it a memory hog. Graphs out in the wild usually don't have too many connections and this is the major reason why adjacency lists are the better choice for most tasks.
While basic operations are easy, operations like inEdges and outEdges are expensive when using the adjacency matrix representation.
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.
Here we have undirected graph
We can represent this graph in the form of a linked list on a computer as shown below.
Pros:
An adjacency list is efficient in terms of storage because we only need to store the values for the edges. For a sparse graph with millions of vertices and edges, this can mean a lot of saved space.
It also helps to find all the vertices adjacent to a vertex easily.
Cons:
Finding the adjacent list is not quicker than the adjacency matrix because all the connected nodes must be first explored to find them.
Types of Graph Data Structure
There are different types of graphs in data structures, each of which is detailed below.
1. Multi Graph
If there are numerous edges between a pair of vertices in a graph G= (V, E), the graph is referred to as a multigraph. There are no self-loops in a Multigraph.
Features:
Some of the key features of a multigraph include:
In a multigraph, it is possible to have multiple edges between the same pair of vertices. This allows for the modeling of more complex relationships, such as multiple roads between two cities or multiple relationships between the same pair of people.
In a multigraph, edges can be labeled or given names, allowing for more descriptive and meaningful relationships between vertices. For example, different edges between the same pair of vertices might represent different modes of transportation, such as car or plane.
In a multigraph, edges can also have weights or costs associated with them, just like in a weighted graph. This allows for the modeling of different costs or values associated with different edges between the same pair of vertices.
Multigraphs can be represented using adjacency matrices, adjacency lists, or other graph data structures, depending on the requirements of the application.
Multigraphs are a flexible data structure that can be used to model a wide variety of relationships, from simple pairwise relationships to complex networks with many different types of relationships.
2. Null Graph
A null graph is a type of graph data structure that has no edges and only one vertex. In other words, a null graph is a graph with no connections or relationships.
Features:
Some of the key features of a null graph include:
In a null graph, there are no edges or connections between vertices, meaning that there are no relationships or interactions in the graph.
A null graph contains only one vertex, which represents an isolated node with no connections to other nodes.
It is often used as edge cases in graph algorithms, to test the behavior of algorithms in cases where there are no edges or relationships in the graph.
3. Complete Graph
In a complete graph, every vertex is connected to every other vertex by an edge. Complete graphs are often used to model complete relationships, such as a group of people who all know each other.
Features:
Some of the key features of a complete graph include:
In a complete graph, every vertex is connected to every other vertex, meaning that there are no isolated vertices or disconnected components in the graph.
Complete graphs have a high edge density, meaning that there are many edges relative to the number of vertices.
Complete graphs are often used to model complete relationships, such as a group of people who all know each other, or a network in which every node is connected to every other node.
4. Weighted Graph
In a weighted graph, each edge has a numerical value associated with it, representing the cost or weight of traversing the edge. Weighted graphs are used in many applications, such as finding the shortest path between two vertices in a transportation network.
Features:
Some of the key features of a weighted graph include:
In a weighted graph, each edge is assigned a numerical weight that represents the cost, distance, or some other meaningful value associated with the edge.
Weighted graphs are often used in pathfinding algorithms, such as Dijkstra's algorithm, to find the shortest path between two vertices based on the edge weights.
Weighted graphs are useful for optimization problems, such as the traveling salesman problem, where the goal is to find the shortest or most efficient path that visits a set of vertices.
Weighted graphs are a flexible data structure that can be used to model a wide variety of relationships and connections, from simple pairwise relationships to complex networks.
5. Directed Graph
In a directed graph, also known as a digraph, the edges have a direction and connect one vertex to another. Directed edges are often represented as arrows pointing from the starting vertex to the ending vertex. Directed graphs are used to model asymmetrical relationships, such as the relationships between web pages in the World Wide Web.
Features:
Some of the key features of a directed graph include:
In a directed graph, the edges have a direction, meaning that the relationships between vertices are one-way.
Directed graphs are often used in pathfinding algorithms, such as Dijkstra's algorithm or A* search, to find the shortest path between two vertices in a graph.
Directed graphs are a flexible data structure that can be used to model a wide variety of relationships, from simple one-way relationships to complex networks.
Directed graphs can contain cycles, meaning that there are sequences of edges that lead back to the starting vertex.
Directed graphs can be used to perform topological sorting, which is the process of ordering the vertices in a directed acyclic graph (DAG) such that for every directed edge (u, v), vertex u comes before vertex v.
6. Undirected Graph
In an undirected graph, the edges have no direction and connect vertices in pairs. Undirected graphs are often used to model symmetrical relationships, such as friendships in a social network.
Features:
Some of the key features of an undirected graph include:
In an undirected graph, the edges do not have a direction, meaning that the relationships between vertices are two-way.
Undirected graphs are often used in pathfinding algorithms, such as breadth-first search or depth-first search, to find a path between two vertices in a graph.
Undirected graphs are a flexible data structure that can be used to model a wide variety of relationships, from simple pairwise relationships to complex networks.
Undirected graphs can contain connected components, meaning that there are groups of vertices that are all connected to each other.
Undirected graphs can contain cycles, meaning that there are sequences of edges that lead back to the starting vertex.
7. Disconnected Graph
A disconnected graph is a type of graph data structure in which there are one or more vertices that are not connected to any other vertices by edges. In other words, there are isolated vertices in the graph that have no relationship to any other vertices..
Features:
Some of the key features of a disconnected graph include:
A disconnected graph contains one or more isolated vertices, which are not connected to any other vertices by edges.
In a disconnected graph, it may not be possible to find a path between all pairs of vertices, since some vertices may be isolated and not connected to any other vertices.
Disconnected graphs are a flexible data structure that can be used to model a wide variety of relationships, from simple isolated relationships to complex networks.
Disconnected graphs are not connected, meaning that there are isolated vertices that are not connected to any other vertices.
Disconnected graphs do not contain cycles, since isolated vertices cannot form a cycle with any other vertices.
8. Cyclic Graph
In a cyclic graph, there is at least one cycle, meaning that it is possible to start at a vertex, follow a sequence of edges, and eventually return to the starting vertex. Cyclic graphs are used in many applications, such as modeling relationships in a social network.
Features:
Some of the key features of a cyclic graph include:
A cyclic graph contains at least one cycle, meaning that there is a closed loop of vertices and edges in the graph.
In a cyclic graph, it may be possible to find a path between all pairs of vertices, since there are cycles that can lead from one vertex to another.
Cyclic graphs are a flexible data structure that can be used to model a wide variety of relationships, from simple cyclic relationships to complex networks.
Cyclic graphs can be connected or disconnected, depending on the relationships between the vertices and edges in the graph.
In a directed acyclic graph (DAG), it is possible to perform topological sorting, which is the process of ordering the vertices such that for every directed edge (u, v), vertex u comes before vertex v. In a cyclic graph, topological sorting is not possible since there are cycles in the graph.
9. Acyclic Graph
In an acyclic graph, also known as a directed acyclic graph (DAG), there are no cycles. Acyclic graphs are used in many applications, such as modeling the relationships between tasks in a project or the dependencies between components in a software system.
Features:
Some of the key features of an acyclic graph include:
An acyclic graph does not contain any cycles, meaning that there are no closed loops of vertices and edges in the graph.
In an acyclic graph, it is always possible to find a path between all pairs of vertices, since there are no cycles that can block the path between vertices.
Acyclic graphs are flexible data structures that can be used to model a wide variety of relationships, from simple linear relationships to complex networks.
Acyclic graphs can be connected or disconnected, depending on the relationships between the vertices and edges in the graph.
In a directed acyclic graph (DAG), it is possible to perform topological sorting, which is the process of ordering the vertices such that for every directed edge (u, v), vertex u comes before vertex v.
Algorithms working with Graph Data Structure
There are many algorithms for working with graph data structures, including both basic and advanced algorithms. Some of the most commonly used algorithms include:
Breadth-First Search (BFS): A basic algorithm for traversing a graph and visiting all vertices in breadth-first order.
Depth-First Search (DFS): A basic algorithm for traversing a graph and visiting all vertices in depth-first order.
Dijkstra's Algorithm: An algorithm for finding the shortest path between two vertices in a weighted graph.
Kruskal's Algorithm: An algorithm for finding the minimum spanning tree in a connected, undirected graph.
Topological Sort: An algorithm for ordering the vertices in a directed acyclic graph such that for every directed edge (u, v), vertex u comes before vertex v.
Maximum Flow: An algorithm for finding the maximum flow in a flow network, which is a special type of graph data structure.
Maximum Matching: An algorithm for finding the maximum number of edges in a matching in a graph, which is a special type of graph data structure.
These are just a few of the many algorithms that can be used for working with graph data structures. The choice of algorithm depends on the specific requirements of the application and the type of graph being used.
Comments