Implement depth-first search (DFS) on a graph.
Depth-First Search (DFS) is a graph traversal algorithm that explores as far as possible along each branch before backtracking.
Algorithm Steps:
- Initialize a set or array to keep track of visited vertices.
- Choose a starting vertex and mark it as visited.
- For each unvisited neighbor of the current vertex:
- Recursively call DFS on the neighbor (or push it onto the stack in the stack-based approach).
- Mark the neighbor as visited.
- Repeat the process until all reachable vertices are visited.
- The time complexity of DFS is O(V + E), where V is the number of vertices and E is the number of edges. Each vertex and edge are visited once.
DFS Implementation C++
#include <iostream>
#include <vector>
class Graph {
private:
int vertices;
std::vector<std::vector<int>> adjacencyList;
public:
Graph(int v) : vertices(v), adjacencyList(v) {}
void addEdge(int u, int v) {
adjacencyList[u].push_back(v);
adjacencyList[v].push_back(u); // For an undirected graph
}
void dfs(int startVertex, std::vector<bool>& visited) {
visited[startVertex] = true;
std::cout << startVertex << " ";
for (int neighbor : adjacencyList[startVertex]) {
if (!visited[neighbor]) {
dfs(neighbor, visited);
}
}
}
void performDFS(int startVertex) {
std::vector<bool> visited(vertices, false);
dfs(startVertex, visited);
}
};
int main() {
// Create a sample graph
Graph graph(7);
graph.addEdge(0, 1);
graph.addEdge(0, 2);
graph.addEdge(1, 3);
graph.addEdge(1, 4);
graph.addEdge(2, 5);
graph.addEdge(2, 6);
// Perform DFS starting from vertex 0
std::cout << "DFS starting from vertex 0: ";
graph.performDFS(0);
std::cout << std::endl;
return 0;
}
Output:
DFS starting from vertex 0: 0 1 3 4 2 5 6