Last Updated on May 5, 2023 by Prepbytes
A graph is a type of data structure that represents a collection of objects called vertices or nodes that are connected by an edge network. A graph’s nodes typically represent entities, and its edges represent relationships or connections between two nodes. Social networks, road networks, and computer networks are all examples of graphs used to represent real-world relationships between objects or entities. In this article, we will discuss graph representation in Data structure.
Overview of Graph Data Structure
G = (V, E) denotes a graph G with a set of V vertices and an edge set of E. A graph is composed of the following two components:
- A node is another name for a finite set of vertices.
- An edge is defined as a finite set of ordered pairs of the form (u, v).
Because (u, v) is not the same as (v, u) in a directed graph, the pair is ordered. The (u, v) pair indicates that an edge exists between vertex u and vertex v. Weight, value, or cost may be assigned to the edges.
Type of Graphs in Data Structure
Mainly, there are two types of graphs:
- Directed Graph
- Un-directed Graph
Directed Graph
A directed graph, also known as a digraph, is a type of graph in which the edges have a direction assigned to them. This means that the edges between nodes are unidirectional, with each having a distinct "start" and "end" point. In other words, an edge between two nodes in a directed graph represents a one-way relationship from the beginning node to the ending node.
An example of a directed graph is shown:
Directed graphs are frequently used to model asymmetric or directional relationships between objects, such as flow networks or one-way road networks. The in-degree of a node in a directed graph is the number of edges that point to the node, whereas the out-degree of a node is the number of edges that originate from the node.
Some standard algorithms that work on directed graphs :
- Depth-first search
- Topological sorting
- Dijkstra’s algorithm for finding the shortest path,
- Bellman-Ford algorithm for finding the shortest path with negative weights.
Undirected Graph
An undirected graph has edges that do not have a direction assigned to them. This means that node edges are bidirectional, and there is no concept of a "start" or "end" point. In other words, an edge between two nodes in an undirected graph represents a two-way relationship between the nodes, and information can flow freely in either direction along the edge.
Here’s an example of an undirected graph:
Undirected graphs are commonly used to represent symmetric or bidirectional relationships between objects, such as friendship networks or road networks with traffic flowing in either direction. In an undirected graph, the degree of a node is simply the number of edges that are incident on the node, regardless of their direction.
Some standard algorithms that work on directed graphs :
- Depth-first search
- Breadth-first search
- Kruskal’s algorithm for finding minimum spanning trees.
Graph Representation in Data Structures
A graph can be represented using three data structures-
- Adjacency matrix
- Adjacency list
- Incidence matrix
Adjacency Matrix Representation
An adjacency matrix is a type of sequential representation.
- It is used to indicate which nodes are adjacent to one another. I.e., do any edges connect nodes in a graph?
- In this representation, an NxN matrix A must be created. If an edge connects vertex i and vertex j, the corresponding element of A is ai,j = 1, otherwise, it is ai,j = 0.
- If there is a weighted graph, we can store the edge weight instead of 1s and 0s.
Directed Graph Representation
Undirected Graph Representation
Pros and Cons of the Adjacency Matrix
- Pros: Representation is simpler to implement and adhere to.
- Cons: It takes a lot of space and time to visit all of a vertex’s neighbors; we have to traverse all of the vertices in the graph, which takes a long time.
Adjacency List Representation
A linked representation is an adjacency list.
- In this representation, we keep a list of neighbors for each vertex in the graph.
- It means that each vertex in the graph has a list of its neighbors.
- Each array element points to a singly linked list of v’s neighbors, and the array is indexed by the vertex number.
Directed Graph Representation
Undirected Graph Representation
Pros and Cons of the Adjacency List
-
Pros:
- A list of adjacencies saves a lot of space.
- We can easily insert and delete items because we are using a linked list.
- Such a representation is simple to understand and clearly shows the adjacent nodes.
-
Cons: While the adjacency list allows you to test whether two vertices are adjacent, it is slower to perform this operation.
Incidence Matrix Representation
The following matrix can be used to represent a graph in incidence matrix form:
- The total number of vertices is divided by the total number of edges.
- That is, a 4X6 matrix can represent a graph with four vertices and six edges. Within this matrix, the columns represent edges and the rows represent vertices.
- This matrix is made up of 0s, 1s, and -1s.
- The row edge that is not connected to the column vertex is represented by 0.
- The row edge is represented by 1 and is an outgoing edge from the column vertex.
- -1 represents the row edge that connects to the column vertex as an incoming edge.
Directed Graph Representation
Conclusion
In this article, we have discussed how we represent a graph in a data structure. So we can represent a graph in mainly three ways: the Adjacency list, Incidence matrix and Adjacency matrix and we have also discussed in detail how these work in addition to the advantages and disadvantages of each representation.
Frequently Asked Questions (FAQs)
Q1. What are the three types of graph data structures?
Ans. An adjacency matrix, an adjacency list, or an adjacency set can all be used to represent a graph.
Q2. What is graph representation?
Ans. A graph representation is a technique used in graph theory to store graphs in a computer’s memory.
Q3. What are BFS and DFS?
Ans. BFS is an acronym that stands for Breadth First Search. DFS is an abbreviation for Depth First Search. Data structure. BFS employs a Queue to determine the shortest path. DFS uses a stack to find the shortest path.
Q4. Why do we use graph representation?
Ans. Graphs in data structures are used to represent the relationships between objects.
Q5. Which one is better, BFS or DFS?
Ans. When a user searches for vertices that remain close to any given source, BFS performs better. DFS works better when a user can find solutions away from any given source.