Depth first search can help us check if a vertex,
v, is connected to another vertex,
s, in constant time. To do so, we just check if there is a path to the vertex in the graph.
We can also find the path
v-s if such a path exists in time proportional to its length. To do so, we simply back-traverse the
DFS is implemented in a recursive fashion.
The time complexity for DFS is
O(|V| + |E|), which is linear.
We visited each vertex once which is
DFS visit is called once per vertex where we have a cost of
O(Sum of adj(v) for all v)=
Every edge is considered exactly twice, and every node is processed exactly once, so the complexity has to be a constant multiple of the number of edges as well as the number of vertices.
- v1 + (incident edges) + v2 + (incident edges) + .... + vn + (incident edges) =(v1 + v2 + ... + vn) + [(incident_edges v1) + (incident_edges v2) + ... + (incident_edges vn)]
Note: For directed graphs it is just O(E) since you visit each edge once
Total time complexity is hence
O(|V| + |E|).
We can imagine this as traversing the entire data structure - each vertex has an adjacency list and we are going through the entire structure which gives us
O(V + 2E).
This also means that whichever term,
Eis bigger will dominate the time complexity.
Note: The time complexity is representative of the data structure used. Here, we have assumed the use of an adjacency list. If it was a adjacency matrix, it would have been