A depth-first search (DFS) is an algorithm that traverses a graph by exploring as far as possible along each branch before backtracking. The basic idea of DFS is to start from a vertex, mark it as visited, and then recursively visit all the vertices that are adjacent to it and not yet visited.
There are two common ways to implement DFS: using a stack (recursive DFS) or using a stack explicitly (iterative DFS).
Recursive DFS
# Recursive DFS function
def dfs(graph, vertex, visited):
# Mark the current vertex as visited
visited[vertex] = True
print(vertex, end=' ')
# Recur for all the vertices adjacent to this vertex
for neighbor in graph[vertex]:
if not visited[neighbor]:
dfs(graph, neighbor, visited)
# Driver code
# Create a graph represented as an adjacency list
graph = {0: [1, 2], 1: [2], 2: [0, 3], 3: [3]}
# Create a list to store the visited vertices
visited = [False] * len(graph)
# Call the DFS function
dfs(graph, 2, visited)
Iterative DFS
# Iterative DFS function
def dfs(graph, start):
# Create a stack for DFS
stack = []
# Mark the source node as visited and push it
stack.append(start)
while stack:
# Pop a vertex from stack and print it
vertex = stack.pop()
print(vertex, end=' ')
# Get all adjacent vertices of the popped vertex
for neighbor in graph[vertex]:
if neighbor not in stack:
stack.append(neighbor)
# Driver code
# Create a graph represented as an adjacency list
graph = {0: [1, 2], 1: [2], 2: [0, 3], 3: [3]}
# Call the DFS function
dfs(graph, 2)
Both the above implementations have the same time complexity of O(V+E), where V is the number of vertices, and E is the number of edges. The iterative version uses additional space for the stack, which is O(V) in the worst case.
Note: The above code snippet is in python and it's taking the graph as adjacency list representation of graph. the graph can be represented in multiple ways like adjacency matrix, edge list, etc. The above code snippet is just one representation of the graph and the implementation will vary depending on the representation chosen.
In adjacency matrix representation of a graph, each vertex is represented by an index in the matrix and an edge between two vertices is represented by a 1 in the corresponding cells of the matrix. For example, in the following graph:
0 -- 1
/ \ |
2 - 3 -4
The adjacency matrix representation will be:
[[0, 1, 1, 1, 0],
[1, 0, 0, 1, 1],
[1, 0, 0, 1, 0],
[1, 1, 1, 0, 0],
[0, 1, 0, 0, 0]]
In this case, the DFS algorithm can be implemented as follows:
# DFS function for adjacency matrix representation
def dfs(graph, vertex, visited):
# Mark the current vertex as visited
visited[vertex] = True
print(vertex, end=' ')
# Recur for all the vertices adjacent to this vertex
for i in range(len(graph)):
if graph[vertex][i] == 1 and not visited[i]:
dfs(graph, i, visited)
# Driver code
# Create a graph represented as an adjacency matrix
graph = [[0, 1, 1, 1, 0],
[1, 0, 0, 1, 1],
[1, 0, 0, 1, 0],
[1, 1, 1, 0, 0],
[0, 1, 0, 0, 0]]
# Create a list to store the visited vertices
visited = [False] * len(graph)
# Call the DFS function
dfs(graph, 2, visited)
In the edge list representation, each edge is represented as a tuple (u, v) representing an edge from vertex u to vertex v. For example, the above graph can be represented as:
[(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)]
In this case, the DFS algorithm can be implemented as follows:
# DFS function for edge list representation
def dfs(graph, vertex, visited):
# Mark the current vertex as visited
visited[vertex] = True
print(vertex, end=' ')
# Recur for all the vertices adjacent to this vertex
for edge in graph:
if edge[0] == vertex and not visited[edge[1]]:
dfs(graph, edge[1], visited)
# Driver code
# Create a graph represented as an edge list
graph = [(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)]
# Create a list to store the visited vertices
visited = [False] * len(graph)
# Call the DFS function
dfs(graph, 2, visited)
In the adjacency list representation, each vertex is represented by a list of its adjacent vertices. For example, the above graph can be represented as:
graph = {0: [1, 2, 3], 1: [0, 2, 3], 2: [0, 1, 3], 3: [0, 1, 2], 4: []}
In this case, the DFS algorithm can be implemented as follows:
# DFS function for adjacency list representation
def dfs(graph, vertex, visited):
# Mark the current vertex as visited
visited[vertex] = True
print(vertex, end=' ')
# Recur for all the vertices adjacent to this vertex
for neighbor in graph[vertex]:
if not visited[neighbor]:
dfs(graph, neighbor, visited)
# Driver code
# Create a graph represented as an adjacency list
graph = {0: [1, 2, 3], 1: [0, 2, 3], 2: [0, 1, 3], 3: [0, 1, 2], 4: []}
# Create a list to store the visited vertices
visited = [False] * len(graph)
# Call the DFS function
dfs(graph, 2, visited)
It's important to note that DFS can be implemented using stack data structure, which is a Last In First Out (LIFO) data structure. The idea is to start the DFS from the starting vertex and push the neighboring vertices to the stack. The vertex at the top of the stack is then popped and the process is repeated until the stack is empty.
In summary, a graph is a collection of vertices and edges that can be represented in different ways, such as adjacency matrix, edge list, and adjacency list. The depth-first search algorithm can be used to traverse a graph and can be implemented using any of the above representations, and it can be implemented using the stack data structure.