设G为连通图。 我知道任何图的 BFS 运行时间都是 O(m+n)，其中 n 是顶点数，m 是边数。 对于连通图，我们有 m>=n-1 所以 n<=m+1. So the running time of BFS is O(m+n) \subseteq O(m+m+1)=O(m). Is this correct?
是的。
根据定义，连通图的每个节点之间都有一条路径。最长的此类路径需要遍历所有节点，从开始到结束的时间复杂度为 O(m)，n（或 m+1。）
我的说法可能会有所不同，但我认为你是对的。