The basic algorithm for BFS:
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
So I would think the time complexity would be:
v1 + (incident edges) + v2 + (incident edges) + .... + vn + (incident edges)
where v
is vertex 1
to n
Firstly, is what I've said correct? Secondly, how is this O(N + E)
, and intuition as to why would be really nice. Thanks
This question is related to
algorithm
time-complexity
graph-theory
breadth-first-search
It's O(V+E) because each visit to v of V must visit each e of E where |e| <= V-1. Since there are V visits to v of V then that is O(V). Now you have to add V * |e| = E => O(E). So total time complexity is O(V + E).
Time complexity is O(E+V)
instead of O(2E+V)
because if the time complexity is n^2+2n+7 then it is written as O(n^2).
Hence, O(2E+V) is written as O(E+V)
because difference between n^2 and n matters but not between n and 2n.
I think every edge has been considered twice and every node has been visited once, so the total time complexity should be O(2E+V).
An intuitive explanation to this is by simply analysing a single loop:
So the total time for a single loop is O(1)+O(e). Now sum it for each vertex as each vertex is visited once. This gives
For every V
=>
O(1)
+
O(e)
=> O(V) + O(E)
Short but simple explanation:
I the worst case you would need to visit all the vertex and edge hence the time complexity in the worst case is O(V+E)
DFS(analysis):
O(1)
timeO(n + m)
time provided the graph is represented by the adjacency list structureSv deg(v) = 2m
BFS(analysis):
Li
O(n + m)
time provided the graph is represented by the adjacency list structureSv deg(v) = 2m
Very simplified without much formality: 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.
Source: Stackoverflow.com