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)) / 2;
    else if (gtype == -1)
        max_edges = n * (n - 1);

    for (int i = 1; i <= max_edges; i++) {
        printf("Enter edge %d (to quit enter -1 -1): ", i);
        scanf("%d%d", &src, &dest);

        if (src == -1 && dest == -1)
            break;

        if (src < 0 || dest < 0 || src >= n || dest >= n) {
            printf("Invalid source or destination!\n");
            i--;
        } else {
            adj[src][dest] = 1;
            if (gtype == 1)
                adj[dest][src] = 1;  
        }
    }

    printf("Adjacency Matrix is:\n");
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++)
            printf("%4d", adj[i][j]);
        printf("\n");
    }
}

void BF_Traversal(int n) {
    int v;
    
    for (v = 0; v < n; v++)
        state[v] = initial;
    
    printf("Enter starting vertex for Breadth First Search: ");
    scanf("%d", &v);
    
    BFS(v, n);
}

void BFS(int v, int n) {
    int i;
    
    insert_queue(v);
    state[v] = waiting;
    
    printf("BFS Traversal starting from vertex %d:\n", v);
    
    while (!isEmpty_queue()) {
        v = delete_queue();
        printf("%d ", v);
        state[v] = visited;
        
        for (i = 0; i < n; i++) {
            if (adj[v][i] == 1 && state[i] == initial) {
                insert_queue(i);
                state[i] = waiting;
            }
        }
    }
    printf("\n");
}
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(1);
    }
    
    del_item = queue[front];
    front = front + 1;
    return del_item;
}
int isEmpty_queue() {
    if (front == -1 || front > rear)
        return 1;
    else
        return 0;
}

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 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):...
Read more