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 :
- A short note on definition of Graph Data Structure
- Terminologies famous of Graph
- Different types of Graph
- Terms important for Undirected and Directed types of Graph
- Different ways to store a Graph
- Types of traversals in Graph
Let we start our article !🤓
A short note on definition of Graph Data Structure
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)} .
Terminologies famous of Graph
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 .
Different types of 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 .
Terms important for Undirected and Directed types of Graph
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 :
Different ways to store a 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 :
- check if vertices u and v are adjacent = theta (1)
- Find all vertices adjacent to u = theta (V)
- Find degree of vertex u = theta (V)
- Add / Remove an Edge = theta (1)
- Add / Remove a vertex = theta (v^2)
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 :
- for undirected graph - theta (V+ 2*E) (as edges are bidirectional in it)
- for directed graph - theta (V + E)
Time required for Operations :
- check if vertices u and v are adjacent = O(V)
- find all vertices adjacent to u = theta (degree (u)) [*outdegree are considered for directed graph ]
- find degree of vertex u = theta (1)
- Add / Remove an Edge = theta(1)
- Add / Remove a vertex = O(V)
Types of traversals in Graph
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 :
- DFS ( Depth First Search )
- BFS ( Breadth First Search )
Reach The End !
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 🙂 !