A Complete Introduction to Graph Data Structure

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 :

1. A short note on definition of Graph Data Structure
2. Terminologies famous of Graph
3. Different types of Graph
4. Terms important for Undirected and Directed types of Graph
5. Different ways to store a Graph
6. Types of traversals in Graph

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).

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

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

1. Undirected Graph : an Edge in Undirected Graph has no specific direction . They are bidirectional in nature .

2. Directed Graph: an Edge in Directed Graph has a specific direction . They are also known as digraph.

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 ) .

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

For Undirected Graph :

For Directed Graph :

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 .

Before we discuss second way to store Graph, let we first discuss some Properties of Adjacency Matrix :

• 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 .

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 :

• for undirected graph - theta (V+ 2*E) (as edges are bidirectional in it)
• for directed graph - theta (V + E)

• 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 :

1. DFS ( Depth First Search )
2. BFS ( Breadth First Search )

Reach The End !