How does time complexity for depth first search on a graph come out to be O(V E) in the following code?

Using a Python dictionary to act as an adjacency list

graph = {
    'A' : ['B','C'],
    'B' : ['D', 'E'],
    'C' : ['F'],
    'D' : [],
    'E' : ['F'],
    'F' : []
}

visited = set() # Set to keep track of visited nodes.

def dfs(visited, graph, node):
    if node not in visited:
        print (node)
        visited.add(node)
        for neighbour in graph[node]:
            dfs(visited, graph, neighbour)

# Driver Code
dfs(visited, graph, 'A')

CodePudding user response：

if node not in visited:

due to this, no vertex is visited more than 1 time, and

for neighbour in graph[node]:

due to this every edge connected to each node is considered as a possible step of DFS

so the time complexity of O(V E) (assuming O(1) insertion and deletion in your set)

CodePudding user response：

Except for the first call of dfs, every other call of dfs will uniquely correspond to one edge. Because of the visited mechanism, it is not possible that for the same value of node and neighbor the recursive call of dfs is made.

Actually this is the only determining factor for this algorithm, and so it is O(E).

In case the graph is disconnected, this algorithm will not visit all nodes. When that is a case that must be dealt with, the driver code should look like this:

for node in graph:
    dfs(visited, graph, node)

With this change the complexity becomes O(V E). This is because there might be more many more nodes than edges in a disconnected graph, and so O(E) would not capture the complexity, and the loop in the driver code becomes the determining factor. Yould thus say it is O(MAX(V, E)), which is the same as O(V E).