1
$\begingroup$

Consider the algorithm (from another question):

set start vertex to visited
load it into queue
    while queue not empty
        for each edge incident to vertex
             if its not visited
                 load into queue
                 mark vertex

The complexity of the algorithm is defined as the upper bound of times the inner loop can run, right? Well, considering a complete graph. For each one of its N vertexes, we run the check if its not visited N-1 times. So, that's N * (N-1) tests, which is quadratic. What is wrong with this view?

$\endgroup$
4
  • 3
    $\begingroup$ If you know the answer, you can answer your own question. $\endgroup$ Commented Dec 1, 2014 at 4:07
  • 2
    $\begingroup$ What research have you done? This is covered by standard textbooks: when they describe DFS and BFS they generally provide an analysis of the running time and explain why the running time is $O(|V|+|E|)$. We expect you to do a significant amount of research and self-study before asking. It doesn't benefit anyone to repeat standard material that is covered in standard textbooks on the subject. $\endgroup$
    – D.W.
    Commented Dec 1, 2014 at 7:16
  • $\begingroup$ Following on from @YuvalFilmus's comment, not only can you answer your own question but it's explicitly encouraged. $\endgroup$ Commented Dec 1, 2014 at 10:42
  • $\begingroup$ Note our reference question on analysis (simple) algorithms. $\endgroup$
    – Raphael
    Commented Dec 1, 2014 at 13:06

3 Answers 3

2
$\begingroup$

Overall, BFS accesses (and processes) each edge constant times (twice actually; we assume an undirected graph), costing $O(E)$ total time in edge processing. Similarly, all the vertices are totally accessed (including queue operations and checking operations) $O(E) \cdot O(1)$ times. The overhead for initialization is $O(V)$. Thus the total running time of BFS is $O(V + E)$.

This can be viewed as a simple instance of aggregate analysis.

$\endgroup$
0
$\begingroup$

Each vertex is visited once and each edge twice assuming implementation with an adjacency list so the running time is a constant multiple of the number of edges + number of vertices. Thus it is O(V + E).

$\endgroup$
-1
$\begingroup$

In BFS algorithm we begin from a arbitary vertex, so we meet all of vertexes then we claim that $O(v)$.since we must meet all vertexes then we used maximum edges to reach other vertexes . so we have $O(V+E)$

$\endgroup$
1
  • $\begingroup$ Welcome to Computer Science Stack Exchange! Unfortunately, I can't work out what your argument is, here. What do you mean by "then we used maximum edges to reach other vertices"? What if you got lucky and only looked at $V$ edges? How can you guarantee that edges won't be considered many times each? $\endgroup$ Commented Dec 1, 2014 at 10:41

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.