Algorithm
Depth-First Search (DFS) Algorithm:
-
Start at the initial node: Begin at the initial (or source) node in the graph.
-
Mark the node as visited: Mark the current node as visited to avoid revisiting it.
-
Explore neighbors: Visit an unvisited neighbor of the current node. If there are multiple neighbors, choose one arbitrarily.
-
Recursion: Recursively apply steps 2-3 to the chosen neighbor. This process continues until there are no more unvisited neighbors.
-
Backtrack: If there are no unvisited neighbors, backtrack to the previous node and repeat step 3 for any unvisited neighbors of that node.
-
Repeat: Repeat steps 2-5 until all nodes in the graph are visited.
The key characteristic of DFS is that it explores as far as possible along each branch before backtracking. It can be implemented using recursion or a stack data structure.
Code Examples
#1 DFS Implementation in Python
Code -
Python Programming
class Graph:
def __init__(self):
self.graph = {}
def add_edge(self, u, v):
if u not in self.graph:
self.graph[u] = []
self.graph[u].append(v)
def dfs(self, start, visited=None):
if visited is None:
visited = set()
print(start, end=' ')
visited.add(start)
for neighbor in self.graph.get(start, []):
if neighbor not in visited:
self.dfs(neighbor, visited)
# Example usage:
# Create a graph
g = Graph()
# Add edges to the graph
g.add_edge(1, 2)
g.add_edge(1, 3)
g.add_edge(2, 4)
g.add_edge(2, 5)
g.add_edge(3, 6)
g.add_edge(3, 7)
# Perform DFS starting from node 1
print("DFS starting from node 1:")
g.dfs(1)
#2 DFS Implementation in Java
Code -
Java Programming
import java.util.*;
class Graph {
private int vertices;
private LinkedList < Integer>[] adjacencyList;
public Graph(int vertices) {
this.vertices = vertices;
this.adjacencyList = new LinkedList[vertices];
for (int i = 0; i < vertices; i++) {
adjacencyList[i] = new LinkedList<>();
}
}
public void addEdge(int vertex, int neighbor) {
adjacencyList[vertex].add(neighbor);
}
public void dfs(int startVertex) {
boolean[] visited = new boolean[vertices];
dfsRecursive(startVertex, visited);
}
private void dfsRecursive(int vertex, boolean[] visited) {
visited[vertex] = true;
System.out.print(vertex + " ");
for (int neighbor : adjacencyList[vertex]) {
if (!visited[neighbor]) {
dfsRecursive(neighbor, visited);
}
}
}
}
public class DFSExample {
public static void main(String[] args) {
Graph graph = new Graph(6);
graph.addEdge(0, 1);
graph.addEdge(0, 2);
graph.addEdge(1, 3);
graph.addEdge(1, 4);
graph.addEdge(2, 5);
System.out.println("Depth-First Traversal starting from vertex 0:");
graph.dfs(0);
}
}
#3 DFS Implementation in C
Code -
C Programming
#include <stdio.h>
#include <stdlib.h>
// Structure to represent a node in the adjacency list
struct Node {
int data;
struct Node* next;
};
// Structure to represent the graph
struct Graph {
int vertices;
struct Node** adjacencyList;
int* visited;
};
// Function to create a new node
struct Node* createNode(int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
newNode->next = NULL;
return newNode;
}
// Function to create a graph with 'vertices' number of vertices
struct Graph* createGraph(int vertices) {
struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph));
graph->vertices = vertices;
graph->adjacencyList = (struct Node**)malloc(vertices * sizeof(struct Node*));
graph->visited = (int*)malloc(vertices * sizeof(int));
for (int i = 0; i < vertices; i++) {
graph->adjacencyList[i] = NULL;
graph->visited[i] = 0; // Initialize all vertices as not visited
}
return graph;
}
// Function to add an edge to the graph
void addEdge(struct Graph* graph, int src, int dest) {
// Add an edge from src to dest
struct Node* newNode = createNode(dest);
newNode->next = graph->adjacencyList[src];
graph->adjacencyList[src] = newNode;
// For undirected graphs, add an edge from dest to src as well
newNode = createNode(src);
newNode->next = graph->adjacencyList[dest];
graph->adjacencyList[dest] = newNode;
}
// Depth-First Search function
void DFS(struct Graph* graph, int vertex) {
// Mark the current vertex as visited
graph->visited[vertex] = 1;
printf("%d ", vertex);
// Traverse all adjacent vertices
struct Node* temp = graph->adjacencyList[vertex];
while (temp != NULL) {
int adjVertex = temp->data;
if (!graph->visited[adjVertex]) {
DFS(graph, adjVertex);
}
temp = temp->next;
}
}
int main() {
// Create a graph with 5 vertices
struct Graph* graph = createGraph(5);
// Add edges to the graph
addEdge(graph, 0, 1);
addEdge(graph, 0, 2);
addEdge(graph, 1, 3);
addEdge(graph, 1, 4);
printf("Depth-First Traversal starting from vertex 0: ");
DFS(graph, 0);
return 0;
}
#4 DFS Implementation in C++
Code -
C++ Programming
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
class Graph {
int V; // number of vertices
vector < vector<int>> adjList; // adjacency list
public:
Graph(int vertices) : V(vertices), adjList(vertices) {}
void addEdge(int v, int w) {
adjList[v].push_back(w);
}
void DFS(int startVertex) {
// Create a boolean array to keep track of visited vertices
vector < bool> visited(V, false);
// Create a stack for DFS
stack<int> stack;
// Push the current vertex to the stack and mark it as visited
stack.push(startVertex);
visited[startVertex] = true;
while (!stack.empty()) {
// Get the top vertex from the stack
int currentVertex = stack.top();
cout << currentVertex << " ";
stack.pop();
// Traverse all adjacent vertices of the popped vertex
for (int adjacentVertex : adjList[currentVertex]) {
if (!visited[adjacentVertex]) {
// If the adjacent vertex is not visited, push it to the stack and mark it as visited
stack.push(adjacentVertex);
visited[adjacentVertex] = true;
}
}
}
}
};
int main() {
Graph g(5); // Create a graph with 5 vertices
// Add edges
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 3);
g.addEdge(2, 4);
cout << "DFS starting from vertex 0: ";
g.DFS(0);
return 0;
}
Demonstration
Depth First Search (DFS) Data Structure and Algorithm