定向非循环图中所有节点的可达性计数
所以在Hackerrank上的一个名为“Acyclic Graph”的编程竞赛中遇到了这个挑战,这个挑战基本归结为计算“定向非循环图”中每个节点可到达的节点数量。 例如,假设你有这样一个图表:
[ 1 ] ---->[ 2 ]--->[ 4 ]--->[ 5 ] [ 3 ] ------/
可达性计数(包括原始节点):
Node 1: 4 Node 2: 3 Node 3: 4 Node 4: 2 Node 5: 1
我的方法是“深度优先”穿越记忆。 四周看了很多,但似乎运行时间似乎不能进一步改善,因为在这样的情况下发生的过度计数:
[ 1 ] ---->[ 2 ]--->[ 4 ]--->[ 5 ] [ 3 ] ------/--------/
第三个节点会统计第四个节点,即使第二个节点已经统计了第四个节点。 为了让事情变得更糟,我只用JavaScript解决了这些挑战。 它是我的主要语言,我从推动它的边界获得快感。 领导委员会中没有人用JavaScript解决了这个问题,但我认为这是可能的。 比赛结束后,我用下面的代码设法通过了24个testing用例中的13个:
function Solution( graph, nodes ) { var memory = new Array( nodes + 1 ) , result = 0; graph.forEach( ( a, v ) => DepthFirstSearch( graph, v, memory ) ); // challenge asks for an output variation, but the accurate // reachability count of every node will be contained in "d.length". memory.forEach( ( d, i ) => { if ( i && ( 2 * d.length ) >= nodes ) result++; } ); return result; } function DepthFirstSearch( graph, v, memory ) { if ( memory[ v ] ) return memory[ v ]; var descendants = new Uint16Array( [ v ] ); graph[ v ].forEach( u => { descendants = MergeTypedArrays( DepthFirstSearch( graph, u, memory ), descendants ); } ); // make elements unique // to avoid over counting return memory[ v ] = Uint16Array.from( new Set( descendants ) ); } function MergeTypedArrays(a, b) { var c = new a.constructor( a.length + b.length ); c.set( a ); c.set( b, a.length ); return c; } // adjacency list var graph = [ [], // 0 [ 2 ], // 1 [ 4 ], // 2 [ 2 ], // 3 [ 5 ], // 4 [] // 5 ]; var nodes = 5; Solution( graph, nodes );
对于大于50kb的所有input,大概input具有大量节点和边缘(即50,000个节点和40,000个边缘),则失败。 如果不能识别或设想一个更快,更高效的内存algorithm,那么接下来要尝试什么,我完全不知所措。 想到使DFS迭代,但我认为记忆成千上万的数组的内存消耗将超过这个,这似乎是主要的问题。 我在Hackerrank上得到11个testing失败的“Abort Called”和“Runtime Error”(与“Timeout”相反)。 还尝试过使用“union”的“bitSets”,但是由于bitSets数组需要足够大以存储高达50,000的数字,所以内存消耗变得更糟。
约束:
1 ≤ n,m ≤ 5×10^4 1 ≤ a(i),b(i) ≤ n and a(i) ≠ b(i) It is guaranteed that graph G does not contain cycles.
只是想说清楚,我将不会得到任何通过所有testing,因为这个挑战被locking,这是为了教育目的,主要是优化。 我意识到相关的SOpost指向拓扑sorting,但据我所知,拓扑sorting仍然会超过上述的情况,因此不是一个可行的解决scheme。 如果我误解了,请赐教。 预先感谢您的时间。
问题:如何进一步优化? 有没有更高效的方法?
深度优先search(DFS)是解决这个问题的好方法。 另一种方法是广度优先search(BFS),它也可以并行运行并且可以很好地进行优化 – 但所有代价都要高得多的代码复杂度。 所以我的build议是坚持DFS。
首先,我必须实现apoligize,但是我的JavaScript技能不是很好(即他们不存在),所以我的解决scheme使用Java,但是这些想法应该很容易移植。
您最初的问题是缺less一个非常重要的细节:我们只需要find所有可达节点数大于或等于|V| / 2
节点|V| / 2
|V| / 2
为什么这很重要? 计算每个节点的可达节点的数量是昂贵的,因为我们必须从图的每个节点开始执行DFS或BFS。 但是,如果我们只需要find具有上述属性的节点,则更容易。
设后继节点(n)是所有可从n到达的节点, 祖先(n)是可到达n的所有节点。 我们可以使用以下观察来大幅减lesssearch空间:
- 如果从n到达的节点数量小于| V | / 2,则后继节点(n)中没有节点可以具有更大的数量
- 如果从n到达的节点数大于或等于| V | / 2,则祖先(n)中的所有节点将具有更大的数目
我们如何使用它?
- 创buildgraphics时,也要创build转置graphics。 这意味着当存储边a-> b时,将b-> a存储在转置图中。
- 创build一个存储要忽略的节点的数组,使用
false
初始化它 - 实现一个基于DFS的函数,该函数确定给定节点是否有多个可达节点
>= |V| / 2
>= |V| / 2
(见下文) - 在该函数中,忽略标记为忽略的节点
- 如果节点n的节点数小于| V | / 2 ,将后继者(n)中的所有节点标记为忽略
- 否则统计祖先(n)中的所有节点并将其标记为忽略
使用迭代DFS的解决scheme
public int countReachable(int root, boolean[] visited, boolean[] ignored, Graph graph) { if (ignored[root]) { return 0; } Stack<Integer> stack = new Stack<>(); stack.push(root); int count = 0; while (stack.empty() == false) { int node = stack.pop(); if (visited[node] == false) { count++; visited[node] = true; for (int neighbor : graph.getNeighbors(node)) { if (visited[neighbor] == false) { stack.push(neighbor); } } } } if (count * 2 >= graph.numNodes()) { return markAndCountAncestors(root, visited, ignored, graph); } else { return markSuccessors(root, visited, ignored, graph); } }
标记祖先的function
这只是另一个DFS,但使用转置图。 请注意,我们可以重用visited
arrays,因为我们将使用的所有值都是false
因为这是一个非循环图。
public int markAndCountAncestors(int root, boolean[] visited, boolean[] ignored, Graph graph) { Stack<Integer> stack = new Stack<>(); stack.push(root); visited[root] = false; int count = 0; while (stack.empty() == false) { int node = stack.pop(); if (visited[node] == false && ignored[node] == false) { count++; visited[node] = true; ignored[node] = true; for (int neighbor : graph.transposed.getNeighbors(node)) { if (visited[neighbor] == false && ignored[node] == false) { stack.push(neighbor); } } } } return count; }
标记后继者的function
请注意,我们已经有了inheritance者,因为他们只是我们设置visited
的节点为true。
public int markSuccessors(int root, boolean[] visited, boolean[] ignored, Graph graph) { for(int node = 0; node < graph.numNodes(); node++) { if (visited[node)) { ignored[node] = true; } } return 0; }
计算结果的函数
public void solve(Graph graph) { int count = 0; boolean[] visited = new boolean[graph.numNodes()]; boolean[] ignored = new boolean[graph.numNodes()]; for (int node = 0; node < graph.numNodes(); node++) { Arrays.fill(visited, false); // reset visited array count += countReachable(node, visited, ignored, graph); } System.out.println("Result: " + count); }
在你发布的大型testing案例中,这对我来说是7.5秒。 如果你颠倒迭代顺序(即solve
你开始最大的节点ID)它下降到4秒,但有点感觉就像作弊^^