Some inconsistencies in representation of sets about dsa HOT 5 CLOSED

Hey @Takashiidobe! Thank you for the feedback. Yep, I'm originally from Omaha, Nebraska.

This code uses a dictionary of node -> bool, when a set works fine.
https://github.com/msambol/dsa/blob/master/shortest_path/dijkstras.py#L21C1-L29C26
If this code initialized an empty visited set, the line of visited[node] = False in the graph iteration could be removed.

Do you want to do a PR for this?

This code uses an array which has O(n) access to check for visited, which makes the dfs algorithm O(n^2) instead of O(n)
https://github.com/msambol/dsa/blob/master/search/depth_first_search.py#L18C1-L29C32
(There is a note in another part of the code that changes a list to a queue to improve time complexity, so I assume this change is in scope).
https://github.com/msambol/dsa/blob/master/search/breadth_first_search.py#L19C1-L21C20

If you change it to a queue, you still need to iterate through the entire visited queue. The only operations on the array are append and pop, which are both O(1) [source]. I changed the BFS code to deque because append and popleft (not pop here) are both O(1), whereas popleft on an array is O(n). Make sense?

This code uses a list for visited, which is probably faster than the set in this case but is another representation of a set:
https://github.com/msambol/dsa/blob/master/maximum_flow/ford_fulkerson.py#L21C1-L21C31

Either should be good here. The only operations on the array are get and set which are both O(1).

Thank you for looking at this!

from dsa.

I can make a PR for these changes (+ some others with some comments). We can discuss them more there and you can take what you'd like.

from dsa.

This code uses an array which has O(n) access to check for visited, which makes the dfs algorithm O(n^2) instead of O(n)
https://github.com/msambol/dsa/blob/master/search/depth_first_search.py#L18C1-L29C32
(There is a note in another part of the code that changes a list to a queue to improve time complexity, so I assume this change is in scope).
https://github.com/msambol/dsa/blob/master/search/breadth_first_search.py#L19C1-L21C20

If you change it to a queue, you still need to iterate through the entire visited queue. The only operations on the array are append and pop, which are both O(1) [source]. I changed the BFS code to deque because append and popleft (not pop here) are both O(1), whereas popleft on an array is O(n). Make sense?

I would change it to a set in this case, since the line if n not in visited where visited is a list is O(n) always, since it does a linear scan. If it was a set, it would be O(1). I wasn't using the bfs example as a direct 1:1 replacement, I was just noting that it was in scope to change a list to a queue to improve time complexity, so changing it from a list to a set to improve time complexity should also be in scope.

from dsa.

@Takashiidobe My fault, I misread that. I thought you were suggesting a queue. I'll take a look at the PRs 👍🏼

from dsa.

@Takashiidobe Thank you for improving these! Let me know if there is anything else.

from dsa.