1
$\begingroup$

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?

Improve this question
$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$
    – Steven
    Sep 23 at 15:55
  • $\begingroup$ @Steven Can you elaborate it further, I don't get what you are saying. $\endgroup$
    – CaptainHow
    Sep 23 at 16:04
  • $\begingroup$ 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'$). $\endgroup$
    – Steven
    Sep 24 at 18:01
  • $\begingroup$ 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? $\endgroup$
    – CaptainHow
    Sep 25 at 8:09

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.