Skip to main content

Graph Data Structure

Graph is a an data structure in computer science. that is combination of vertices (nodes) and pairs of edges. node is used to store of data information. and pair of edges is references of other node.

Graph Data Structure

In this graph is pair of vertices {V} and edges{E}.

Vertices V= {A,B,C,D,E,F}
Edges  E= {(A,B),(A,D),(A,C),(B,F),(B,E),(B,C),(D,F),(D,C)}

Graph Terminology (Basic)

Directed graph: Edge of directed is represent the connectivity and accessibility to one node to another. generally one side arrow are used in directed graph edge. arrow of edge are indicates head of edge. and non-arrow is used to tail of the edge.

Directed Graph

Possible to access Tail node to head node. or in other word tail node edge reference is point to head node. So help of tail node are possible to visit head node.

A->B
A->E
B->E
B->C
C->D
D->B
D->E

Undirected graph: Edge of this graph is unordered. So help of edges is possible to visit other connected node in both directions.

Undirected Graph 
A->B and B->A or = A<->B
A->C and C->A or = A<->C
B->C and C->B or = B<->C
B->D and D->B or = B<->D
D->C and C->D or = D<->C

Bi-directional graph is an undirected graph.

Path: Edge of vertices are represent the path of the nodes.

Cycle

Cyclic Graph

Complete Graph

Complete Graph

Connected one node to all other node by edges it is called complete graph.

Implementation of graph

There are two common way to implement graph data in programmatically. Adjacency matrix and Adjacency list. Adjacency matrix is represented as 2d array of Nx2 nodes. That is simplest form of matrix representation. for example given undirected graph contain following nodes.

adjacency list graph

This graph is represented of Adjacency matrix in following way.

//C Graph represented by Adjacency List
#include<stdio.h>
int size=5;
void setData(int node[size][size]){
    if(size>0){
        int row=0,col=0;
        for(row;row<size;row++){
            for(col=0;col<size;col++){
                node[row][col]=0;
            }
        }
    }
}
void addEdge(int node[size][size],int start,int end){

    if(size>start && size>end){
        node[start][end]=1;
        node[end][start]=1;
    }else{
        printf("Invalid nodes location\n");
    }
}
void printGraph(int node[size][size]){
    if(size>0){
        int row=0,col=0;
        printf(" Graph Nodes");
        for(row;row<size;row++){
            printf("\n vertex %d: ",row );
            for(col=0;col<size;col++){
                printf("  %d",node[row][col]);
            }
        }
    }
}
void adjacencyNode(int node[size][size]){
    if(size>0){
        int row=0,col=0;
        
        for(row;row<size;row++){
            printf("\n Adjacency Matrix of vertex %d: ",row );
            for(col=0;col<size;col++){
                if(node[row][col]==1){
                    printf("  %d",col);
                }
            
            }
        }
    }
}
int main(){
      int node[size][size];
        //First set node keys
        setData(node); 
        //Connected two node with Edges
        addEdge(node,0,1);
        addEdge(node,0,4);
        addEdge(node,0,3);
        addEdge(node,1,3);

        addEdge(node,1,0);
        addEdge(node,2,4);
        addEdge(node,3,1);
        addEdge(node,3,4);

        addEdge(node,4,0);
        addEdge(node,4,2);
        addEdge(node,4,3);
        printGraph(node);
        adjacencyNode(node);
    
    return 0;
}

Output

 Graph Nodes
 vertex 0:   0  1  0  1  1
 vertex 1:   1  0  0  1  0
 vertex 2:   0  0  0  0  1
 vertex 3:   1  1  0  0  1
 vertex 4:   1  0  1  1  0
 Adjacency Matrix of vertex 0:   1  3  4
 Adjacency Matrix of vertex 1:   0  3
 Adjacency Matrix of vertex 2:   4
 Adjacency Matrix of vertex 3:   0  1  4
 Adjacency Matrix of vertex 4:   0  2  3
//C++ Graph represented by Adjacency Matrix
#include<iostream>
using namespace std;

class Graph{
    int **node;
  int size;//number of nodes
public:
    Graph(int);
    void addEdge(int,int);
    void printGraph();
};
Graph::Graph(int size){
    this->size=size;
    //take bool data when use true false
    //set number of nodes
    node=new int*[size];//
    for(int i=0;i<size;i++){
        //create inner array
        node[i]=new int [size]; 
        //set default value
        for(int j=0;j<size;j++){
            node[i][j]=0;
        }
    }
}

//Add Edge from Two given Nodes
void Graph ::addEdge(int start ,int end){
    //add edge form start to end
    if(start<size && end <size){
            node[start][end]=1;
    }else{
        //not valid Vertices
        cout<<"Invalid Node Vertices "<< start<<" "<<end;
    }
}
//Display Adjacency list of vertex
void Graph::printGraph(){
    if(size>0 && node!=NULL){
    
        for(int i=0;i<size;i++){
            cout<<"\n Node "<<i<<" : ";
            for(int j=0;j<size;j++){
                    cout<<" "<<node[i][j];
            }
        }
    }else{
        cout<<"Empty Graph"<<endl;
    }
}
int main(){
    //Create Object
    Graph g(5);
    //Connected two node with Edges
    g.addEdge(0,1);
    g.addEdge(0,4);
    g.addEdge(0,3);
    g.addEdge(1,3);

    g.addEdge(1,0);
    g.addEdge(2,4);
    g.addEdge(3,1);
    g.addEdge(3,4);

    g.addEdge(4,0);
    g.addEdge(4,2);
    g.addEdge(4,3);
    g.printGraph();
    return 0;
}
//Java Graph implemented by Adjacency Matrix
public class Graph{
    private int [][]node; 
    private int size;
    Graph(int size){
     node=new int[size][size];
     this.size=size;
    }
    public void addEdge(int start,int end){
        if(size>start&&size>end){
            node[start][end]=1;
        }
    }
    public void graphNode(){
        if(size>0 && node!=null){
            for(int row=0;row<size;row++){
                System.out.print("\nVertex "+row+" : ");
                for(int col=0;col<size;col++){
                    System.out.print("  "+node[row][col]);
                }
            }
        }
    }
    public void adjacencyNode(){
        if(size>0 && node!=null){
            for(int row=0;row<size;row++){
                System.out.print("\nAdjacency Matrix of vertex "+row+" :");
                for(int col=0;col<size;col++){
                    if(node[row][col]==1)
                    System.out.print(" "+col);
                }
            }
        }
    }
    public void freeArray(){
        if(node!=null){
            node=null;
        }
    }
    public static void main(String[] args) {
        Graph g=new Graph(5);
        g.addEdge(0,1);
        g.addEdge(0,4);
        g.addEdge(0,3);
        g.addEdge(1,3);

        g.addEdge(1,0);
        g.addEdge(2,4);
        g.addEdge(3,1);
        g.addEdge(3,4);

        g.addEdge(4,0);
        g.addEdge(4,2);
        g.addEdge(4,3);
        g.graphNode();
        g.adjacencyNode();
      g.freeArray();
    }
}
Java Graph Adjacency matrix

Output

Vertex 0 :   0  1  0  1  1
Vertex 1 :   1  0  0  1  0
Vertex 2 :   0  0  0  0  1
Vertex 3 :   0  1  0  0  1
Vertex 4 :   1  0  1  1  0
Adjacency Matrix of vertex 0 : 1 3 4
Adjacency Matrix of vertex 1 : 0 3
Adjacency Matrix of vertex 2 : 4
Adjacency Matrix of vertex 3 : 1 4
Adjacency Matrix of vertex 4 : 0 2 3
#python implement graph using Adjacency Matrix

class Graph:
  """Constructor for Graph"""
  def __init__(self, size):
    self.size=size
    self.node=[] #empty list

  def setData(self):
    if(self.size>0 and self.node!=None):
      for i in range(self.size):
        #create list a new list and apped to
        #node list
        self.node.append([0]*self.size)

  def addEdge(self,start,end):
    #S and E is two nodes
    if(self.size>start and self.size>end):
      self.node[start][end]=1
    else:
      print("Invalid nodes")
  def printGraph(self):
    if(self.size>0 and self.node!=None):
      index=0 
      while(index<self.size):
        print("\n Vertics {0} :".format(index)),
        print(self.node[index])
        index+=1
def main():
  g=Graph(5)
  g.setData(); 
  #Connected two node with Edges


  g.addEdge(0,1);
  g.addEdge(0,4);
  g.addEdge(0,3);
  g.addEdge(1,3);

  g.addEdge(1,0);
  g.addEdge(2,4);
  g.addEdge(3,1);
  g.addEdge(3,4);

  g.addEdge(4,0);
  g.addEdge(4,2);
  g.addEdge(4,3);
  g.printGraph();

if __name__ == '__main__':
  main()
Python Graph Adjacency matrix

Output

 Vertics 0 : [0, 1, 0, 1, 1]

 Vertics 1 : [1, 0, 0, 1, 0]

 Vertics 2 : [0, 0, 0, 0, 1]

 Vertics 3 : [0, 1, 0, 0, 1]

 Vertics 4 : [1, 0, 1, 1, 0]
//C# Graph represented by Adjacency Matrix
using System;

class MyGraph{
    //2d array
    public int[,]node;
    public int size;
    public MyGraph(int size){
        this.size=size;
        node=new int[size,size];
    }
    
    public void addEdge(int start,int end){
        if(this.size>start && this.size>end){
          node[start,end]=1;
        }
    }
    public void printGraph(){
        if(size>0 && node!=null){
            for(int index=0;index<size;index++){
                Console.Write("\nvertex {0} :",index);
                for(int col=0;col<size;col++){
                    Console.Write(" {0}",node[index,col]);
                }
            }
        }
    }
    public void freeNode(){
        node=null;
    }
    
}
class Program{
    
    static void Main(string[] args){
        //create object
        MyGraph g=new MyGraph(5);
      
        //Connected two node with Edges
        g.addEdge(0,1);
        g.addEdge(0,4);
        g.addEdge(0,3);
        g.addEdge(1,3);

        g.addEdge(1,0);
        g.addEdge(2,4);
        g.addEdge(3,1);
        g.addEdge(3,4);

        g.addEdge(4,0);
        g.addEdge(4,2);
        g.addEdge(4,3);
        g.printGraph();
        g.freeNode();
    }
}

Output

vertex 0 : 0 1 0 1 1
vertex 1 : 1 0 0 1 0
vertex 2 : 0 0 0 0 1
vertex 3 : 0 1 0 0 1
vertex 4 : 1 0 1 1 0

Array are used to store of store node and edges information. that reason add and modify edge information time complexity is constant O(1). But it will take N*N space to store information. N is nodes of graph. so it will not suitable of spaced point of view. adjacency list is suitable of this case.

Adjacency list

Graph adjacency list 
//C Graph represented by Adjacency List
#include<stdio.h>
#include<stdlib.h>
struct AjlistNode{
    int vId;//Vertices id
    struct AjlistNode*next;
};

struct Graph{
    int data; //node key value
    struct AjlistNode*next;
};
void setData(struct Graph *);
int size=5;

//set node key value
void setData(struct Graph*node){
    if(node!=NULL && size>0){
        int index=0;
        for(index;index<size;index++){
            //set vertic node data
      node[index].data=index;//set node key
      //Initial no AjlistNode
      //set NULL Value
      node[index].next=NULL;
    }
  }else{
    printf("Vertic Node is Empty");
  }
}
//Add Edge from Two given Nodes
void addEdge(struct Graph*node, int V ,int E){
    //add edge form V to E
    //V and E is Node location
    if(V<size && E <size){
      //first create Adjacency node
        struct AjlistNode *newEdge=(struct AjlistNode*)malloc(sizeof(struct AjlistNode));
        if(newEdge!=NULL){
            newEdge->next=node[V].next;
            newEdge->vId=E;
            node[V].next=newEdge;
        }else{
            printf("\n Memory overflow");
        }
    }else{
        //not valid Vertices
        printf("Invalid Node Vertices %d  %d", V,E);
    }
}
//Display Adjacency list of vertex
void printGraph(struct Graph*node){
    if(node!=NULL){
        struct AjlistNode *temp=NULL;
        for(int index=0;index<size;index++){
            printf("\n Adjacency list of vertex %d  :",index);
            temp=node[index].next;
            while(temp!=NULL){
                //temp->vId is graph node vertices
                //in this case temp->vId is same as 
                //node[temp->vId].data
                
                printf("  %d",node[temp->vId].data);
                temp=temp->next;
            }
        }
    }else{
        printf("Empty Graph");
    }
}
int main(){
    struct Graph*node=NULL;
    node=(struct Graph*)malloc(sizeof(struct Graph)*size);
    
    if(node==NULL){
        printf("\n Memory overflow");
    }else{
        //First set node keys
        setData(node); 
        //Connected two node with Edges
        addEdge(node,0,1);
        addEdge(node,0,4);
        addEdge(node,0,3);
        addEdge(node,1,3);

        addEdge(node,1,0);
        addEdge(node,2,4);
        addEdge(node,3,1);
        addEdge(node,3,4);

        addEdge(node,4,0);
        addEdge(node,4,2);
        addEdge(node,4,3);
        printGraph(node);
    }
        
    return 0;
}

Output

 Adjacency list of vertex 0  :  3  4  1
 Adjacency list of vertex 1  :  0  3
 Adjacency list of vertex 2  :  4
 Adjacency list of vertex 3  :  4  1
 Adjacency list of vertex 4  :  3  2  0
//C++ Graph represented by Adjacency List
#include<iostream>
using namespace std;
struct AjlistNode{
    int vId;//Vertices id
    struct AjlistNode*next;
};
struct Vertices{
    int data; //node key value
    struct AjlistNode*next;
};
class Graph{
    Vertices *node;
  int size;//number of 
public:
    Graph(int);
    void setData();
    void addEdge(int,int);
    void printGraph();
};
Graph::Graph(int size){
    this->size=size;
    //set number of nodes
    node=new Vertices[size];
}
//set node key value
void Graph:: setData(){
    if(node!=NULL){
        int index=0;
        for(index;index<size;index++){
            //set vertic node data
      node[index].data=index;//set node key
      //Initial no AjlistNode
      //set NULL Value
      node[index].next=NULL;
    }
  }else{
    cout<<"Vertic Node is Empty"<<endl;
  }
}
//Add Edge from Two given Nodes
void Graph ::addEdge(int V ,int E){
    //add edge form V to E
    //V and E is Node location
    if(V<size && E <size){
      //first create Adjacency node
        AjlistNode *newEdge=new AjlistNode;
        if(newEdge!=NULL){
            newEdge->next=node[V].next;
            newEdge->vId=E;
            node[V].next=newEdge;
        }
    }else{
        //not valid Vertices
        cout<<"Invalid Node Vertices "<< V<<" "<<E;
    }
}
//Display Adjacency list of vertex
void Graph::printGraph(){
    if(node!=NULL){
        AjlistNode *temp=NULL;
        for(int index=0;index<size;index++){
            cout<<"\n Adjacency list of vertex "<<index<<" :";
            temp=node[index].next;
            while(temp!=NULL){
                //temp->vId is graph node vertices
                //in this case temp->vId is same as 
                //node[temp->vId].data
                
                cout<<" "<<node[temp->vId].data;
                temp=temp->next;
            }
        }
    }else{
        cout<<"Empty Graph"<<endl;
    }
}
int main(){
    //Create Object
    Graph g(5);
    //First set node keys
    g.setData(); 
    //Connected two node with Edges
    g.addEdge(0,1);
    g.addEdge(0,4);
    g.addEdge(0,3);
    g.addEdge(1,3);

    g.addEdge(1,0);
    g.addEdge(2,4);
    g.addEdge(3,1);
    g.addEdge(3,4);

    g.addEdge(4,0);
    g.addEdge(4,2);
    g.addEdge(4,3);
    g.printGraph();
    return 0;
}

Output

 Adjacency list of vertex 0 : 3 4 1
 Adjacency list of vertex 1 : 0 3
 Adjacency list of vertex 2 : 4
 Adjacency list of vertex 3 : 4 1
 Adjacency list of vertex 4 : 3 2 0
//java Graph represented by Adjacency List 
public class MyGraph{
    //number of Vertices
    static int size;
    MyGraph(int size){
        //set value
        this.size=size;
    }
    static class AjlistNode{
        int id;//Vertices node key
        AjlistNode next;
    }
    static class Vertices{
        int data;
        AjlistNode next;
    }
    //set initial node value
    static void setData(Vertices node[]){
        if(node==null){
            System.out.println("\nEmpty Graph");
        }else{
            for(int index=0;index<size;index++){
                // avoid java.lang.NullPointerException
                node[index]=new Vertices(); 
                node[index].data=index;//set your data
                node[index].next=null;
            }
        }
    }
    static void addEdge(Vertices node[],int S,int E){
        if(S<size &&E<size &&node!=null){
            AjlistNode newEdge=new AjlistNode();
            newEdge.id=E;//end node
            newEdge.next=node[S].next;
            node[S].next=newEdge;
        }else{
            System.out.println("\nEmpty Graph");
        }
    }
    static void printGraph(Vertices node[]){
        if(size>0&&node!=null){
            for(int index=0;index<size;index++){
                System.out.print("\nAdjacency list of vertex "+index+" :");
                AjlistNode temp=node[index].next;
                while(temp!=null){
                    System.out.print(" "+node[temp.id].data);
                    temp=temp.next;
                }
            }
        }
    }
    
    public static void main(String[] args) {
        int totalNode=5;
        Vertices node[]=new Vertices[totalNode];
        MyGraph g=new MyGraph(totalNode);
        g.setData(node);
        //Connected two node with Edges
        g.addEdge(node,0,1);
        g.addEdge(node,0,4);
        g.addEdge(node,0,3);
        g.addEdge(node,1,3);

        g.addEdge(node,1,0);
        g.addEdge(node,2,4);
        g.addEdge(node,3,1);
        g.addEdge(node,3,4);

        g.addEdge(node,4,0);
        g.addEdge(node,4,2);
        g.addEdge(node,4,3);
        g.printGraph(node);

    }
}
Java Graph Adjacency-list

Output

Adjacency list of vertex 0 : 3 4 1
Adjacency list of vertex 1 : 0 3
Adjacency list of vertex 2 : 4
Adjacency list of vertex 3 : 4 1
Adjacency list of vertex 4 : 3 2 0
#python implement graph using Adjacency List
class AjLinkeNode:
  def __init__(self,data):
    self.id=data
    self.next=None
class Vertices:
  def __init__(self,data):
    self.data=data
    self.next=None

class Graph:
  """Constructor for Graph"""
  def __init__(self, size):
    self.size=size
    self.node=[];
  def setData(self):
    if(self.size>0 and self.node!=None):
      index=0
      while(index<self.size):
        self.node.append(Vertices(index))
        index+=1

  def addEdge(self,S,E):
    #S and E is two nodes
    if(self.size>S and self.size>E):
      new_edge=AjLinkeNode(E)
      new_edge.next=self.node[S].next
      self.node[S].next=new_edge
    else:
      print("Invalid nodes")
  def printGraph(self):
    if(self.size>0 and self.node!=None):
      index=0
      while(index<self.size):
        print("\nAdjacency list of vertex {0} :".format(index)),
        temp=self.node[index].next
        while temp!=None:
          print("  {0}".format(temp.id)),
          temp=temp.next
        index+=1;

g=Graph(5)
g.setData(); 
#Connected two node with Edges
g.addEdge(0,1);
g.addEdge(0,4);
g.addEdge(0,3);
g.addEdge(1,3);

g.addEdge(1,0);
g.addEdge(2,4);
g.addEdge(3,1);
g.addEdge(3,4);

g.addEdge(4,0);
g.addEdge(4,2);
g.addEdge(4,3);
g.printGraph();

Output

Adjacency list of vertex 0 :   3   4   1
Adjacency list of vertex 1 :   0   3
Adjacency list of vertex 2 :   4
Adjacency list of vertex 3 :   4   1
Adjacency list of vertex 4 :   3   2   0
Python Graph Adjacency-list 
//C# Graph represented by Adjacency List
using System;
class AjlistNode{
    public int key;
    public AjlistNode next;
    public AjlistNode(int key){
        this.key=key;
        this.next=null;
    }
}
class Node{
    public int data;
    public AjlistNode next;
    public Node(int data){
        this.data=data;
        this.next=null;

    }
}
class MyGraph{
    //empty array
    public Node[]node= new Node[] {};
    public int size;
    public MyGraph(int size){
        this.size=size;
        node=new Node[size];
    }
    public void setData(){
        if(size>0 && this.node!=null){
            for(int index=0;index<size;index++){
                node[index]=new Node(index);
            }
            
        }
    }
    public void addEdge(int start,int end){
        if(this.size>start && this.size>end){
            AjlistNode newEdge=new AjlistNode(end);
            newEdge.next=node[start].next;
            node[start].next=newEdge;
        }
    }
    public void printGraph(){
        if(size>0 && node.Length>0 && node!=null){
            for(int index=0;index<size;index++){
                Console.Write("\nAdjacency list of vertex {0} :",index);
                AjlistNode temp=node[index].next;
                while(temp!=null){
                    Console.Write(" "+node[temp.key].data);
                    temp=temp.next;
                }
            }
        }
    }
    
}
class Program{
    
    static void Main(string[] args){
        //create object
        MyGraph g=new MyGraph(5);
        g.setData();
        //Connected two node with Edges
        g.addEdge(0,1);
        g.addEdge(0,4);
        g.addEdge(0,3);
        g.addEdge(1,3);

        g.addEdge(1,0);
        g.addEdge(2,4);
        g.addEdge(3,1);
        g.addEdge(3,4);

        g.addEdge(4,0);
        g.addEdge(4,2);
        g.addEdge(4,3);
        g.printGraph();
    }
}

Output

Adjacency list of vertex 0 : 3 4 1
Adjacency list of vertex 1 : 0 3
Adjacency list of vertex 2 : 4
Adjacency list of vertex 3 : 4 1
Adjacency list of vertex 4 : 3 2 0
Last updated on by Kalkicode




Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment