ℹ️ Select 'Choose Exercise', or randomize 'Next Random Exercise' in selected language.

Choose Exercise:
Timer 00:00
WPM --
Score --
Acc --
Correct chars --

Depth First Search (DFS) - Adjacency List

C

Goal -- WPM

Ready
Exercise Algorithm Area
1#include <stdio.h>

2#include <stdlib.h>

3

4// Structure to represent an adjacency list node

5struct AdjListNode {

6int dest;

7struct AdjListNode* next;

8};

9

10// Structure to represent a graph using adjacency list

11struct Graph {

12int V; // Number of vertices

13struct AdjListNode** adjLists; // Array of pointers to adjacency lists

14int* visited; // Array to keep track of visited vertices

15};

16

17// Function to create a new adjacency list node

18struct AdjListNode* createNode(int dest) {

19struct AdjListNode* newNode = (struct AdjListNode*)malloc(sizeof(struct AdjListNode));

20newNode->dest = dest;

21newNode->next = NULL;

22return newNode;

23}

24

25// Function to create a graph

26struct Graph* createGraph(int V) {

27struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph));

28graph->V = V;

29graph->adjLists = (struct AdjListNode**)malloc(V * sizeof(struct AdjListNode*));

30graph->visited = (int*)malloc(V * sizeof(int));

31

32for (int i = 0; i < V; i++) {

33graph->adjLists[i] = NULL;

34graph->visited[i] = 0; // Initialize all vertices as not visited

35}

36return graph;

37}

38

39// Function to add an edge to the graph

40void addEdge(struct Graph* graph, int src, int dest) {

41struct AdjListNode* newNode = createNode(dest);

42newNode->next = graph->adjLists[src];

43graph->adjLists[src] = newNode;

44

45// For undirected graph, add an edge from dest to src as well

46// newNode = createNode(src);

47// newNode->next = graph->adjLists[dest];

48// graph->adjLists[dest] = newNode;

49}

50

51// Recursive DFS function

52void DFSUtil(struct Graph* graph, int vertex) {

53graph->visited[vertex] = 1; // Mark the current node as visited

54printf("%d ", vertex); // Print the visited vertex

55

56// Recur for all the vertices adjacent to this vertex

57struct AdjListNode* adj = graph->adjLists[vertex];

58while (adj != NULL) {

59int connectedVertex = adj->dest;

60if (!graph->visited[connectedVertex]) {

61DFSUtil(graph, connectedVertex);

62}

63adj = adj->next;

64}

65}

66

67// Main DFS function to handle disconnected components

68void DFS(struct Graph* graph) {

69if (graph == NULL) return;

70for (int i = 0; i < graph->V; i++) {

71if (!graph->visited[i]) {

72DFSUtil(graph, i);

73}

74}

75}

76

77// Example usage

78int main() {

79int V = 7;

80struct Graph* graph = createGraph(V);

81addEdge(graph, 0, 1);

82addEdge(graph, 0, 2);

83addEdge(graph, 1, 3);

84addEdge(graph, 1, 4);

85addEdge(graph, 2, 5);

86addEdge(graph, 2, 6);

87

88printf("DFS traversal starting from vertex 0:\n");

89DFS(graph);

90printf("\n");

91

92// Example with disconnected component

93struct Graph* graph2 = createGraph(5);

94addEdge(graph2, 0, 1);

95addEdge(graph2, 0, 2);

96addEdge(graph2, 3, 4);

97

98printf("DFS traversal for a graph with disconnected components:\n");

99DFS(graph2);

100printf("\n");

101

102// Clean up memory (simplified for example)

103// In a real application, you'd free all allocated memory.

104

105return 0;

106}
Algorithm description viewbox

Depth First Search (DFS) - Adjacency List

Algorithm description:

Depth First Search (DFS) is an algorithm for traversing or searching tree or graph data structures. The algorithm starts at the root node (or an arbitrary node in the case of a graph) and explores as far as possible along each branch before backtracking. It's commonly used for topological sorting, finding connected components, and pathfinding.

Algorithm explanation:

DFS explores a graph by going as deep as possible along each branch before backtracking. It uses a visited array to keep track of nodes already explored, preventing infinite loops in cyclic graphs. The algorithm starts at a chosen vertex, marks it as visited, and then recursively visits all its unvisited neighbors. If a vertex has no unvisited neighbors, the algorithm backtracks to the previous vertex and continues exploring. The time complexity is O(V + E), where V is the number of vertices and E is the number of edges, because each vertex and edge is visited at most once. The space complexity is O(V) for the recursion stack and the visited array. Edge cases include disconnected graphs, which are handled by iterating through all vertices and starting a new DFS if a vertex hasn't been visited.

Pseudocode:

FUNCTION DFS(graph)
  FOR EACH vertex v IN graph
    IF v is not visited THEN
      DFS_Util(graph, v)
    END IF
  END FOR
END FUNCTION

FUNCTION DFS_Util(graph, v)
  Mark v as visited
  PROCESS v (e.g., print it)
  FOR EACH neighbor u of v
    IF u is not visited THEN
      DFS_Util(graph, u)
    END IF
  END FOR
END FUNCTION