DFS与内部访问地图元素。时间复杂度

Question

我已经得到了通过用C ++编写的地图来表示有向图。

Node{
 vector<int> adjacency_list;
};
Graph{
 map<Node,Node> map;
};

我有递归DFS像（伪代码）：

dfs(node):
   for adjacent_node in node.adjacency_list:
       if(map[adjacent_node].valid):
          dfs(map[adjacent_node])

作为C ++复杂地图[]操作符是：

对数的大小。

我知道，在DFS（邻接表）向图是O（V + E），但我不知道是什么的复杂性这个功能让我这个地图[]运营商。

Answer 1

首先，它是不是从你的伪代码，其中地图:: operator []的叫，因为通过地图迭代通常在没有完成它明确（线性时间）。

其次，根据该图的结构（即它是一个树？）你的算法可能会访问同一节点多次，造成潜在的指数时间复杂度。如果它包含定向环路，它永远不会终止。

用下面的C ++代码，你的确会得到O（V + E）的时间复杂度。

void dfs(Node& node) {
    if(node.visited) return;
    node.visited = true;
    for(Node& adj : node.adjacency_list) dfs(adj);
}

编辑：请注意，您实际上会获得O（E）的时间复杂度，但如果E <V-1，您将不能访问所有节点。