#include <stdio.h>
#include <stdlib.h>
// Define the maximum number of vertices in the graph
#define MAX_VERTICES 10
// Structure to represent a graph
typedef struct Graph {
int numVertices; // Number of vertices
int adjMatrix[MAX_VERTICES][MAX_VERTICES]; // Adjacency matrix
} Graph;
// Function to create a graph with a given number of vertices
Graph* createGraph(int vertices) {
Graph* graph = (Graph*)malloc(sizeof(Graph));
graph->numVertices = vertices;
// Initialize the adjacency matrix with zeros
for (int i = 0; i < vertices; i++) {
for (int j = 0; j < vertices; j++) {
graph->adjMatrix[i][j] = 0;
}
}
return graph;
}
// Function to add an edge to the graph
void addEdge(Graph* graph, int src, int dest) {
graph->adjMatrix[src][dest] = 1; // Add edge from src to dest
graph->adjMatrix[dest][src] = 1; // Since the graph is undirected
}
// DFS function
void DFS(Graph* graph, int vertex, int visited[]) {
// Mark the current vertex as visited
visited[vertex] = 1;
printf("%d ", vertex); // Print the visited vertex
// Recur for all the vertices adjacent to this vertex
for (int i = 0; i < graph->numVertices; i++) {
if (graph->adjMatrix[vertex][i] == 1 && !visited[i]) {
DFS(graph, i, visited);
}
}
}
// Main function to demonstrate DFS
int main() {
Graph* graph = createGraph(5);
// Adding edges to the graph
addEdge(graph, 0, 1);
addEdge(graph, 0, 2);
addEdge(graph, 1, 3);
addEdge(graph, 1, 4);
addEdge(graph, 2, 4);
// Array to keep track of visited vertices
int visited[MAX_VERTICES] = {0};
printf("Depth First Search starting from vertex 0:\n");
DFS(graph, 0, visited);
// Free the allocated memory
free(graph);
return 0;
}
Explanation of the Program
- Graph Structure: We define a
Graphstructure that contains the number of vertices and an adjacency matrix to represent the edges. - Creating the Graph: The
createGraphfunction initializes the graph with a specified number of vertices. It allocates memory for the graph and sets all entries in the adjacency matrix to zero. - Adding Edges: The
addEdgefunction allows us to add an edge between two vertices in the graph. Since it’s an undirected graph, we update both directions in the adjacency matrix. - DFS Implementation:
- The
DFSfunction takes the graph, the current vertex, and an array to track visited vertices. It marks the current vertex as visited, prints it, and recursively visits all unvisited adjacent vertices.
- The
- Main Function: The
mainfunction demonstrates the use of the graph by creating one, adding edges, and initiating the DFS from a starting vertex (in this case, vertex 0).
Output
When the program is executed, it will output the vertices in the order they are visited during the DFS traversal:
Depth First Search starting from vertex 0:
0 1 3 4 2
Summary
This C program provides a straightforward implementation of Depth First Search using an adjacency matrix representation of a graph. DFS is a powerful algorithm for exploring graphs and has numerous applications in computer science. Understanding its mechanics lays a foundation for tackling more complex graph-related problems.
