dfs.c

graphs Implementation

38 lines
799 bytes
C
1// Graph - DFS (Depth First Search)
2#include <stdio.h>
3#define MAX 100
4
5void DFSUtil(int graph[][MAX], int vertices, int vertex, int visited[]) {
6    visited[vertex] = 1;
7    printf("%d ", vertex);
8    
9    for (int i = 0; i < vertices; i++) {
10        if (graph[vertex][i] == 1 && !visited[i]) {
11            DFSUtil(graph, vertices, i, visited);
12        }
13    }
14}
15
16void DFS(int graph[][MAX], int vertices, int start) {
17    int visited[MAX] = {0};
18    
19    printf("DFS Traversal: ");
20    DFSUtil(graph, vertices, start, visited);
21    printf("\n");
22}
23
24int main() {
25    int vertices = 5;
26    int graph[MAX][MAX] = {
27        {0, 1, 1, 0, 0},
28        {1, 0, 0, 1, 1},
29        {1, 0, 0, 0, 1},
30        {0, 1, 0, 0, 0},
31        {0, 1, 1, 0, 0}
32    };
33    
34    DFS(graph, vertices, 0);
35    
36    return 0;
37}
38