News for hackers. Stuff that matters.
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.

There are no comments on this comment yet.