Let’s implement DFS (Depth-First Search) for the Graph
object using recursion in different programming languages.
Java
In Java, assuming the Graph
class has a field LinkedList<Integer>[] adjList
:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| import java.util.LinkedList;
public class Graph {
LinkedList<Integer>[] adjList;
int vertices;
// Constructor and other methods...
public void dfs(int startVertex, boolean[] visited) {
visited[startVertex] = true;
System.out.print(startVertex + " ");
for (int neighbor : adjList[startVertex]) {
if (!visited[neighbor]) {
dfs(neighbor, visited);
}
}
}
public void dfs(int startVertex) {
boolean[] visited = new boolean[vertices];
dfs(startVertex, visited);
System.out.println();
}
}
|
C++
In C++, assuming the Graph
class has a field vector<vector<int>> adjList
:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| #include <iostream>
#include <vector>
class Graph {
public:
std::vector<std::vector<int>> adjList;
int vertices;
// Constructor and other methods...
void dfs(int startVertex, std::vector<bool>& visited) {
visited[startVertex] = true;
std::cout << startVertex << " ";
for (int neighbor : adjList[startVertex]) {
if (!visited[neighbor]) {
dfs(neighbor, visited);
}
}
}
void dfs(int startVertex) {
std::vector<bool> visited(vertices, false);
dfs(startVertex, visited);
std::cout << std::endl;
}
};
|
Python
In Python, assuming the Graph
class has a field adjList
:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Graph:
def __init__(self, vertices):
self.vertices = vertices
self.adjList = [[] for _ in range(vertices)]
# Other methods to add edges, etc...
def dfs(self, startVertex, visited):
visited[startVertex] = True
print(startVertex, end=" ")
for neighbor in self.adjList[startVertex]:
if not visited[neighbor]:
self.dfs(neighbor, visited)
def dfs(self, startVertex):
visited = [False] * self.vertices
self.dfs(startVertex, visited)
print()
|
Each of these implementations of DFS uses the Graph
object’s adjacency list (adjList
) to explore the vertices.