CODEWITHSUNDEEP
data-structures
Maher Turifi
Maher Turifi

Reputation: 33

what options of data structure could be used in finding connected components in large datasets?

let's say we have a HashMap with for a graph with node and adjacency list

HashMap[node:Long,compId:Long, neighbours:Set[Long])]

what is the best way to update all the nodes with the minimum compId(connected component id) and what is the best data structure that can be used when the size of the data is large?

Upvotes: 0

Views: 112

Answers (1)

codecrazer
codecrazer

Reputation: 535

just use disjoint set data struture, in general case, the amortized complexity would be O(1), very fast!!

Upvotes: 1

Related Questions