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

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.

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.

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

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.

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;
}
}
}
}

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]);
}
}
}
}
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

printGraph(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 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;
}
}
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.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;
}
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]);
}
}
}
}
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.graphNode();
g.freeArray();
}
}``````

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

#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.printGraph();

if __name__ == '__main__':
main()
``````

#### 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];
}

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

``````//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){
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);
}
}
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

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 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){
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;
}
}
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.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].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.printGraph(node);

}
}``````

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

#S and E is two nodes
if(self.size>S and self.size>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.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``````
``````//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);
}

}
}
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.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``````

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