Experiment Name:
Write a C program to implement a Graph with following operations:
a) Create a Graph
b) Representation using Adjacency Matrix and Adjacency List
c) Implement Breadth First Search (BFS)
d) Implement Depth First Search (DFS)
Code:
#include <stdio.h>
#include <stdlib.h>
// Structure for a node in the adjacency list
struct Node {
int vertex;
struct Node* next;
};
// Structure for the graph using adjacency list
struct GraphList {
int numVertices;
struct Node** adjLists;
int* visited;
};
// Structure for the graph using adjacency matrix
struct GraphMatrix {
int numVertices;
int** adjMatrix;
};
// Function to create a node
struct Node* createNode(int v) {
struct Node* newNode = malloc(sizeof(struct Node));
newNode->vertex = v;
newNode->next = NULL;
return newNode;
}
// Function to create a graph using adjacency list
struct GraphList* createGraphList(int vertices) {
struct GraphList* graph = malloc(sizeof(struct GraphList));
graph->numVertices = vertices;
graph->adjLists = malloc(vertices * sizeof(struct Node*));
graph->visited = malloc(vertices * sizeof(int));
for (int i = 0; i < vertices; i++) {
graph->adjLists[i] = NULL;
graph->visited[i] = 0;
}
return graph;
}
// Function to create a graph using adjacency matrix
struct GraphMatrix* createGraphMatrix(int vertices) {
struct GraphMatrix* graph = malloc(sizeof(struct GraphMatrix));
graph->numVertices = vertices;
graph->adjMatrix = malloc(vertices * sizeof(int*));
for (int i = 0; i < vertices; i++) {
graph->adjMatrix[i] = malloc(vertices * sizeof(int));
for (int j = 0; j < vertices; j++) {
graph->adjMatrix[i][j] = 0;
}
}
return graph;
}
// Function to add an edge to the graph using adjacency list
void addEdgeList(struct GraphList* graph, int src, int dest) {
// Add edge from src to dest
struct Node* newNode = createNode(dest);
newNode->next = graph->adjLists[src];
graph->adjLists[src] = newNode;
// Since graph is undirected, add edge from dest to src also
newNode = createNode(src);
newNode->next = graph->adjLists[dest];
graph->adjLists[dest] = newNode;
}
// Function to add an edge to the graph using adjacency matrix
void addEdgeMatrix(struct GraphMatrix* graph, int src, int dest) {
graph->adjMatrix[src][dest] = 1;
graph->adjMatrix[dest][src] = 1; // Since the graph is undirected
}
// Function to print the graph using adjacency list
void printGraphList(struct GraphList* graph) {
for (int v = 0; v < graph->numVertices; v++) {
struct Node* temp = graph->adjLists[v];
printf("\n Vertex %d\n: ", v);
while (temp) {
printf("%d -> ", temp->vertex);
temp = temp->next;
}
printf("\n");
}
}
// Function to print the graph using adjacency matrix
void printGraphMatrix(struct GraphMatrix* graph) {
for (int i = 0; i < graph->numVertices; i++) {
for (int j = 0; j < graph->numVertices; j++) {
printf("%d ", graph->adjMatrix[i][j]);
}
printf("\n");
}
}
// BFS algorithm
void bfs(struct GraphList* graph, int startVertex) {
struct Node* adjList;
struct Node* temp;
int* visited = malloc(graph->numVertices * sizeof(int));
int* queue = malloc(graph->numVertices * sizeof(int));
int front = 0;
int rear = 0;
for (int i = 0; i < graph->numVertices; i++)
visited[i] = 0;
visited[startVertex] = 1;
queue[rear] = startVertex;
rear++;
while (front < rear) {
int currentVertex = queue[front];
front++;
printf("Visited %d\n", currentVertex);
temp = graph->adjLists[currentVertex];
while (temp) {
int adjVertex = temp->vertex;
if (visited[adjVertex] == 0) {
queue[rear] = adjVertex;
rear++;
visited[adjVertex] = 1;
}
temp = temp->next;
}
}
free(visited);
free(queue);
}
// DFS algorithm
void dfs(struct GraphList* graph, int vertex) {
struct Node* adjList = graph->adjLists[vertex];
struct Node* temp = adjList;
graph->visited[vertex] = 1;
printf("Visited %d\n", vertex);
while (temp != NULL) {
int connectedVertex = temp->vertex;
if (graph->visited[connectedVertex] == 0) {
dfs(graph, connectedVertex);
}
temp = temp->next;
}
}
// Main function
int main() {
int vertices, choice, src, dest, startVertex;
printf("Enter the number of vertices in the graph: ");
scanf("%d", &vertices);
struct GraphList* graphList = createGraphList(vertices);
struct GraphMatrix* graphMatrix = createGraphMatrix(vertices);
while (1) {
printf("\nGraph Operations:\n");
printf("1. Add Edge\n");
printf("2. Print Graph (Adjacency List)\n");
printf("3. Print Graph (Adjacency Matrix)\n");
printf("4. BFS\n");
printf("5. DFS\n");
printf("6. Exit\n");
printf("Enter your choice: ");
scanf("%d", &choice);
switch (choice) {
case 1:
printf("Enter the source and destination vertices: ");
scanf("%d %d", &src, &dest);
addEdgeList(graphList, src, dest);
addEdgeMatrix(graphMatrix, src, dest);
break;
case 2:
printf("Graph (Adjacency List):\n");
printGraphList(graphList);
break;
case 3:
printf("Graph (Adjacency Matrix):\n");
printGraphMatrix(graphMatrix);
break;
case 4:
printf("Enter the start vertex for BFS: ");
scanf("%d", &startVertex);
bfs(graphList, startVertex);
break;
case 5:
printf("Enter the start vertex for DFS: ");
scanf("%d", &startVertex);
for (int i = 0; i < vertices; i++) // Reset visited array for DFS
graphList->visited[i] = 0;
dfs(graphList, startVertex);
break;
case 6:
exit(0);
default:
printf("Invalid choice! Please try again.\n");
}
}
return 0;
}
Output:
