This week we covered chapter 18 of A Common-Sense Guide to Data Structures and Algorithms, 2nd ed. by Jay Wengrow (link). I’ve been coding along in Python on my Github.
Our topic today was graphs.
- Jamie did the examples in C#: https://gist.github.com/phillipsj/b05b1c528b2dee26dfc40f1d5c0eb6dc
- Houston struggled getting the Dijkstra’s algorithm to work in Python. Geoff had some issues trying to get this to work as well.
- This type of data structure really resonated with Jamie… trees are a type of graph, the impact of cycles, how Git is a directed acyclic graph (no cycles, multiple parents), network routing.
- Houston liked revisiting breadth-first and depth-first search implementations, as he hasn’t used this since college.
- Jamie noted that the depth-first search implementation uses memoization because you have bookkeeping to keep track of what nodes you’ve visited. Houston had the same idea with Dijkstra’s algorithm, as you build up metadata while traversing the graph that could be stored off for later use.
- Even though Geoff learned graphs in computer science class, the concept of including V (vertex count) and E (edge count) in big-O was new: e.g., O(V + E). Houston and Dennis hadn’t seen this either. Jamie found this comment on StackOverflow about big-O.
- We found that graph problems are more subtle — i.e., not quite as likely to encounter directly in our careers — than many of the other data structures we’ve discussed so far.