javascript - 强连通分量算法
问题描述
我很难解决强连通分量算法。到目前为止,我已经完成了这些实现,但我得到了意想不到的结果。
DFS 并将节点添加到堆栈(
var leader
在我的代码中命名)以保持每个顶点的深度反转图边的方向 (
getReverseGraph()
)第二个 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' ] ]
解决方案
您正在为每个节点运行 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' ] ]
推荐阅读
- android - Gitlab CI :- 如何在 Gitlab 中创建不依赖于任何系统的 Shared Runner?
- android - 有没有办法使用android studio添加布局标签?
- node.js - 当 Firestore 发生一些变化时,我想在不刷新页面的情况下更新数据
- html - 我的菜单栏的下拉菜单不起作用不显示下拉菜单
- javascript - JavaScript/GraphQL 有条件地添加片段
- python - 导入张量流错误:ImportError: DLL load failed while importing _pywrap_tensorflow_internal: The specified module could not be found
- laravel - 如何在简单的类似系统中检查用户是否已经喜欢帖子?
- sql - java.sql.SQLException:ORA-06550:第 1 行,第 4 列:PLS-00103:遇到符号“文件结尾”
- python - 使用 Python 和 Selenium 抓取特定酒店所有页面的 Tripadvisor 评论
- generics - 如何在 Rust 中定义具有不同 const 参数的结构族?