As we know data structures are very important, If we want to store data in an efficient way. So in this article, we will discuss about a data structure which is quite famous: Graph Data Structure💡. In this article, we will discuss on the following topics :
Let we start our article !🤓
Graph Data Structure is a popular non-linear data structure, consists of finite number of vertices (nodes) and edges .
And the main thing which makes Graph Data Structure so popular is its uses in real-world applications (or problems) . Examples of its applications are telephone networks, road networks, social networks, its use in circuit networks and in all those problems in which we need a shortest path between two points .
It basically used for representing random connections, from anybody to anybody (or friendship relation, opposed of Tree Data Structure which denotes parent-child relation).
Each graph is denoted by a pair of vertex set and edge set.
Graph, G ( V, E )
^ ^
| |
Vertex Edge set
set
In the above graph, set of vertices are V = {1, 2, 3, 4} and set of edges are E = {(1, 2), (2, 3), (3, 4), (4, 2)} .
As we have discussed definition of Graph, let we now discuss some terminologies used in Graphs :
Adjacent : two vertices are said to be adjacent, if an edge is present between them . Like in above Graph, 1 and 2 are adjacent.
Walk (path) : a sequence of edges, we get while travelling through the vertices of Graph . In some places, walk is said path. And in this, repetition of edge ( hence of vertex also) is allow. Like in above Graph: 1- 2, 2- 3, 3- 2 is a walk.
Path (simple path) : It is a walk, without repeated edge and vertex . In some places, path is said simple path. Like in above Graph : 1- 2, 2- 3 is a path.
Cyclic : if a path exists in the Graph, which starts and end with same vertex then Graph is said to be cyclic. It can be Directed or Undirected Graph.
Acyclic : When a Graph is not Cyclic, then it is Acyclic . It also, can be Directed or Undirected Graph .
In this section, we are going to discuss different types of Graph🤔 . And we will mainly focus on four types of Graph, which are found very commonly :
1. Undirected Graph : an Edge in Undirected Graph has no specific direction . They are bidirectional in nature .
For example : let a vertex represents an user of Facebook, and an edge as a connection between them. So, if 1 (vertex in graph) is a friend of 5 then 5 will also a friend of 1.
2. Directed Graph: an Edge in Directed Graph has a specific direction . They are also known as digraph.
In the above graph, there is an edge between 0 and 4, but because arrow head points toward 4 . we can only traverse from 0 to 4, and not from 4 to 0 .
It is same as Simplex Mode of communication, in which communication is unidirectional .
3. Weighted Graph : In weighted graph, values are associated with edges known as weights . These weights can represent cost ( like traffic in computer networks ) or length ( like distance in road networks ) .
They can be Directed or Undirected .
4. Unweighted Graph : Graph in which no weights (or values) are associated with edges . By default, all graphs are unweighted, unless values are associated with edge. They can be Directed or Undirected also .
There are some terms which are common for Undirected and Directed types of Graph but have different values, and they used frequently .
For Undirected Graph :
For Directed Graph :
we have reached on discussion of the second last topic for this article, 😎. Let we discuss, different ways to store a Graph :
1 . Adjacency Matrix : Graph is represented by a 2D-matrix, called adjacency matrix . The size of matrix is V * V, where V is number of vertex .
Each row and column represents a vertex, and value at row i column j, matrix[i][j] = 1 if there is an edge between vertex i and vertex j. otherwise matrix[i][j] = 0.
Before we discuss second way to store Graph, let we first discuss some Properties of Adjacency Matrix :
Space required : theta (V * V)
Time required for Operations :
Problem with this method ? If you look at the matrix, you find that it stores redundant information (information of vertex, having no connection).
2. Adjacency List : In this method, Graph is represented by an array of list. And an array list can be a dynamic size array or linked list .
A single index, A[i] represents the list of nodes(or vertex) adjacent to the vertex i .
Why this? The reason for using this method is that it stores only relevant information (information of only adjacent vertex). And a common operation, which used in many algorithms (like DFS and BFS), operation of finding all adjacent vertex is fast in this.
Some properties of Adjacency Lists are :
Space required :
Time required for Operations :
Searching for a node or a path (simple path) require Graph traversal . There are two ways available,in which we can find a node or traverse a Graph :
Congrats 👏, you have reached at the end of the article.
In this article, we discussed about definition of Graph Data Structure . Then we discussed some terminologies famous in Graph, and its types . We also discussed some terms of Undirected and Directed Graph . Then we discussed some storing methods of a Graph, and traversals types .
If you want to see codes related to Graph, you may have a look at this on github.
Thank you for reading it till the end 🙂 !