Exploring Time Complexity of the Depth First Search Algorithm

Depth-First Search (DFS) is a traversal algorithm that explores a graph or tree by going as deep as possible along each branch of the graph. It uses the stack data structure to keep track of the visited nodes.

The algorithm starts from a given source node and explores as far as possible along each branch before exploring other branches.

def dfs_traversal(adj_list, vertex):
    traversal_seq = []
    visited = set()
    stack = [vertex]

    while stack:
        current_vertex = stack.pop()
        # Visit each vertex
        if current_vertex not in visited:
            traversal_seq.append(current_vertex)
            visited.add(current_vertex)
            # Iterate over edges
            stack.extend([v for v in adj_list[current_vertex] if v not in visited])

        	print(f"Sequence: {traversal_seq}")
        	print('---------------------')
    return traversal_seq

traverse = dfs_traversal(graph_adj_list, "A")
print(f"Final traversal sequence:\n{traverse}")

vector<int> dfs_traversal(int start_vertex) {
    vector<int> traversal_seq;
    unordered_set<int> visited;
    stack<int> to_visit;
    to_visit.push(start_vertex);

    while (!to_visit.empty()) {
        int current_vertex = to_visit.top();
        to_visit.pop();

        // Visit each vertex
        if (!visited.count(current_vertex)) {
            traversal_seq.push_back(current_vertex);
            visited.insert(current_vertex);

            // Iterate over edges
            for (auto neighbor : adj_list[current_vertex]) {
                if (!visited.count(neighbor)) {
                    to_visit.push(neighbor);
                }
            }
        }
    }
    return traversal_seq;
}

Analyzing Time Complexity

The time complexity of this algorithm can be broken down into two parts:

1. Visiting Each Vertex

This algorithm visits each vertex once, which takes constant time, O(1), per vertex. Since there are V vertices, the total time complexity of visiting each vertex is O(V).

2. Iterating Over Edges

This algorithm also iterates over the neighbours of each vertex, which takes time proportional to the number of edges, E. Since each edge is visited once, the total time complexity of iterating over edges is O(E).

Thus, the time complexity of the DFS algorithm is O(V + E), which accounts for visiting each vertex once (O(V)) and processing each edge once (O(E)).

Despite the nested structure, the algorithm does not revisit edges for every vertex, so the complexity is not O(V * E).

Factors Affecting Time Complexity

While the time complexity of DFS is O(V + E), there are some factors that can affect its performance:

1. Graph Density

In a dense graph, the number of edges E approaches <katex>V^{2}</katex>, where V is the number of vertices. This makes the time complexity <katex>O(V + V^{2})</katex>.

But since <katex>V^{2}</katex> dominates V, the effective time complexity becomes <katex>(V^{2})</katex>.

2. Graph Sparsity

In a sparse graph, E and V are almost equal. Thus, the complexity is closer to O(V) as very few edges need to be explored.