График DFS медленное время работы

Question

У меня проблема с запуском графической DFS для больших объемов данных (n> 5 000 000).Проблема во времени медленно.Может ли кто-нибудь указать, что я должен изменить?Я думаю, что сложность времени это O (V * M).Спасибо!

Graph.prototype.dfs = function(graph, vertex, cb) {


  // track which node visited
  var visited = {};

  // Take graph as option
  var list = graph ? graph : this.list;

  // get initial nodes
  var currentNodes = list[vertex];

  // Invoke given function for inital node
  cb(vertex);

  // Mark vertex as visited
  visited[vertex] = true;

  // If there is no node to traverse return 
  if (currentNodes.length === 0) {
    return;
  }

  var stack = [...currentNodes];

  while (stack.length > 0) {

    // Get a node from stack
    var nextNode = stack.pop();
    if (!visited[nextNode]) {
      // Invoke given function
      cb(nextNode);
    }

    // Mark the vertex as visited
    visited[nextNode] = true;

    // Iterate adjacent nodes
    if (list[nextNode]) {
      for (var neighbor of list[nextNode]) {

        // If the vertex is not visited, push each nodes to stack
        if (!visited[neighbor]) { 
          stack.push(neighbor);
        }      
      } 
    } 

  }
}

Answer 1

Сложность DFS - O (V + M), поэтому, если она занимает более 10 секунд, что-то не так.Первое, что я вижу, это то, что вы добавляете узлы в стек, не отмечая их как посещенные, поэтому несколько узлов могут в конечном итоге добавить один и тот же узел в стек.

Попробуйте добавить visited[neighbor] = true; после stack.push(neighbor);