Program Structure

The program consists of several key components:

• Graph Representation: The graph is represented using an adjacency list. This is efficient for sparse graphs.
• DFS Function: A recursive function that visits nodes and explores as far as possible along each branch before backtracking.
• Main Function: Initializes the graph and starts the DFS traversal from a specified node.

Code

#include 
#include 

#define MAX_VERTICES 100

// Structure to represent a graph
typedef struct {
    int vertices;
    int adj[MAX_VERTICES][MAX_VERTICES];
} Graph;

// Function to create a graph
Graph* createGraph(int vertices) {
    Graph* graph = (Graph*)malloc(sizeof(Graph));
    graph->vertices = vertices;

    // Initialize adjacency matrix
    for (int i = 0; i < vertices; i++) {
        for (int j = 0; j < vertices; j++) { graph->adj[i][j] = 0;
        }
    }
    return graph;
}

// Function to add an edge to the graph
void addEdge(Graph* graph, int src, int dest) {
    graph->adj[src][dest] = 1; // Directed edge from src to dest
    graph->adj[dest][src] = 1; // Undirected edge for bidirectional connection
}

// DFS utility function
void DFSUtil(Graph* graph, int vertex, int visited[]) {
    // Mark the current vertex as visited
    visited[vertex] = 1;
    printf("%d ", vertex);

    // Recur for all the vertices adjacent to this vertex
    for (int i = 0; i < graph->vertices; i++) {
        if (graph->adj[vertex][i] && !visited[i]) {
            DFSUtil(graph, i, visited);
        }
    }
}

// Function to perform DFS traversal
void DFS(Graph* graph, int startVertex) {
    int visited[MAX_VERTICES] = {0}; // Mark all vertices as not visited
    DFSUtil(graph, startVertex, visited);
}

int main() {
    int vertices = 5;
    Graph* graph = createGraph(vertices);

    // Add edges to the graph
    addEdge(graph, 0, 1);
    addEdge(graph, 0, 2);
    addEdge(graph, 1, 3);
    addEdge(graph, 1, 4);
    addEdge(graph, 2, 4);

    printf("DFS Traversal starting from vertex 0:\n");
    DFS(graph, 0);

    // Free allocated memory
    free(graph);
    return 0;
}

Explanation of the Code

1. Graph Structure: The graph is defined using a structure that includes the number of vertices and an adjacency matrix to store edges.

2. createGraph: This function initializes the graph with a specified number of vertices and sets the adjacency matrix to zero.

3. addEdge: This function adds edges to the graph by updating the adjacency matrix. It allows for both directed and undirected edges.

4. DFSUtil: This is a recursive function that performs the actual DFS traversal. It marks the current vertex as visited, prints it, and recursively visits all adjacent unvisited vertices.

5. DFS: This function initializes the visited array and starts the recursive traversal from a specified vertex.

6. main: This function creates a graph, adds edges, and initiates the DFS traversal starting from vertex 0.

Conclusion

The program demonstrates a simple implementation of Depth First Search using an adjacency matrix for graph representation. This approach is suitable for educational purposes and can be adapted for more complex scenarios.