algorithm - 列表性能优化

Question

是否有机会优化下一行代码:

 val adj: Array[ListBuffer[Int]] = Array.fill(n)( ListBuffer[Int]())
...
..

 val sourceVertexes = inGraph.zipWithIndex.filter(v => a.zipWithIndex.exists(r => r._2 != v._2 && r._1.exists(f => f == v._2) )

inGraph - 具有指向/链接到其他顶点的顶点数组。inGraph 的大小可以是 10000 个顶点。

我正在尝试查找源列表(没有任何输入边的顶点列表)

  val adj: Array[List[Int]] = Array.fill(n)( List[Int]())

Answer 1

是的，可以通过使用更高效的算法使其更快。现在的代码基本上是:

for each vertex:
    for each edge:
        if egde goes to vertex:
            discard it

它在最坏情况下有一个O(n * m)时间复杂度(其中m是边的数量，n是顶点数)。

这是一个与图的大小成线性关系的解决方案:

noIncoming = a hash set with all vertices (or just a boolean array)
for each edge:
    if edge is not a loop:
       noIncoming.remove(edge.desitination) // or we can put a mark in a boolean array

noIncoming 是没有传入边的顶点集。