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 ++ map []:

Логарифмический размер.

Я знаю, что DFS в (графе смежности) ориентированного графа - это O (V + E), но я 'Я не уверен, какую сложность дает мне эта функция с оператором map [].

Answer 1

Во-первых, из вашего псевдокода неясно, где вызывается map :: 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