A Complete Introduction to Graph Data Structure by@hsnice

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 !๐ค

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

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

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 )

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 ๐ย !

Join Hacker Noon

Create your free account to unlock your custom reading experience.