Depth First Search - Graph in Python

Depth-first search (DFS) is a method of visiting all the nodes of a tree or a graph in a depth-first manner, i.e., visiting a node and all its descendants before moving on to the next sibling. Here is a basic implementation of depth-first search on a graph in Python 3.10:

class Graph:
    def __init__(self, num_of_vertices):
        self.num_of_vertices = num_of_vertices
        self.adj_list = {i: [] for i in range(num_of_vertices)}

    def add_edge(self, v, w):
        self.adj_list[v].append(w)

    def depth_first_search(self, start_vertex, visited, result):
        visited[start_vertex] = True
        result.append(start_vertex)

        for neighbor in self.adj_list[start_vertex]:
            if not visited[neighbor]:
                self.depth_first_search(neighbor, visited, result)

    def DFS(self, start_vertex):
        result = []
        visited = [False for _ in range(self.num_of_vertices)]
        self.depth_first_search(start_vertex, visited, result)
        return result

The above implementation of depth-first search on a graph uses recursion to traverse the graph in a depth-first manner. The depth_first_search method visits a node and all its descendants before moving on to the next sibling, and the DFS method calls the depth_first_search method, passing in the start_vertex and two lists to keep track of the nodes visited and the order they were visited. Time complexity of depth-first search in a graph:

• The time complexity of depth-first search is O(V + E), where V is the number of vertices and E is the number of edges in the graph. This is because each vertex and each edge is visited exactly once.

Space complexity of depth-first search in a graph:

• The space complexity of depth-first search is O(V), where V is the number of vertices in the graph. This is because in the worst case, the recursion will use V function calls, each of which takes O(1) space.