Bfs,Dfs,Floyd-Warshall

C Program For Bfs,Dfs,Floyd-Warshall Source Code: #include <stdio.h> #include <stdlib.h> #define TRUE 1 #define FALSE 0 typedef struct Queue { int *arr; int f, r, size, capacity; }Queue; typedef struct Stack { int *arr; int top, capacity; }Stack; void createGraph(int G[][50], int v) { int i, j; printf("\nEnter The Adjacency Matrix: \n"); for(i = 0; i < v; i++) { for(j = 0; j < v; j++) { printf("\nBetween (%d,%d)?: ",i+1, j+1); scanf("%d",&G[i][j]); } } } int countEdge(int G[][50], int v) { int i, j, e = 0; for(i = 0; i < v; i++) for(j = 0; j < v; j++) if(G[i][j] == 1) e = e + 1; return e/2; } void printGraph(int G[][50], int v) { int i, j; for(i = 0; i < v; i++) { putchar('['); for (j = 0; j < v; j++) printf("%3d ",G[i][j]); putchar(']'); putchar('\n'); } } void DFS(int G[][50], int i, int visited[], int v) { int u; visited[i] = TRUE; for(u = 0; u < v; u++) if(G[i][u] == TRUE && visited[u] != TRUE) DFS(G, u, visited, v); } int visitAll(int G[][50], int v) { int i, visited[50], count = 0; for(i = 0; i < v; i++) visited[i] = FALSE; for(i = 0; i < v; i++) { if(visited[i] != TRUE) { ++count; DFS(G, i, visited, v); } } return count; } int isConnected(int G[][50], int v) { return ((visitAll(G, v) > 1)? FALSE : TRUE); } int countIsolated(int G[][50], int v) { int i, j, count = 0, flag; for(i = 0; i < v; i++) { flag = TRUE; for(j = 0; j < v & flag; j++) if(G[i][j] == TRUE) flag = FALSE; if(j == v & flag == TRUE) count++; } return count; } Queue *createQueue(int N) { Queue *Q = (Queue*)malloc(sizeof(Queue)); Q->capacity = N; Q->arr = (int*)malloc(sizeof(int) * Q->capacity); Q->size = 0; Q->f = 0; Q->r = Q->capacity-1; return Q; } void enqueue(Queue *Q, int item) { if(Q->size == Q->capacity) { printf("\nOverflow."); exit(-1); } Q->r = (Q->r +1) % Q->capacity; Q->arr[Q->r] = item; Q->size = Q->size + 1; } int isEmptyQueue(Queue *Q) { return (Q->size == 0); } int dequeue(Queue *Q) { int item; if(isEmptyQueue(Q)) { printf("\nEmpty."); exit(-1); } item = Q->arr[Q->f]; Q->f = (Q->f +1) % Q->capacity; Q->size = Q->size - 1; return item; } void BFS(int G[][50], int s, int v) { Queue *Q = createQueue(30); int u, w, visited[30] = {0}; enqueue(Q,s); visited[s] = TRUE; while(!isEmptyQueue(Q)) { u = dequeue(Q); printf("%d ",u); for(w = 0; w < v; w++) { if(G[u][w] == TRUE && visited[w] == FALSE) { enqueue(Q,w); visited[w] = TRUE; } } } } Stack *createStack(int capacity) { Stack *S = (Stack*)malloc(sizeof(Stack)); S->top = -1; S->capacity = capacity; S->arr = (int*)malloc(sizeof(int) * S->capacity); return S; } int isEmptyStack(Stack *S) { return (S->top == -1); } void push(Stack *S, int item) { if(S->top== S->capacity-1) { printf("\nOverslow."); exit(-1); } S->top = S->top + 1; S->arr[S->top] = item; } int pop(Stack *S) { int item; if(isEmptyStack(S)) { printf("\nEmpty."); exit(-1); } item = S->arr[S->top]; S->top = S->top - 1; return item; } void DFS(int G[][50], int s, int v) { Stack *S = createStack(30); int u, w, visited[30] = {0}; push(S,s); visited[s] = TRUE; while(!isEmptyStack(S)) { u = pop(S); printf("%d ",u); for(w = 0; w < v; w++) { if(G[w][u] == TRUE && visited[w] == FALSE) { push(S,w); visited[w] = TRUE; } } } } int min(int a, int b) { return (a>b?b:a); } void warshall(int G[][50], int v) { int P[50][50], i, j, k; for(i = 0; i < v; i++) for(j = 0; j < v; j++) P[i][j] = G[i][j]; for(k = 0; k < v; k++) for(i = 0; i < v; i++) for(j = 0; j < v; j++) P[i][j] = P[i][j] || (P[i][k] && P[k][j]); printGraph(P,v); } void floydWarshall(int G[][50], int v) { int D[50][50], i, j, k; for(i = 0; i < v; i++) for(j = 0; j < v; j++) (G[i][j] == 0) ? D[i][j] = 999 : D[i][j] = G[i][j]; for(k = 0; k < v; k++) for(i = 0; i < v; i++) for(j = 0; j < v; j++) D[i][j] = min(D[i][j],D[i][k]+D[k][j]); printGraph(D,v); } int main() { int G[50][50], v, e; printf("Enter The Number Of Vertices: "); scanf("%d",&v); createGraph(G, v); printf("\nThe Adjacency Matrix:\n\n"); printGraph(G, v); printf("\nNumber Of Edges Are: %d.",countEdge(G, v)); printf("\n\nThe Given Graph Is%sConnected.",isConnected(G, v)?" ":" Not "); printf("\n\nThere Are %d Components.",visitAll(G, v)); printf("\n\nThere Are %d Isolated Vertex.",countIsolated(G, v)); printf("\n\nThe BFS Traversal Is:"); BFS(G, 0, v); printf("\n\nThe DFS Traversal Is:"); DFS(G, 0, v); printf("\n\nFloyd-Warshall:\n"); floydWarshall(G,v); printf("\n\nWarshall:\n"); warshall(G,v); return 0; }

Tags:

Share:

0 comments