假设我们有4个节点，所有节点都连接到所有其他节点，我需要从node1转到node4。我检查的大多数资源的时间复杂性是O(V+E)，但我有点困惑。
node1
|
node2 / node3 / node4 level2 3
|
node1 / node3 / node4 .................. level3 3 to power of 2
因此如果所有节点都将被访问，则复杂性是N的幂。即使使用哈希集来跟踪使用回溯访问了哪些节点，也不应该影响总体时间复杂性？
复杂度不会是NN如果您从每个节点访问所有节点，它将是N2，如果N这里是您的节点数。
现在，一个完整的图(一个所有节点都连接到所有节点的图，就像在你的例子中一样(有很多边|E|=O(|V|2(。如果你不知道为什么，只需注意每个节点都连接到(N-1(其他节点，所以边的确切数量是。
深度优先搜索的时间复杂性，就像你说的，O(|V|+|E|(。在big-O表示法中，这与O(max(|V|，|E|((相同，因为只有主项才重要。因此，对于我们的完全图，|E|占主导地位，并且复杂性仅为O(|E|(。
正如我们之前所说的，|E|=O(|V|2(，所以我们的复杂性是O(|E|(=O(| V|2(。
这是否为您的困惑提供了一些澄清？