Depth First Search (DFS)

Depth First Search is executed utilizing a stack-based mechanism, commencing from a specified vertex. It systematically traverses through adjacent vertices, persisting until no further adjacent vertices remain unexplored. Here’s an example implementation of Depth First Search (DFS) algorithm:

Time Complexity: O(V + E)

Python

class Node:
    def __init__(self, vertex):
        self.vertex = vertex
        self.next = None


class Graph:
    def __init__(self, numVertices):
        self.numVertices = numVertices
        self.adjLists = [None] * numVertices
        self.visited = [0] * numVertices

    def addEdge(self, src, dest):
        # Add edge from src to dest
        newNode = Node(dest)
        newNode.next = self.adjLists[src]
        self.adjLists[src] = newNode

        # Add edge from dest to src
        newNode = Node(src)
        newNode.next = self.adjLists[dest]
        self.adjLists[dest] = newNode

    def DFS(self, vertex):
        adjList = self.adjLists[vertex]
        temp = adjList

        self.visited[vertex] = 1
        print("Visited", vertex)

        while temp:
            connectedVertex = temp.vertex

            if self.visited[connectedVertex] == 0:
                self.DFS(connectedVertex)
            temp = temp.next

    def printGraph(self):
        for v in range(self.numVertices):
            temp = self.adjLists[v]
            print("\nAdjacency list of vertex", v)
            while temp:
                print(temp.vertex, "->", end=" ")
                temp = temp.next
            print()


if __name__ == '__main__':
    graph = Graph(4)
    graph.addEdge(0, 1)
    graph.addEdge(0, 2)
    graph.addEdge(1, 2)
    graph.addEdge(2, 3)
    
    graph.printGraph()
    
    graph.DFS(2)

#include <stdio.h>
#include <stdlib.h>

struct node {
  int vertex;
  struct node* next;
};

struct node* createNode(int v);

struct Graph {
  int numVertices;
  int* visited;

  // We need int** to store a two dimensional array.
  // Similary, we need struct node** to store an array of Linked lists
  struct node** adjLists;
};

// DFS algo
void DFS(struct Graph* graph, int vertex) {
  struct node* adjList = graph->adjLists[vertex];
  struct node* temp = adjList;

  graph->visited[vertex] = 1;
  printf("Visited %d \n", vertex);

  while (temp != NULL) {
    int connectedVertex = temp->vertex;

    if (graph->visited[connectedVertex] == 0) {
      DFS(graph, connectedVertex);
    }
    temp = temp->next;
  }
}

// Create a node
struct node* createNode(int v) {
  struct node* newNode = malloc(sizeof(struct node));
  newNode->vertex = v;
  newNode->next = NULL;
  return newNode;
}

// Create graph
struct Graph* createGraph(int vertices) {
  struct Graph* graph = malloc(sizeof(struct Graph));
  graph->numVertices = vertices;

  graph->adjLists = malloc(vertices * sizeof(struct node*));

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

  int i;
  for (i = 0; i < vertices; i++) {
    graph->adjLists[i] = NULL;
    graph->visited[i] = 0;
  }
  return graph;
}

// Add edge
void addEdge(struct Graph* graph, int src, int dest) {
  // Add edge from src to dest
  struct node* newNode = createNode(dest);
  newNode->next = graph->adjLists[src];
  graph->adjLists[src] = newNode;

  // Add edge from dest to src
  newNode = createNode(src);
  newNode->next = graph->adjLists[dest];
  graph->adjLists[dest] = newNode;
}

// Print the graph
void printGraph(struct Graph* graph) {
  int v;
  for (v = 0; v < graph->numVertices; v++) {
    struct node* temp = graph->adjLists[v];
    printf("\n Adjacency list of vertex %d\n ", v);
    while (temp) {
      printf("%d -> ", temp->vertex);
      temp = temp->next;
    }
    printf("\n");
  }
}

int main() {
  struct Graph* graph = createGraph(4);
  addEdge(graph, 0, 1);
  addEdge(graph, 0, 2);
  addEdge(graph, 1, 2);
  addEdge(graph, 2, 3);

  printGraph(graph);

  DFS(graph, 2);

  return 0;
}

Output

Adjacency list of vertex 0
2 -> 1 -> 

Adjacency list of vertex 1
2 -> 0 -> 

Adjacency list of vertex 2
3 -> 1 -> 0 -> 

Adjacency list of vertex 3
2 -> 
Visited 2
Visited 3
Visited 1
Visited 0

Click to view another code.

Python

def dfs(graph, start, visited=None):
    if visited is None:
        visited = set()
    
    visited.add(start)
    print(start)
    
    for next_node in graph[start] - visited:
        dfs(graph, next_node, visited)
        # print(start)  # Print the current node again after exploring neighbors
    
    return visited

graph = {'0': set(['1', '2']),
         '1': set(['0', '3', '4']),
         '2': set(['0']),
         '3': set(['1']),
         '4': set(['2', '3'])}

dfs(graph, '0')

DFS