# Why in Edmonds Karp or Ford Fulkerson Algorithm the time complexity of BFS or DFS respectively is O(E) rather than O(V+E)?

For these algorithms, the time complexity of BFS and DFS is O(E).

I have gone through many websites and even the algorithm books, but I never got a clear idea of why it is O(E). It just says it's O(E) in the flow graph as it considers only edges. What does this mean?

• They are probably assuming that $|E| \ge |V|-1$. You cal always restrict yourself to the subgraph induced by the vertices reachable from your the flow source. This subgraph satisfies the above condition. Doing so requires one-time preprocessing which can be done in $O(|V|+|E|)$ time. Sep 23 at 15:55
• @Steven Can you elaborate it further, I don't get what you are saying. Sep 23 at 16:04
• You are looking for the maximum flow from $s$ to $t$. If some node $v$ is not reachable from $s$, then there will certainly be no flow that "passes through" $v$. This means that you can delete all vertices that are not reachable from $s$ before even running any flow algorithm. Once you do this (in time $O(|V|+|E|)$), every vertex except possibly $s$ will have at least one incoming edge. Therefore the number $m'$ of edges can be at most the number of vertices $n'$ minus $1$. Then, the time of BFS/DFS visit is $O(n' + m') = O(m')$ (since $n'+m' < 2m'$). Sep 24 at 18:01
• So, from this what I understood is that at a vertex we are gonna check if the edges are incoming or outgoing, if they’re incoming we won’t go ahead, so the cost would be of checking the edges. Then there won’t be some of the vertices to be checked. That’s why we will have less vertices to be checked and the edges to be checked would be more. Am I right? Sep 25 at 8:09