javascript - 强连通分量算法

Question

我很难解决强连通分量算法。到目前为止，我已经完成了这些实现，但得到了意想不到的结果。

1. DFS 并将节点添加到堆栈(在我的代码中命名为 var leader)以保持每个顶点的深度

2. 反转图边的方向(getReverseGraph())

3. 第二个 DFS 并创建强连接组件

我在第 3 步遇到问题，无法正确检测组件。

预期:

[ [ '1', '7', '5' ], ['2', '4'], [ 6, '3' ] ]

结果:

[ [ '1', '7', '5', '2', '4'], [ 6, '3' ] ]。

有人能给我一些建议吗？谢谢!

function Graph() {
  this.list = {};
}

Graph.prototype.insert = function(newVertex, neighborVertex) {
  if (!this.list[newVertex]) {

    if (neighborVertex) {
      this.list[newVertex] = [neighborVertex];
    } else {
      this.list[newVertex] = [];
    }

  } else {

    // If neighborVertex is not initialized
    if (!this.list[neighborVertex]) {
      this.list[neighborVertex] = [];
    }

    // Add neighborVertex to
    this.list[newVertex].push(neighborVertex);

  }
};

Graph.prototype.addEdge = function(vertexFrom, vertexTo) {
  if (this.list[vertexFrom] || this.list[vertexTo]) {
    throw new Error('Vertex does not exsists')
  }

  this.list[vertexFrom].push(vertexTo);
};

/*
 * DFS
 *
 * @param graph {object}: Takes different graph as optional
 * @param vertex {string|integer}
 * @param cb {function}
 */

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];

  for (var node of currentNodes) {
    visited[node] = true;
  }

  while (stack.length > 0) {

    // Get a node from stack
    var nextNode = stack.pop();

    // Invoke given function
    cb(nextNode);

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

    // Iterate adjacent nodes
    if (list[nextNode]) {

      // console.log('stack', stack)
      for (var neighbor of list[nextNode]) {

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

function getReverseGraph(graph) {
  var vertices = Object.keys(graph);
  var reverseEdgeGraph = {};

  for (let vertex of vertices) {
    for (let neighbor of graph[vertex]) {
      if (reverseEdgeGraph[neighbor]) {
        reverseEdgeGraph[neighbor].push(vertex);
      } else {
        reverseEdgeGraph[neighbor] = [vertex];
      }
    }
  }

  return reverseEdgeGraph;
}

Graph.prototype.getStrongComponent = function(vertex) {

  if (vertex && !this.list[vertex]) {
    throw new("No vertex exsits")
  }

  vertex = vertex ? vertex.toString() : Object.keys(this.list)[0].toString();

  /*
  Create Copy of current Adjacency list
  */

  var reverseEdgeGraph = getReverseGraph(this.list);

  /*
  Create Leader
  */

  var leader = []; // stack to keep the depth

  var keys = Object.keys(this.list);

  while (keys.length > 0) {

    var indexOfVertex = keys.indexOf(vertex);
    keys.splice(indexOfVertex, 1);

    this.dfs(null, vertex, function(vertex) {

      // If leader does not have the vertex

      if (leader.indexOf(vertex) < 0) {
        // Get the key (vertex)
        var indexOfVertex = keys.indexOf(vertex);

        // Delete vertex
        keys.splice(indexOfVertex, 1);

        // Add vertex to leader
        leader.unshift(vertex);
      }

    });

    // Move to next key (remaining node)
    vertex = keys[0];
  }


  /**
   *
   * Create SCC
   *
   **/

  var allSCC = [];
  var visited = {};

  while (leader.length > 0) {
    var SCC = [];
    var target = leader.pop();

    if (visited[target]) {
      break;
    }

    this.dfs(reverseEdgeGraph, target, function(vertex) {
      // Create component
      if (!visited[vertex]) {
        visited[vertex] = true;
        SCC.push(vertex);
      }

    });

    if (SCC.length > 0) {
      allSCC.push(SCC);
    }
  }

  return allSCC
}


function test() {
  var graph = new Graph();
  var result = [
    [2, 4],
    [4, 2],
    [7, 5],
    [5, 1],
    [1, 7],
    [1, 5],
    [5, 7],
    [7, 1],
    [6, 3],
    [3, 6],
    [2, 7],
    [1, 6]
  ]
  result.forEach(function(line) {
    // console.log(line)
    graph.insert(line[0], line[1]);
  });

  var result = graph.getStrongComponent().map(function(components) {
    return components.length
  }).sort(function(a, b) {
    return b - a
  });
  console.log('result => ', graph.getStrongComponent(1));
}

function dfs() {
  var graph = new Graph();
  graph.insert('a', 'b');
  graph.insert('a', 'g');
  graph.insert('b', 'c');
  graph.insert('c', 'd');
  graph.insert('d', 'e');
  graph.insert('e', 'f');
  graph.insert('f', 'd');
  graph.insert('f', 'g');
  graph.insert('g', 'e');
  graph.insert('g', 'a');
  graph.insert('g', 'b');
  graph.insert('g', 'c');
  graph.insert('g', 'd');
  graph.insert('g', 'h');

  graph.dfs(null, 'a', function(v) {
    console.log(v);
  })
}

// dfs();
test(); // should be [ [ '1', '7', '5' ], ['2', '4'], [ 6, '3' ] ]

Answer 1

您正在为每个节点运行 dfs，当您在所有节点都未访问时启动每个 dfs 时效率非常低。我向您的 dfs 函数添加了第四个参数，以便为所有调用保留一个访问过的对象。这也避免了在你的回调中重复节点，给出你想要的顺序。还稍微修改了它以使其更短一些。

有了这个，我在反转图上重构了第一个 dfs 遍历和第二个遍历。回调更清晰，更容易理解这种方式，我花了很长时间才明白你在第一个 dfs 回调中做了什么。

代码现在可以工作了:

function Graph() {
  this.list = {};
}

Graph.prototype.insert = function(newVertex, neighborVertex) {
  if (!this.list[newVertex]) {

    if (neighborVertex) {
      this.list[newVertex] = [neighborVertex];
    } else {
      this.list[newVertex] = [];
    }

  } else {

    // If neighborVertex is not initialized
    if (!this.list[neighborVertex]) {
      this.list[neighborVertex] = [];
    }

    // Add neighborVertex to
    this.list[newVertex].push(neighborVertex);

  }
};

Graph.prototype.addEdge = function(vertexFrom, vertexTo) {
  if (this.list[vertexFrom] || this.list[vertexTo]) {
    throw new Error('Vertex does not exsists')
  }

  this.list[vertexFrom].push(vertexTo);
};

/*
 * DFS
 *
 * @param graph {object}: Takes different graph as optional
 * @param vertex {string|integer}
 * @param cb {function}
 */

Graph.prototype.dfs = function(graph, vertex, cb, visited) {
  // track which node visited
  var visited = visited || {};

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

  if (visited[vertex]) return;
  
  // Mark vertex as visited
  visited[vertex] = true;

  var stack = [vertex];

  while (stack.length > 0) {

    // Get a node from stack
    var nextNode = stack.pop();

    // Invoke given function
    cb(nextNode);

    // Iterate adjacent nodes
    if (list[nextNode]) {

      // console.log('stack', stack)
      for (var neighbor of list[nextNode]) {

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

function getReverseGraph(graph) {
  var vertices = Object.keys(graph);
  var reverseEdgeGraph = {};

  for (let vertex of vertices) {
    for (let neighbor of graph[vertex]) {
      if (reverseEdgeGraph[neighbor]) {
        reverseEdgeGraph[neighbor].push(vertex);
      } else {
        reverseEdgeGraph[neighbor] = [vertex];
      }
    }
  }

  return reverseEdgeGraph;
}

Graph.prototype.getStrongComponent = function(vertex) {

  if (vertex && !this.list[vertex]) {
    throw new("No vertex exsits")
  }

  vertex = vertex ? vertex.toString() : Object.keys(this.list)[0].toString();

  /*
  Create Copy of current Adjacency list
  */

  var reverseEdgeGraph = getReverseGraph(this.list);
  var stack = [];
  var visited = {}
  
  for (var vertex in this.list) {
    this.dfs(null, vertex, function(v) {
      stack.push(v);
    }, visited)
  }
 
  /**
   *
   * Create SCC
   *
   **/
  var allSCC = [];
  visited = {};
  stack.reverse().forEach((vertex) => {
    var SCC = []
    this.dfs(reverseEdgeGraph, vertex, function(v) {
      SCC.push(v);
    }, visited)
    if (SCC.length) allSCC.push(SCC)  
  })
  
  return allSCC
}


function test() {
  var graph = new Graph();
  var result = [
    [2, 4],
    [4, 2],
    [7, 5],
    [5, 1],
    [1, 7],
    [1, 5],
    [5, 7],
    [7, 1],
    [6, 3],
    [3, 6],
    [2, 7],
    [1, 6]
  ]
  result.forEach(function(line) {
    // console.log(line)
    graph.insert(line[0], line[1]);
  });

  console.log('result => ', graph.getStrongComponent(1));
}

// dfs();
test(); // should be [ [ '1', '7', '5' ], ['2', '4'], [ 6, '3' ] ]