Graph In Data Structure

      ⇰ GRAPH

A graph is a non-linear data structure. It is a pictorial representation of a set of objects where some pairs of objects are connected by links. It consisting of nodes and edges. The nodes are sometimes also referred to as vertices and the edges are links that connect any two nodes or vertices in the graph. 

Therefore we can say a graph is a collection of nodes and edges in which two nodes are coonected with edges. It can be seen as a cyclic tree, where the vertices maintain any other relationship among them instead of having parent child relationship as in tree. 

Generally a graph 'G' is represented as G(V,E) , where V represents set of vertices of G  and E represents  set of edges or links of G.

following is  a graph with five vertices and seven edges. 

Graph with 5 vertices and 7 edges

We can define the above graph as G(V,E). where V={A, B, C, D, E} and E={ (A,B), (A,C), (A,D), (B,D), (C,D), (B,E), (D,E) }.

    ⇰  APPLICATIONS OF GRAPH :- 

∗  followings are some of most important applications of graph :-

∘ Social networking (Facebook).

∘ Web graphs.

∘ Product recommendation graphs.
∘ Road networks.
∘ Blockchains. 
∘ Bitcoin transaction graphs.
∘ Biological networks.

     ⇰ SOME  BASIC GRAPH TERMINOLOGIES :-

Directed edge :- An edge that is directed from one verted to another.

Undirected edge :- An edge which has no specific direction.

Directed graph :- A graph in which every edge is directed is called directed graph or digraph.

Undirected graph :- A graph in which every edge is undirected is called undirected graph.

Mixed graph:- A graph in which some of the edges are directed and some are undirected is called mixced graph.

Null graph :- A graph containing only isolated vertex or a graph without an edge is called null graph. 

Path :-The sequence of nodes that are followed in order to reach some terminal node is called path.

Closed Path :- If the initial node is same as terminal node then it is called as closed node.

Simple Path :- If all the nodes of the graph are distinct then such path P is called as simple path.

Cycle :- The path which has no repeated edges or vertices except the first and last vertices is called cycle.

Connected Graph :- A graph in which some or any path exists between every two vertices is called connected graph.

Complete Graph :- A graph in which  every node is connected with all other nodes present is called complete graph. 

Weighted Graph :- A graph in which each edge is assigned with some data such as length or weight is called weighted graph.

Degree of the Node :- A degree of a node is the number of edges that are connected with that node. A node with degree 0 is called as isolated node.

     ⇰  REPRESENTATION OF GRAPH :-

∗ There are many ways of representation of graph in memory. Some of them are as follows :-

   i >  Adjacency matrix representation.

  ii > Incidence matrix representation.

  iii > Adjacency List representation.

  iv >  Edge list representation.

 i >  Adjacency matrix representation :-  Adjacency matrix is a type of sequential representation of graph . It is used to represent which nodes are adjacent to other. We can represent a graph using matrix. The given matrix is square adjacency matrix. It contain  binary 1 ,if there is an edge in ith row to jth column. When we will try to represent an undirected graph using adjacency matrix, the matrix will be symmetric.

For undirected graph

For directed graph

ii > Incidence matrix representation :-  Incidence matrix representation is also a graph epresentation. In this representation  graph can be represented using a matrix of size, total number of vertices by total number of edges.

It means if a graph has 5 vertices and 6 edges, then it can be represented by matrix of 5X6. In this matrix, columns represent edges and rows represent vertices. This matrix is filled with either 0 or 1 or -1. Where, 0 is used to represent row edge which is not connected to column vertex. 1 is used to represent row edge which is connected as outgoing edge to column vertex. -1 is used to represent row edge which is connected as incoming edge to column vertex.

Incidence matrix representation

iii > Adjacency List representation :- The adjacency list representation is a type of graph representation .This representation is based on Linked List. In this approach, each Node is holding a list of Nodes, which are Directly connected with that vertices. At the end of list, each node is connected with the null values to show  that it is the end node of that list.This representation can also be used to represent a weighted graph. The weights of edges can be represented as lists of pairs. 

Adjacency list representation of directed graph

Adjacency list representation of undirected graph

iv >  Edge list representation :- In this graph representation we have to use  using one dimensional array . This is called the edge list. In this representation for each edge the first element is the source and the second one is the destination. For undirected graph representation the number of elements in the edge list will be doubled.

Edge list representation

click here for Basic concept of Tree

Share, Follow and please comment if you find anything incorrect, or to share more information about the topic discussed above.