Graph Traversal Implementation Using C - Adjacency List

Different graph traversals are
Breadth First Search
Depth First Search

Implementation 



/************************************************************
* Filename: graph_operations.c
* Description: To implement Graph Operations using Adjacency List
* Author: Sarju S
* Date: 03-Apr-2012
*************************************************************/
#include
#include
//Structure for Vertex Nodes
struct vertexNode{
int element;
int visited;
struct edgeNode *edge;
struct vertexNode *next;
};
typedef struct vertexNode vertexNode ;
vertexNode *start = NULL;


//Structure for Edge Nodes
struct edgeNode{
struct vertexNode *connectsTo;
struct edgeNode *next;
};
typedef struct edgeNode edgeNode ;
//Structure for Stack Nodes
struct stackNode
{
vertexNode *vElement;
struct stackNode *next;
};
typedef struct stackNode stackNode;
stackNode *top = NULL;


//Structure for Queue Nodes
struct queueNode
{
vertexNode *vElement;
struct queueNode *next;
};


typedef struct queueNode queueNode;
queueNode *qFront=NULL,*qRear=NULL;


//Function for creating new vertex node
void addVertex(int element){
vertexNode *newVertex,*temp;
//Allocating memory for new vertex node and initializing the values
newVertex = (vertexNode *) malloc(sizeof(vertexNode));
newVertex->element = element;
newVertex->visited =0;
newVertex->edge=NULL;
newVertex->next=NULL;
if(start==NULL){//If the graph is empty
start=newVertex;
}
else{//If the graph is not empty
temp= start;
while(temp->next!=NULL){
temp = temp->next;
}
temp->next = newVertex;
}
}


//Function for creating new edge node
void addEdge(int v1, int v2){
edgeNode *newEdge,*temp;
vertexNode *temp1,*v,*u;
temp1 = start;
/*Finding the source and destination vertex v is
the source vertex and u is the destination
vertex*/
while(temp1){
if(temp1->element == v1)
v=temp1;
if(temp1->element == v2)
u=temp1;
temp1=temp1->next;
}
newEdge = (edgeNode *) malloc(sizeof(edgeNode));
newEdge->connectsTo = u;
newEdge->next = NULL;
if(v->edge==NULL){
v->edge = newEdge;
}
else{
temp=v->edge;
while(temp->next!=NULL){
temp=temp->next;
}
temp->next=newEdge;
}

}


//Function for displaying the graph
void displayGraph(){
vertexNode *temp1;
edgeNode *temp2;
temp1=start;
while(temp1){
printf("%d->",temp1->element);
if(temp1->edge!=NULL){
temp2=temp1->edge;
while(temp2){
printf("%d->",temp2->connectsTo->element);
temp2=temp2->next;
}


}
printf("\n|\n");
printf("v\n");
temp1=temp1->next;

}

}
//Stack push function
void push(vertexNode *v){
stackNode *newStackNode;
newStackNode = (stackNode *) malloc(sizeof(stackNode));
newStackNode->vElement = v;
newStackNode->next = NULL;
if(top==NULL){
top=newStackNode;
}
else{
newStackNode->next = top;
top = newStackNode;
}


}
//Stack pop function
vertexNode * pop(){
vertexNode *temp=NULL;
if(top==NULL){
printf("\nStack is Empty");
}
else{
temp = top->vElement;
top = top->next;


}
return(temp);
}
//Function for Depth First Search
void dfs(){
vertexNode *temp;
edgeNode *temp2;
push(start);
while(top){
temp = pop();
if(temp->visited==0){
printf("%d\t",temp->element);
temp->visited = 1;
}
temp2=temp->edge;
while(temp2){
push(temp2->connectsTo);
temp2=temp2->next;
}
}
}
//Queue Insert function
void enQueue(vertexNode *v){
queueNode *tmp_ptr=NULL;
tmp_ptr=(queueNode *)malloc(sizeof(queueNode));
tmp_ptr->vElement = v;
tmp_ptr->next = NULL;
if(qFront == NULL){
qFront=tmp_ptr;
qRear=tmp_ptr;
}
else{
qRear->next=tmp_ptr;
qRear=tmp_ptr;
}

}


//Queue Delete function
vertexNode * deQueue(){
/*Delete element from Queue*/
vertexNode *temp=NULL;
temp = qFront->vElement;
if(qFront==NULL)
printf("\nThe Queue is Empty");
else if(qFront==qRear)
qFront=qRear=NULL;
else
qFront=qFront->next;

return(temp);

}
//Function for Breadth First Search
void bfs(){
vertexNode *temp;
edgeNode *temp2;
enQueue(start);
while(qFront){
temp =deQueue();
if(temp->visited==0){
printf("%d\t",temp->element);
temp->visited = 1;
}
temp2=temp->edge;
while(temp2){
enQueue(temp2->connectsTo);
temp2=temp2->next;
}
}
}
/*Function used for clering the visit tag of the
nodes to zero*/
void clearVisit(){
vertexNode *temp=start;
while(temp){
temp->visited =0;
temp=temp->next;
}
}


int main(){
int ch;
int element;
int v1,v2;
do{
printf("\n1:AddVertex\n2:AddEdge\n3:Dispaly\n4:DFS\n5:BFS\n6:Exit");
printf("\nEnter your choice:");
scanf("%d",&ch);
switch(ch){
case 1: printf("Entere the vertex to add:");
scanf("%d",&element);
addVertex(element);
break;
case 2: printf("\nEnter the vertices that are to be connected:");
scanf("%d%d",&v1,&v2);
addEdge(v1,v2);
break;
case 3: displayGraph();
break;
case 4: dfs();
clearVisit();
break;
case 5: bfs();
clearVisit();
}
}while(ch<6);
return 0;
}




OUTPUT

sjcet@sjcet-laptop:~$ gcc -Wall graph_operations.c
sjcet@sjcet-laptop:~$ ./a.out


1:AddVertex
2:AddEdge
3:Dispaly
4:DFS
5:BFS
6:Exit
Enter your choice:1
Entere the vertex to add:0


1:AddVertex
2:AddEdge
3:Dispaly
4:DFS
5:BFS
6:Exit
Enter your choice:1
Entere the vertex to add:1


1:AddVertex
2:AddEdge
3:Dispaly
4:DFS
5:BFS
6:Exit
Enter your choice:1
Entere the vertex to add:2


1:AddVertex
2:AddEdge
3:Dispaly
4:DFS
5:BFS
6:Exit
Enter your choice:1
Entere the vertex to add:3


1:AddVertex
2:AddEdge
3:Dispaly
4:DFS
5:BFS
6:Exit
Enter your choice:1
Entere the vertex to add:4


1:AddVertex
2:AddEdge
3:Dispaly
4:DFS
5:BFS
6:Exit
Enter your choice:1
Entere the vertex to add:5


1:AddVertex
2:AddEdge
3:Dispaly
4:DFS
5:BFS
6:Exit
Enter your choice:1
Entere the vertex to add:6


1:AddVertex
2:AddEdge
3:Dispaly
4:DFS
5:BFS
6:Exit
Enter your choice:1
Entere the vertex to add:7


1:AddVertex
2:AddEdge
3:Dispaly
4:DFS
5:BFS
6:Exit
Enter your choice:1
Entere the vertex to add:8


1:AddVertex
2:AddEdge
3:Dispaly
4:DFS
5:BFS
6:Exit
Enter your choice:2


Enter the vertices that are to be connected:0 1


1:AddVertex
2:AddEdge
3:Dispaly
4:DFS
5:BFS
6:Exit
Enter your choice:2


Enter the vertices that are to be connected:0 2


1:AddVertex
2:AddEdge
3:Dispaly
4:DFS
5:BFS
6:Exit
Enter your choice:2


Enter the vertices that are to be connected:1 3


1:AddVertex
2:AddEdge
3:Dispaly
4:DFS
5:BFS
6:Exit
Enter your choice:2


Enter the vertices that are to be connected:2 4


1:AddVertex
2:AddEdge
3:Dispaly
4:DFS
5:BFS
6:Exit
Enter your choice:2


Enter the vertices that are to be connected:3 5


1:AddVertex
2:AddEdge
3:Dispaly
4:DFS
5:BFS
6:Exit
Enter your choice:2


Enter the vertices that are to be connected:4 6


1:AddVertex
2:AddEdge
3:Dispaly
4:DFS
5:BFS
6:Exit
Enter your choice:2


Enter the vertices that are to be connected:4 7


1:AddVertex
2:AddEdge
3:Dispaly
4:DFS
5:BFS
6:Exit
Enter your choice:2


Enter the vertices that are to be connected:4 8


1:AddVertex
2:AddEdge
3:Dispaly
4:DFS
5:BFS
6:Exit
Enter your choice:3
0->1->2->
|
v
1->3->
|
v
2->4->
|
v
3->5->
|
v
4->6->7->8->
|
v
5->
|
v
6->
|
v
7->
|
v
8->
|
v


1:AddVertex
2:AddEdge
3:Dispaly
4:DFS
5:BFS
6:Exit
Enter your choice:4
0 2 4 8 7 6 1 3 5
1:AddVertex
2:AddEdge
3:Dispaly
4:DFS
5:BFS
6:Exit
Enter your choice:5
0 1 2 3 4 5 6 7 8
1:AddVertex
2:AddEdge
3:Dispaly
4:DFS
5:BFS
6:Exit
Enter your choice:6
sjcet@sjcet-laptop:~$ ./a.out

Read More

Postfix Evaluation using Stack

/************************************************************
* Filename: postfix_evaluation.c
* Description: postfix evaluation using stack
* Author:Sarju S
* Date: 02-Dec-2011
*************************************************************/


#include
#include
#define MAX_EXPR_SIZE 100
#define MAX_STACK_SIZE 100 


typedef enum {eos,lparen, rparen, plus, minus, times, divide,mod,operand} precedence;
char postfixExpr[MAX_EXPR_SIZE];
int stack[MAX_STACK_SIZE];
int top=-1,postfixCount=0;


void stackFull()
{
fprintf(stderr, "Stack is full cannot add elements\n");
exit(EXIT_FAILURE);
}


void stackEmpty()
{
fprintf(stderr, "Stack is empty cannot delete elements\n");
exit(EXIT_FAILURE);
}


void push(int item)
{/* add an element to stack */
if(top>=MAX_STACK_SIZE-1)
stackFull();
top++;
stack[top] = item;
}


int pop()
{/*Delete top element from the stack*/
if(top==-1)
stackEmpty();
return stack[top--];
}




precedence getToken(char *symbol)
{ /* get the next token, symbol is the character representation,which is 
returned, the token is represented by its enumerated value, which is 
returned in the function name */
*symbol = postfixExpr[postfixCount];
postfixCount++;
switch(*symbol) {
case '\0': return eos;
case '(' : return lparen;
case ')' : return rparen;
case '+' : return plus;
case '-' : return minus;
case '/' : return divide;
case '*' : return times;
case '%' : return mod;
default  : return operand;
}
}




int postfixEvaluate(){
/* evaluate a postfix expression and returns the result */
precedence token;
char symbol;
int op1,op2;
token = getToken(&symbol);
while(token!=eos){
if(token==operand)
push(symbol-'0');

else{
/* pop two operands, perform operation and 
push result to stack */
op2 = pop();
op1 = pop();
switch(token){
case plus :push(op1+op2);
  break;
case minus :push(op1-op2);
  break;
case times :push(op1*op2);
  break;
case divide :push(op1/op2);
  break;
case mod :push(op1%op2);
 
}
}
token = getToken(&symbol);
}
return pop();/* return result */
}


void main(){
int result;
printf("\nEnter the POSTFIX expression:");
scanf("%s",postfixExpr);
result=postfixEvaluate(); /* Function Call*/
printf("\nThe Result is:%d",result);
}




OUTPUT

krishnakripa@krishnakripa-K8Upgrade-VM800:~$ gcc postfix_evaluation.c
krishnakripa@krishnakripa-K8Upgrade-VM800:~$ ./a.out


Enter the POSTFIX expression:62/3-42*+


The Result is:8
krishnakripa@krishnakripa-K8Upgrade-VM800:~$ 

Read More

Infix to Postfix conversion using stack

/************************************************************
* Filename: infix_to_postfix.c
* Description: infix to postfix conversion using stack
* Author:Sarju S
* Date: 01-Dec-2011
*************************************************************/
#include
#include
#define MAX_EXPR_SIZE 100
#define MAX_STACK_SIZE 100 

typedef enum {eos,lparen, rparen, plus, minus, times, divide,mod,operand} precedence;
char infixExpr[MAX_EXPR_SIZE],postfixExpr[MAX_EXPR_SIZE];
precedence stack[MAX_STACK_SIZE];
int top=-1,infixCount=0,postfixCount=0;

void stackFull()
{
fprintf(stderr, "Stack is full cannot add elements\n");
exit(EXIT_FAILURE);
}

void stackEmpty()
{
fprintf(stderr, "Stack is empty cannot delete elements\n");
exit(EXIT_FAILURE);
}

void push(precedence item)
{/* add an element to stack */
if(top>=MAX_STACK_SIZE-1)
stackFull();
top++;
stack[top] = item;
}

precedence pop()
{/*Delete top element from the stack*/
if(top==-1)
stackEmpty();
return stack[top--];
}

void printToken(precedence token){
/* to print the symbol corresponding to token*/
switch(token) {
case 3 :postfixExpr[postfixCount]='+';
postfixCount++;
break;
case 4 :postfixExpr[postfixCount]='-';
postfixCount++;
break;
case 5 :postfixExpr[postfixCount]='*';
postfixCount++;
break; 
case 6 :postfixExpr[postfixCount]='/';
postfixCount++;
break;
case 7 :postfixExpr[postfixCount]='%';
postfixCount++;
}
}

precedence getToken(char *symbol)
{ /* get the next token, symbol is the character representation,which is 
returned, the token is represented by its enumerated value, which is 
returned in the function name */

*symbol = infixExpr[infixCount];
infixCount++;
switch(*symbol) {
case '\0': return eos;
case '(' : return lparen;
case ')' : return rparen;
case '+' : return plus;
case '-' : return minus;
case '/' : return divide;
case '*' : return times;
case '%' : return mod;
default  : return operand;
}
}

int checkPriority(precedence token){
switch(token) {
case plus   : 
case minus  : return 4;
case times  : 
case divide : return 6;
}

}

void infixToPostfix()
{/* output postfix of expression */
char symbol;
precedence token;
top = 0;
stack[0]= eos;
token = getToken(&symbol);
while(token!=eos){
if(token == operand){
postfixExpr[postfixCount]=symbol;
postfixCount++;
}

else if(token == rparen){
/*unstack tokens until left parenthesis */
while(stack[top]!= lparen)
printToken(pop());
pop(); /*remove left parenthesis */
}
else {
/*remove and print symbols whose in-stack precedence is greater than or 
 equal to the current tokens incoming precedence */
if(token!=1) /*Avoid Comparison of Left Paranthesis */
while(checkPriority(stack[top])>= checkPriority(token))
printToken(pop());
push(token);
}
token =getToken(&symbol);
} 
while((token = pop())!=eos)
printToken(token);
postfixExpr[postfixCount]='\0';
}

void main(){
printf("\nEnter the INFIX expression:");
scanf("%s",infixExpr);
infixToPostfix(); /* Function Call*/
printf("\nThe POSTFIX expression:");
printf("%s\n",postfixExpr);

}

OUTPUT

krishnakripa@krishnakripa-K8Upgrade-VM800:~$ gcc infix_to_postfix.c
krishnakripa@krishnakripa-K8Upgrade-VM800:~$ ./a.out

Enter the INFIX expression:((a/(b-c+d)))*(e-a)*c

The POSTFIX expression:abc-d+/ea-*c*
krishnakripa@krishnakripa-K8Upgrade-VM800:~$ ./a.out

Enter the INFIX expression:a/b-c+d*e-a*c        

The POSTFIX expression:ab/c-de*+ac*-
krishnakripa@krishnakripa-K8Upgrade-VM800:~$ 

Read More

Stack operations using array

/************************************************************
* Filename: Stack_Using_Array.c
* Description: To do stack operations using array 
* Author: Sarju S
* Date: 01-Dec-2011
*************************************************************/
#include
#include

#define MAX_STACK_SIZE 100 /*maximum stack size*/

int stack[MAX_STACK_SIZE],top=-1;/* Global Declarations */

void stackFull()
{
fprintf(stderr, "Stack is full cannot add elements\n");
exit(EXIT_FAILURE);
}

void stackEmpty()
{
fprintf(stderr, "Stack is empty cannot delete elements\n");
exit(EXIT_FAILURE);
}

void push(int item)
{/* add an element to stack */
if(top>=MAX_STACK_SIZE-1)
stackFull();
stack[++top] = item;
}

int pop()
{/*Delete top element from the stack*/
if(top==-1)
stackEmpty();
return stack[top--];

}

void display()
{
int i;
for(i=0;i<=top;i++)
printf("%d\t",stack[i]);
}

void main()
{
int ch,element;
do /* Loop for repeating the menu*/
{
printf("\nMENU\n1.PUSH \n2.POP\n3.EXIT");
printf("\nEnter Your Choice:");
scanf("%d",&ch);
switch(ch)
{
case 1: printf("\nEnter the element to add:");
scanf("%d",&element);
push(element);
printf("\nElement added is:%d",element);
printf("\nThe Current Stack is:\n");
display();
break;
case 2: element = pop();
printf("\nElement deleted is:%d",element);
printf("\nThe Current Stack is:\n");
display();

}
}while(ch<3);
}

OUTPUT

krishnakripa@krishnakripa-K8Upgrade-VM800:~$ gcc Stack_Using_Array.c
krishnakripa@krishnakripa-K8Upgrade-VM800:~$ ./a.out

MENU
1.PUSH 
2.POP
3.EXIT
Enter Your Choice:2
Stack is empty cannot delete elements
krishnakripa@krishnakripa-K8Upgrade-VM800:~$ ./a.out

MENU
1.PUSH 
2.POP
3.EXIT
Enter Your Choice:1

Enter the element to add:11

Element added is:11
The Current Stack is:
11
MENU
1.PUSH 
2.POP
3.EXIT
Enter Your Choice:1

Enter the element to add:22

Element added is:22
The Current Stack is:
11 22
MENU
1.PUSH 
2.POP
3.EXIT
Enter Your Choice:1

Enter the element to add:33

Element added is:33
The Current Stack is:
11 22 33
MENU
1.PUSH 
2.POP
3.EXIT
Enter Your Choice:2

Element deleted is:33
The Current Stack is:
11 22
MENU
1.PUSH 
2.POP
3.EXIT
Enter Your Choice:2

Element deleted is:22
The Current Stack is:
11
MENU
1.PUSH 
2.POP
3.EXIT
Enter Your Choice:2

Element deleted is:11
The Current Stack is:

MENU
1.PUSH 
2.POP
3.EXIT
Enter Your Choice:2
Stack is empty cannot delete elements

Read More