Is there any chance to optimise next line of code:
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) )
val adj: Array[List[Int]] = Array.fill(n)( List[Int]())
Yes, it is possible to make it faster by using a more efficient algorithm. What code does now is basically:
for each vertex: for each edge: if egde goes to vertex: discard it
It has an
O(n * m) time complexity in the worst case (where
m is the number of edges and
n is the number of vertices).
Here is a solution which is linear in the size of the graph:
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 is the set of vertices with no incoming edges.