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: 💡. In this article, we will discuss on the following topics : Graph Data Structure 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 is a popular non-linear data structure, consists of  finite number of vertices (nodes) and edges . Graph Data Structure And the main thing which makes 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 . Graph Data Structure It basically used for representing random connections, from anybody to anybody (or friendship relation, opposed of which denotes parent-child relation). Tree Data Structure Each graph is denoted by a pair of vertex set and edge set. , G ( V, E )
           ^  ^
           | Edge Graph |
       Vertex 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 : two vertices are said to be adjacent, if an edge is present  between them . Like in above Graph, 1 and 2 are adjacent. Adjacent : 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. Walk (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. Path (simple path) : 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. Cyclic : When a Graph is not Cyclic, then it is Acyclic . It also, can be Directed or Undirected Graph . Acyclic : 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 : an Edge in Undirected Graph has no specific direction . They are bidirectional in nature . 1. Undirected Graph : 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. an Edge in Directed Graph has a specific direction . They are also known as digraph. 2. Directed Graph: 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 of communication, in which communication is unidirectional . Simplex Mode 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 ) . 3. Weighted Graph : They can be Directed or Undirected . 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 . 4. Unweighted Graph : 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 : Graph is represented by a 2D-matrix, called adjacency matrix . The size of matrix is V * V, where V is number of vertex . 1 . Adjacency Matrix : 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) If you look at the matrix, you find that it stores redundant information (information of vertex, having no connection). Problem with this method ? In this method, Graph is represented by an array of list. And an array list can be a dynamic size array or linked list . 2. Adjacency List : A single index, A[i] represents the list of nodes(or vertex) adjacent to the vertex i . 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. Why this? Some are : properties of Adjacency Lists 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 or a require Graph traversal . There are two ways available,in which we can find a node or traverse a Graph : node path (simple path) ( Depth First Search ) DFS ( Breadth First Search ) BFS 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 🙂 !

The Graph

Facebook

Connect With Me

Read My Stories

Too Long; Didn't Read

In your car, at home, or at work — Bosch technology shapes many areas of life.

A Complete Introduction to Graph Data Structure

Too Long; Didn't Read

Company Mentioned

Coin Mentioned

Himanshu Singh

About Author

TOPICS

THIS ARTICLE WAS FEATURED IN...

A Complete Introduction to Graph Data Structure

Too Long; Didn't Read

Company Mentioned

Coin Mentioned

Himanshu Singh

About Author

TOPICS

THIS ARTICLE WAS FEATURED IN...

RELATED STORIES