定向非循环图中所有节点的可达性计数

所以在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)中的所有节点将具有更大的数目

我们如何使用它?

  1. 创buildgraphics时,也要创build转置graphics。 这意味着当存储边a-> b时,将b-> a存储在转置图中。
  2. 创build一个存储要忽略的节点的数组,使用false初始化它
  3. 实现一个基于DFS的函数,该函数确定给定节点是否有多个可达节点>= |V| / 2 >= |V| / 2 (见下文)
  4. 在该函数中,忽略标记为忽略的节点
  5. 如果节点n的节点数小于| V | / 2 ,将后继者(n)中的所有节点标记为忽略
  6. 否则统计祖先(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,但使用转置图。 请注意,我们可以重用visitedarrays,因为我们将使用的所有值都是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秒,但有点感觉就像作弊^^