Another program for DFS and BFS

Another implementation of DFS and BFS. Comment if you need help.

#include<stdio.h> #include<stdlib.h> //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; //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; } } struct stackNode { vertexNode *vElement; struct stackNode *next; }; typedef struct stackNode stackNode; stackNode *top = NULL; //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); } 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) { if(temp2->connectsTo->visited==0) push(temp2->connectsTo); temp2=temp2->next; } } } //Structure for Queue Nodes struct queueNode { vertexNode *vElement; struct queueNode *next; }; typedef struct queueNode queueNode; queueNode *qFront=NULL,*qRear=NULL; //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; } } } int main() { int i,num,v1,v2; do { printf("\n1.INSERT\n2.ADD EDGE\n3.BFS traversal\n4.DFS traversal\n5.DISplay\n6.exit\nenter your choice:"); scanf("%d",&i); switch(i) { case 1: printf("\nEnter vertex:\t"); scanf("%d",&num); addVertex(num); break; case 4: dfs(); break; case 2: printf("\nEnter vertices to be connected:\t"); scanf("%d%d",&v1,&v2); addEdge(v1,v2); break; case 3: bfs(); break; case 5: displayGraph(); break; case 6: break; default: printf("ERROR! Invalid Choice..\n"); } } while(i!=6); }

DFS and BFS of a tree

Program for DFS and BFS of a tree. Comment below if you need help

#include<stdio.h> int adj[50][50]; int visited[50]; void adjcreate(); void dfs(int); void bfs(int); int n; main() { int i, v, ch; adjcreate(); do { printf("\nMENU:\n1.DFS\n2.BFS\n3.Exit\n"); printf("Enter your choice:"); scanf("%d",&ch); switch (ch) { case 1: printf("\nEnter starting node for Depth First Search:"); scanf("%d",&v); for (i=1;i<=n;i++) visited[i]=0; dfs(v); break; case 2: printf("\nEnter starting node for Breadth First Search:"); scanf("%d",&v); for (i=1;i<=n;i++) visited[i]=0; bfs(v); break; case 3: break; default: printf("Wrong choice!\n"); break; } }while(ch!=3); } void adjcreate() { int i,j,ch; printf("Enter number of nodes :"); scanf("%d", &n); for(i=1;i<=n;i++) { for(j=1;j<=n;j++) { printf("\n Press 1 if %d connected to %d",i,j); scanf("%d",&ch); if(ch==1) { adj[i][j]=1; } else { adj[i][j]=0; } } } for(i=1;i<=n;i++) { for(j=1;j<=n;j++) printf(" %d ",adj[i][j]); printf("\n"); } } void dfs(int v) { int i,stack[50],top=-1,pop; top++; stack[top]=v; while(top>=0) { pop=stack[top]; top--; if(visited[pop]==0) { printf("%d ",pop); visited[pop]=1; } else continue; for(i=n;i>=1;i--) { if(adj[pop][i]==1&&visited[i]==0) { top++; stack[top]=i; } } } } void bfs(int v) { int i,front,rear; int que[50]; front=rear=-1; printf("%d ",v); visited[v]=1; rear++; front++; que[rear]=v; while(front<=rear) { v=que[front]; front++; for (i=1;i<=n;i++) { if (adj[v][i]==1&&visited[i]==0) { printf("%d ",i); visited[i]=1; rear++; que[rear]=i; } } } }