Scribd Logo
Upload

Welcome to Scribd!

  • 75 views

    A Program To Implement Bfs Algorithm

    Uploaded by

    Gaurav Sahu
    The document contains code implementations for three graph algorithms - BFS, DFS, and Dijkstra's algorithm. The BFS code uses a queue data structure to traverse the graph level-by-level starting from a source vertex. The DFS code recursively visits all vertices reachable from a source vertex. The Dijkstra's algorithm code finds the shortest path between a source vertex and all other vertices of a weighted graph.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as DOC, PDF, TXT or read online from Scribd

    A Program To Implement Bfs Algorithm

    Uploaded by

    Gaurav Sahu
    75 views8 pages
    The document contains code implementations for three graph algorithms - BFS, DFS, and Dijkstra's algorithm. The BFS code uses a queue data structure to traverse the graph level-by-level starting from a source vertex. The DFS code recursively visits all vertices reachable from a source vertex. The Dijkstra's algorithm code finds the shortest path between a source vertex and all other vertices of a weighted graph.

    Original Description:

    c programms

    Original Title

    C Programs

    Copyright

    © Attribution Non-Commercial (BY-NC)

    Available Formats

    DOC, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    The document contains code implementations for three graph algorithms - BFS, DFS, and Dijkstra's algorithm. The BFS code uses a queue data structure to traverse the graph level-by-level starting from a source vertex. The DFS code recursively visits all vertices reachable from a source vertex. The Dijkstra's algorithm code finds the shortest path between a source vertex and all other vertices of a weighted graph.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as DOC, PDF, TXT or read online from Scribd
    Download as doc, pdf, or txt
    75 views8 pages

    A Program To Implement Bfs Algorithm

    Uploaded by

    Gaurav Sahu
    The document contains code implementations for three graph algorithms - BFS, DFS, and Dijkstra's algorithm. The BFS code uses a queue data structure to traverse the graph level-by-level starting from a source vertex. The DFS code recursively visits all vertices reachable from a source vertex. The Dijkstra's algorithm code finds the shortest path between a source vertex and all other vertices of a weighted graph.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as DOC, PDF, TXT or read online from Scribd
    Download as doc, pdf, or txt
    of 8

    A PROGRAM TO IMPLEMENT BFS ALGORITHM

    #include<stdio.h> #include<conio.h> #define MAX 10 typedef struct Q{ int R,F; int data[MAX]; }Q; int empty(Q *P); int full(Q *P); void enqueue(Q *P, int x); int dequeue(Q *P); void BFS(int); int G[MAX][MAX]; int n; void main(){ int i, j, v; clrscr(); printf("\nEnter no of vertices:: "); scanf("%d", &n); printf("\nEnter the adjecency matrix of the graph:: \n"); for(i=0;i<n;i++) for(j=0;j<n;j++) scanf("%d", &G[i][j]); printf("\nEnter the starting vertex for BFS"); scanf("%d", &v); BFS(v); getch(); } void BFS(int v){ int visited[MAX],i; Q q; q.R=q.F=1; for(i=0;i<n;i++) visited[i]=0; enqueue(&q,v); printf("\nvisit\t%d",i); visited[i]=1; while(!empty(&q)){ v=dequeue(&q); for(i=0;i<n;i++){ if(visited[i]==0&&G[v][i]!=0){ enqueue(&q,i); visited[i]=1; printf("\nvisit\t%d",i);

    KRITI SINGH 1034810037

    } } } } int empty(Q *P){ if(P->R==-1) return(1); return(0); } int full(Q *P){ if(P->R==MAX-1) return(1); return(0); } void enqueue(Q *P, int x){ if(P->R==MAX-1){ P->R=P->F=0; P->data[P->R]=x; } else{ P->R=P->R+1; P->data[P->R]=x; } } int dequeue(Q *P){ int x; x=P->data[P->F]; if(P->R==P->F){ P->R=-1; P->F=-1; } else P->F=P->F+1; return(x); }

    KRITI SINGH 1034810037

    A PROGRAM TO IMPLEMENT DFS ALGORITHM

    #include<stdio.h> #include<conio.h> KRITI SINGH 1034810037

    void DFS(int); int G[10][10], visited[10], n; void main(){ int i, j; clrscr(); printf("\nEnter no. of vertices:: "); scanf("%d", &n); printf("\nEnter adjecency matrix of the graph::\n"); for(i=0;i<n;i++) for(j=0;j<n;j++) scanf("%d", &G[i][j]); for(i=0;i<n;i++) visited[i]=0; DFS(0); } void DFS(int i){ int j; printf("\n%d",i); visited[i]=1; for(j=0;j<n;j++) if(!visited[j]&&G[i][j]==1) DFS(j); }

    KRITI SINGH 1034810037

    A PROGRAM TO IMPLEMENT DIJIKSTRA ALGORITHM


    #define INFINITY 9999 #include<stdio.h> #include<conio.h> #define MAX 10 KRITI SINGH 1034810037

    void dijikstra(int G[MAX][MAX], int n, int startnode); void main(){ int G[MAX][MAX], i, j, n, u; clrscr(); printf("\nEnter the no. of vertices:: "); scanf("%d", &n); printf("\nEnter the adjacency matrix::\n"); for(i=0;i<n;i++) for(j=0;j<n;j++) scanf("%d", &G[i][j]); printf("\nEnter the starting node:: "); scanf("%d", &u); dijikstra(G,n,u); getch(); } void dijikstra(int G[MAX][MAX], int n, int startnode){ int cost[MAX][MAX], distance[MAX], pred[MAX]; int visited[MAX], count, mindistance, nextnode, i,j; for(i=0;i<n;i++) for(j=0;j<n;j++) if(G[i][j]==0) cost[i][j]=INFINITY; else cost[i][j]=G[i][j]; for(i=0;i<n;i++){ distance[i]=cost[startnode][i]; pred[i]=startnode; visited[i]=0; } distance[startnode]=0; visited[startnode]=1; count=1; while(count<n-1){ mindistance=INFINITY; for(i=0;i<n;i++) if(distance[i]<mindistance&&!visited[i]){ mindistance=distance[i]; nextnode=i; } visited[nextnode]=1; for(i=0;i<n;i++) if(!visited[i]) if(mindistance+cost[nextnode][i]<distance[i]){ distance[i]=mindistance+cost[nextnode][i]; pred[i]=nextnode; } count++; } KRITI SINGH 1034810037

    for(i=0;i<n;i++) if(i!=startnode){ printf("\nDistance of %d = %d", i, distance[i]); printf("\nPath = %d", i); j=i; do{ j=pred[j]; printf("<-%d", j); }while(j!=startnode); } }

    KRITI SINGH 1034810037

    KRITI SINGH 1034810037

    You might also like