Why is the time complexity of both DFS and BFS O(

问题:

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

回答1:

Your sum

v1 + (incident edges) + v2 + (incident edges) + .... + vn + (incident edges)

can be rewritten as

(v1 + v2 + ... + vn) + [(incident_edges v1) + (incident_edges v2) + ... + (incident_edges vn)]

and the first group is O(N) while the other is O(E).

回答2:

DFS(analysis):

• Setting/getting a vertex/edge label takes O(1) time
• Each vertex is labeled twice
  • once as UNEXPLORED
  • once as VISITED
• Each edge is labeled twice
  • once as UNEXPLORED
  • once as DISCOVERY or BACK
• Method incidentEdges is called once for each vertex
• DFS runs in O(n + m) time provided the graph is represented by the adjacency list structure
• Recall that Σv deg(v) = 2m

BFS(analysis):

• Setting/getting a vertex/edge label takes O(1) time
• Each vertex is labeled twice
  • once as UNEXPLORED
  • once as VISITED
• Each edge is labeled twice
  • once as UNEXPLORED
  • once as DISCOVERY or CROSS
• Each vertex is inserted once into a sequence Li
• Method incidentEdges is called once for each vertex
• BFS runs in O(n + m) time provided the graph is represented by the adjacency list structure
• Recall that Σv deg(v) = 2m

回答3:

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.

回答4:

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.

回答5:

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).

回答6:

An intuitive explanation to this is by simply analysing a single loop:

1. visit a vertex -> O(1)
2. a for loop on all the incident edges -> O(e) where e is a number of edges incident on a given vertex v.

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

Sigma_i

p {
    height: 50px;
    line-height: 50px;
}

span {
    position: relative;
    font-size: 2.5em;
    display: inline-block;
    line-height: .7em;
    vertical-align: middle;
}

span:before {
    font-size: 12px;
    display: block;
    position absolute;
    left: 0;
    top: 0;
    content: "V";
    width: 22px;
    text-align: center;
}

span:after {
    font-size: 12px;
    display: block;
    position absolute;
    left: 0;
    bottom: 0;
    content: "k = 1";
    width: 27px;
    text-align: center;
}

<p>
    <span>&Sigma;</span>
    O(1) + O(e)
=> 
    <span>&Sigma;</span>
    O(1)
    +
   <span>&Sigma;</span>
    O(e)

=> O(V) + O(E)

</p>

[ O(1) + O(e)]

回答7:

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)