BFS List

-
#include<stdio.h>
#include<stdlib.h>

#define MAX 100
#define initial 1
#define waiting 2
#define visited 3

struct Node
{
int vertex;
struct Node* next;
};

int queue[MAX],front=-1,rear=-1;
int state[MAX];
struct Node* adj[MAX];

void create_graph(int n,int gtype);
void insert_queue(int v);
int delete_queue();
int isEmpty_queue();
void BFT(int n);
void BFS(int start,int n);
void add_edge(int src,int dest);
struct Node* create_node(int v);

int main()
{
int gtype,n;
printf("Enter 1 for undirected graph and -1 for directed graph:");
scanf("%d",&gtype);
printf("Enter the number of vertices:");
scanf("%d",&n);
create_graph(n,gtype);
BFT(n);
return 0;
}
void create_graph(int n,int gtype)
{
int max_edges,src,dest;
if(gtype==1)
max_edges=(n*(n-1))/2;
else if(gtype==-1)
max_edges=(n*(n-1));
for(int i=0;i<n;i++)
adj[i]=NULL;
for(int i=0;i<max_edges;i++)
{
printf("Enter edge %d (press -1 and -1 to quit):",i);
scanf("%d%d",&src,&dest);
if(src==-1&&dest==-1)
break;
if(src<0||dest<0||dest>=n||dest>=n)
{
printf("Invalid source or destination entered\n");
i--;
}
else
{
add_edge(src,dest);
if(gtype==1)
add_edge(dest,src);
}
}
printf("Adjacency list\n");
for(int i=0;i<n;i++)
{
struct Node* temp=adj[i];
printf("Vertex %d:",i);
while(temp)
{
printf("%d->",temp->vertex);
temp=temp->next;
}
printf("NULL\n");
}
}
void BFT(int n)
{
int v;
for(v=0;v<n;v++)
state[v]=initial;
printf("Enter the starting vertex:");
scanf("%d",&v);
BFS(v,n);
}
void BFS(int start,int n)
{
insert_queue(start);
state[start]=waiting;
printf("The breadth first traversal order with start vertex %d is\n",start);
while(!isEmpty_queue())
{
int v=delete_queue();
printf("%d ",v);
state[v]=visited;
struct Node* temp=adj[v];
while(temp)
{
int adjvertex=temp->vertex;
if(state[adjvertex]==initial)
{
insert_queue(adjvertex);
state[adjvertex]=waiting;
}
temp=temp->next;
}
}
}
void insert_queue(int vertex) {
    if (rear == MAX - 1) {
        printf("Queue Overflow\n");
        return;
    }
    if (front == -1)  
        front = 0;
    
    rear = rear + 1;
    queue[rear] = vertex;
}

int delete_queue() {
    int del_item;
    if (front == -1 || front > rear) {
        printf("Queue Underflow\n");
        exit(0);
    }
    del_item = queue[front];
    front = front + 1;
    return del_item;
}

int isEmpty_queue() {
    if (front == -1 || front > rear)
        return 1;
    else
        return 0;
}
void add_edge(int src,int dest)
{
struct Node* newNode=create_node(dest);
newNode->next=adj[src];
adj[src]=newNode;
}
struct Node* create_node(int v)
{
struct Node* newNode=(struct Node*)malloc(sizeof(struct Node));
newNode->vertex=v;
newNode->next=NULL;
return newNode;
}

Comments

Post a Comment

Popular posts from this blog

AVL Trees

-
#include <stdio.h> #include <stdlib.h> // Structure to represent a node in the AVL tree struct Node {     int key;     struct Node* left;     struct Node* right;     int height; }; // Function to get the height of the node int height(struct Node* N) {     if (N == NULL)         return 0;     return N->height; } // Function to get the maximum of two integers int max(int a, int b) {     return (a > b) ? a : b; } // Helper function that allocates a new node with the given key struct Node* newNode(int key) {     struct Node* node = (struct Node*)malloc(sizeof(struct Node));     node->key = key;     node->left = NULL;     node->right = NULL;     node->height = 1; // New node is initially added at leaf     return(node); } // Right rotate subtree rooted with y struct Node* rightRotate(struct Node* y) {     ...
Read more

BFS Matrix

-
#include<stdio.h> #include<stdlib.h> #define MAX 100 #define initial 1 #define waiting 2 #define visited 3 int adj[MAX][MAX];   int state[MAX];      int queue[MAX], front = -1, rear = -1;  void create_graph(int n, int gtype); void BF_Traversal(int n); void BFS(int v, int n); void insert_queue(int vertex); int delete_queue(); int isEmpty_queue(); int main() {     int n, gtype;          printf("Enter 1 for undirected graph and -1 for directed graph: ");     scanf("%d", &gtype);     printf("Enter the number of vertices: ");     scanf("%d", &n);          create_graph(n, gtype);          BF_Traversal(n);          return 0; } void create_graph(int n, int gtype) {     int max_edges, src, dest;          if (gtype == 1)         max_edges = (n * (n - 1)) /...
Read more