Re:Connected Components – The one Graph Algorithm you need t...
by daveFNbuck on Saturday December 29, 2018 @11:00AM
(#18784153)
It's actually not even a nice implementation of a classical graph algorithm. They use a Python list as a queue. Python lists are only efficient when used as stacks. calling list.pop(0) or list.remove(list[0]) takes time proportional to the length of the list. This makes the algorithm take quadratic time, when it should be linear.
For this to be a nice implementation, they should use the standard library deque for the BFS or just pop from the end of the list to do a more efficient DFS for the connected component algorithm.
For this to be a nice implementation, they should use the standard library deque for the BFS or just pop from the end of the list to do a more efficient DFS for the connected component algorithm.