1.
DEPTH FIRST SEARCH
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
// Structure for a node in the adjacency list
struct Node {
int data;
struct Node* next;
};
// Structure for the adjacency list
struct List {
struct Node* head;
};
// Structure for the graph
struct Graph {
int vertices;
struct List* array;
};
// Function to create a new node
struct Node* createNode(int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
newNode->next = NULL;
return newNode;
// Function to create a graph with a given number of vertices
struct Graph* createGraph(int vertices) {
struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph));
graph->vertices = vertices;
graph->array = (struct List*)malloc(vertices * sizeof(struct List));
for (int i = 0; i < vertices; i++) {
graph->array[i].head = NULL;
return graph;
// Function to add an edge to the graph
void addEdge(struct Graph* graph, int src, int dest) {
struct Node* newNode = createNode(dest);
newNode->next = graph->array[src].head;
graph->array[src].head = newNode;
// Function to perform Depth First Search (DFS) from a given vertex
void DFS(struct Graph* graph, int vertex, bool visited[]) {
visited[vertex] = true;
printf("%d ", vertex);
struct Node* currentNode = graph->array[vertex].head;
while (currentNode) {
int adjacentVertex = currentNode->data;
if (!visited[adjacentVertex]) {
DFS(graph, adjacentVertex, visited);
currentNode = currentNode->next;
// Function to perform DFS traversal from a given vertex
void DFSTraversal(struct Graph* graph, int startVertex) {
bool* visited = (bool*)malloc(graph->vertices * sizeof(bool));
for (int i = 0; i < graph->vertices; i++) {
visited[i] = false;
DFS(graph, startVertex, visited);
free(visited);
// Function to display the graph's adjacency list
void displayGraph(struct Graph* graph) {
for (int i = 0; i < graph->vertices; i++) {
struct Node* currentNode = graph->array[i].head;
printf("Vertex %d:", i);
while (currentNode) {
printf(" -> %d", currentNode->data);
currentNode = currentNode->next;
printf(" -> NULL\n");
// Free memory for the graph
void freeGraph(struct Graph* graph) {
for (int i = 0; i < graph->vertices; i++) {
struct Node* currentNode = graph->array[i].head;
while (currentNode) {
struct Node* temp = currentNode;
currentNode = currentNode->next;
free(temp);
free(graph->array);
free(graph);
// Menu-driven interface
int main() {
int vertices, choice, src, dest;
printf("Enter the number of vertices in the graph: ");
scanf("%d", &vertices);
struct Graph* graph = createGraph(vertices);
do {
printf("\nMenu:\n");
printf("1. Add an edge\n");
printf("2. Perform DFS traversal\n");
printf("3. Display the graph\n");
printf("4. Exit\n");
printf("Enter your choice: ");
scanf("%d", &choice);
switch (choice) {
case 1:
printf("Enter source vertex (0 to %d): ", vertices - 1);
scanf("%d", &src);
printf("Enter destination vertex (0 to %d): ", vertices - 1);
scanf("%d", &dest);
if (src >= 0 && src < vertices && dest >= 0 && dest < vertices) {
addEdge(graph, src, dest);
printf("Edge added from %d to %d\n", src, dest);
} else {
printf("Invalid vertices. Please try again.\n");
break;
case 2:
printf("Enter the starting vertex for DFS (0 to %d): ", vertices - 1);
scanf("%d", &src);
if (src >= 0 && src < vertices) {
printf("Depth First Traversal starting from vertex %d:\n", src);
DFSTraversal(graph, src);
printf("\n");
} else {
printf("Invalid vertex. Please try again.\n");
break;
case 3:
printf("Displaying the graph:\n");
displayGraph(graph);
break;
case 4:
printf("Exiting the program.\n");
break;
default:
printf("Invalid choice. Please try again.\n");
} while (choice != 4);
freeGraph(graph);
return 0;
