Graph Traversal Breadth First Traversal using c program

Data Structures using C Language / Graph Traversal Breadth First Traversal using c program

Program

#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#define VERTICES_COUNT 50

typedef struct Graph_t {
int V;
bool adj[VERTICES_COUNT][VERTICES_COUNT];
} Graph;

// Constructor
Graph* create_Graph(int V)
{
Graph* g = malloc(sizeof(Graph));
g->V = V;

for (int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) {
g->adj[i][j] = false;
}
}
return g;
}

void destroy_Graph(Graph* g) { free(g); }
void addEdge(Graph* g, int v, int w)
{
// Add w to v’s list.
g->adj[v][w] = true;
}

// Prints BFS traversal from a given source s
void BFS(Graph* g, int s)
{
bool visited[VERTICES_COUNT];
for (int i = 0; i < g->V; i++) {
visited[i] = false;
}

int queue[VERTICES_COUNT];
int front = 0, rear = 0;

visited[s] = true;
queue[rear++] = s;

while (front != rear) {

s = queue[front++];
printf("%d ", s);

for (int adjacent = 0; adjacent < g->V;
adjacent++) {
if (g->adj[s][adjacent] && !visited[adjacent]) {
visited[adjacent] = true;
queue[rear++] = adjacent;
}
}
}
}

int main()
{
Graph* g = create_Graph(4);
addEdge(g, 0, 1);
addEdge(g, 0, 2);
addEdge(g, 1, 2);
addEdge(g, 2, 0);
addEdge(g, 2, 3);
addEdge(g, 3, 3);
printf("Breadth First Traversal " "(starting from vertex 2) \n");
BFS(g, 2);
destroy_Graph(g);
return 0;
}

Output

Breadth First Traversal (starting from vertex 2) 
2 0 3 1

Home Back