Graphs are so daunting, but not impossible. I'm just glad leetcode doesn't ask impossible problems. Graphs are fun. Who uses matrixes for graphs tho. SO boring...
Notes on my faults:
- I started graphs. The questions on leetcode aren't directly related to graphs, its more about the traversals and applying graph logic. BFS and DFS. BFS - checking shortest path
DFS- checking if it exists. BFS uses queues. DFS uses stacks and recursion.
- Topological sort is complicated, but the basics use a set and a stack. Its a sort that outputs an order of a graph. The graph has to be directed. It doesn't make sense if it isn't
- Topological sort is for package management. It's a quick way to use packages and their dependencies. If there is a edge between two vertices from a to b. A must be before b when being
traversed in topological sort. There are many outputs for topological sorts, but they all follow this rule.
- I ran into one DP problem, I tried it out on my own, but couldn't figure out how to implement it correctly. If the problem is about distances, most likely can be done with DP.
- DP could require more than one pass. Just think of the order in which you are traversing the given data/structure and think about what's been visited and what information you have.
You may have to traverse again to fill in the gaps of knowledge you need for each node or point on that data/structure. (very complicated to think about)
- Graphs seem daunting. Every problem on leetcode that use it is complicated. Really complicated.
No comments:
Post a Comment