Representations of Graph
Here are the two most common ways to represent a graph :
- Adjacency Matrix
- Adjacency List
Adjacency Matrix
An adjacency matrix is a way of representing a graph as a matrix of boolean (0’s and 1’s).
Let’s assume there are n vertices in the graph So, create a 2D matrix adjMat[n][n] having dimension n x n.
- If there is an edge from vertex i to j, mark adjMat[i][j] as 1.
- If there is no edge from vertex i to j, mark adjMat[i][j] as 0.
Representation of Directed Graph to Adjacency Matrix:
The below figure shows a directed graph. Initially, the entire Matrix is initialized to 0. If there is an edge from source to destination, we insert 1 for that particular adjMat[destination].
Adjacency List
An array of Lists is used to store edges between two vertices. The size of array is equal to the number of vertices (i.e, n). Each index in this array represents a specific vertex in the graph. The entry at the index i of the array contains a linked list containing the vertices that are adjacent to vertex i.
Let’s assume there are n vertices in the graph So, create an array of list of size n as adjList[n].
- adjList[0] will have all the nodes which are connected (neighbour) to vertex 0.
- adjList[1] will have all the nodes which are connected (neighbour) to vertex 1 and so on.
Representation of Directed Graph to Adjacency list:
The below directed graph has 3 vertices. So, an array of list will be created of size 3, where each indices represent the vertices. Now, vertex 0 has no neighbours. For vertex 1, it has two neighbour (i.e, 0 and 2) So, insert vertices 0 and 2 at indices 1 of array. Similarly, for vertex 2, insert its neighbours in array of list.
Graph Data Structure Notes for GATE Exam [2024]
Graphs, a fundamental concept in computer science and mathematics, serve as powerful tools for modeling and solving a myriad of real-world problems. As aspirants gear up for the GATE Exam 2024, a comprehensive understanding of graph data structures becomes paramount. These notes aim to provide a concise and illuminating guide to graph data structures, unraveling the principles, representations, and algorithms associated with them, all of which are essential for mastering this topic in the GATE examination.
Table of Content
- What is Graph?
- Components of a Graph
- Breadth First Search or BFS in Graph
- Depth First Search or DFS in Graph
- Types of Graphs
- Representations of Graph
- Basic Properties of a Graph
- Applications of Graph Data Structure
- Advantages of Graph:
- Disadvantages of Graph
- Gate Previous Year Problems on Graph Data Structure
Contact Us