blocks|key|522533|text|你的总和|type|unstyled|depth|inlineStyleRanges|entityRanges|data|522534|v1+%2B+(incident+edges)+%2B+v2+%2B+(incident+edges)+%2B+....+%2B+vn+%2B+(incident+edges)|code-block|syntax|javascript|522535|可以重写为|522536|(v1+%2B+v2+%2B+...+%2B+vn)+%2B+[(incident_edges+v1)+%2B+(incident_edges+v2)+%2B+...+%2B+(incident_edges+vn)]|522537|第一组是O(N)，另一组是O(E)。|offset|length|style|CODE|522538|entityMap^0|0|0|0|0|4|4|D|4|0^^$0|@$1|2|3|4|5|6|7|S|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|T|8|@]|9|@]|A|$E|F]]|$1|G|3|H|5|6|7|U|8|@]|9|@]|A|$]]|$1|I|3|J|5|D|7|V|8|@]|9|@]|A|$E|F]]|$1|K|3|L|5|6|7|W|8|@$M|X|N|Y|O|P]|$M|Z|N|10|O|P]]|9|@]|A|$]]|$1|Q|3|-4|5|6|7|11|8|@]|9|@]|A|$]]]|R|$]]

Your sum

<pre><code>v1 + (incident edges) + v2 + (incident edges) + .... + vn + (incident edges)
</code></pre>

can be rewritten as

<pre><code>(v1 + v2 + ... + vn) + [(incident_edges v1) + (incident_edges v2) + ... + (incident_edges vn)]
</code></pre>

and the first group is <code>O(N)</code> while the other is <code>O(E)</code>.

blocks|key|305880|text|非常简化，没有太多的形式:每条边被恰好考虑两次，每个节点被恰好处理一次，所以复杂度必须是边的数量以及顶点的数量的恒定倍数。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|305881|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|D|8|@]|9|@]|A|$]]|$1|B|3|-4|5|6|7|E|8|@]|9|@]|A|$]]]|C|$]]

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.

blocks|key|522704|text|时间复杂度是O(E%2BV)而不是O(2E%2BV)，因为如果时间复杂度是n%5E2%2B2n%2B7，那么它就写成O(n%5E2)。|type|unstyled|depth|inlineStyleRanges|offset|length|style|CODE|entityRanges|data|522705|因此，O(2E%2BV)写成O(E%2BV)|522706|因为n%5E2和n之间的差异很重要，但n和2n之间并不重要。|522707|entityMap^0|6|6|F|7|0|0|0^^$0|@$1|2|3|4|5|6|7|L|8|@$9|M|A|N|B|C]|$9|O|A|P|B|C]]|D|@]|E|$]]|$1|F|3|G|5|6|7|Q|8|@]|D|@]|E|$]]|$1|H|3|I|5|6|7|R|8|@]|D|@]|E|$]]|$1|J|3|-4|5|6|7|S|8|@]|D|@]|E|$]]]|K|$]]

Time complexity is <code>O(E+V)</code> instead of <code>O(2E+V)</code> 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.

blocks|key|305923|text|我认为每条边都被考虑过两次，每个节点都被访问过一次，所以总的时间复杂度应该是O(2E%2BV)。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|305924|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|D|8|@]|9|@]|A|$]]|$1|B|3|-4|5|6|7|E|8|@]|9|@]|A|$]]]|C|$]]

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

blocks|key|522830|text|在Bfs中，每个相邻顶点被插入到队列中一次。这是通过查看顶点的边来完成的。标记每个访问过的顶点，使其不能再次访问:每个顶点只访问一次，并检查每个顶点的所有边。在V%2BE中，每个节点维护着它所有相邻边的列表，然后，对于每个节点，你只需要在线性时间内遍历它的邻接表一次，就可以发现它的所有邻居。对于有向图，所有节点的邻接表的大小之和为E(边的总数)。因此，DFS的复杂度为O(V+%2B+E)。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|522831|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|D|8|@]|9|@]|A|$]]|$1|B|3|-4|5|6|7|E|8|@]|9|@]|A|$]]]|C|$]]

In Bfs, each neighboring vertex is inserted once into a queue. This is done by looking at the edges of the vertex. Each visited vertex is marked so it cannot be visited again: each vertex is visited exactly once, and all edges of each vertex are checked. So the complexity of BFS is V+E.
In DFS, each node maintains a list of all its adjacent edges, then, for each node, you need to discover all its neighbors by traversing its adjacency list just once in linear time. For a directed graph, the sum of the sizes of the adjacency lists of all the nodes is E(total number of edges). So, the complexity of DFS is O(V + E).

blocks|key|306042|text|它是O(V%2BE)，因为每次访问V的v都必须访问E的每个e，其中%7Ce%7C+<=+V-1。因为有V访问V的v，那么就是O(V)。现在你必须添加V*+%7Ce%7C+=E+=>+O(E)。因此，总时间复杂度为O(V+%2B+E)。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|306043|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|D|8|@]|9|@]|A|$]]|$1|B|3|-4|5|6|7|E|8|@]|9|@]|A|$]]]|C|$]]

It's O(V+E) because each visit to v of V must visit each e of E where |e| &lt;= V-1. Since there are V visits to v of V then that is O(V). Now you have to add V * |e| = E =&gt; O(E). So total time complexity is O(V + E).

The basic algorithm for BFS:

<pre><code>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
</code></pre>

So I would think the time complexity would be: 

<pre><code>v1 + (incident edges) + v2 + (incident edges) + .... + vn + (incident edges) 
</code></pre>

where <code>v</code> is vertex <code>1</code> to <code>n</code>

Firstly, is what I've said correct? Secondly, how is this <code>O(N + E)</code>, and intuition as to why would be really nice. Thanks

Why is the time complexity of both DFS and BFS O( V + E )

翻译质量差，导致语言生硬或混乱。

没有提供实际的解决方法或示例。

解答不清晰，无法理解或解决问题。

页面排版不美观，阅读体验差。

文章

问答

视频

教程

学习中心

腾讯云实验室

直播

竞赛

腾讯云代码分析专区

腾讯iOA零信任安全管理系统专区

腾讯云架构师技术同盟交流圈

腾讯云数据库专区

腾讯云智能顾问专区

腾讯云原生专区

腾讯混元专区

腾讯云TCE专区

腾讯云Lighthouse专区

腾讯云HAI专区

腾讯云Edgeone专区

腾讯云存储专区

腾讯云智能专区

腾讯轻联专区 

腾讯云开发专区

TAPD专区

腾讯轻量云游戏服专区

腾讯云最具价值专家

腾讯云架构师技术同盟

腾讯云创作之星

腾讯云开发者先锋

腾讯云代码助手

云原生构建

TAPD 敏捷项目管理

Cloud Studio

SDK中心

API中心

命令行工具

涵盖代码开发、场景应用、自动测试全流程，助你从零构建专属AI助手

一站式MCP教程库，解锁AI应用新玩法

聚焦“写作效率、视觉美观与运行性能”三方面进行全面升级，为您提供更高效、稳定的创作环境

社区富文本&Markdown编辑器全新改版上线，欢迎大家体验!

诚挚邀请您参与本次调研，分享您的真实使用感受与建议。您的反馈至关重要，感谢您的支持与参与！

社区新版编辑器体验调研

BFS的基本算法：set start vertex to visitedload it into queuewhile queue not empty   for each edge incident to vertex        if its not visited            load into queue            mark vertex所以我认为时间复杂度应该是：

问为什么DFS和BFS的时间复杂度都是O( V+E)
EN

回答 6

Stack Overflow用户

Stack Overflow用户

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问为什么DFS和BFS的时间复杂度都是O( V+E)EN

回答 6

Stack Overflow用户

Stack Overflow用户

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问为什么DFS和BFS的时间复杂度都是O( V+E)
EN