Graphs
Graph problems are plentiful but the core data structure does have some unique techniques that can be applied to it
Last updated
Graph problems are plentiful but the core data structure does have some unique techniques that can be applied to it
Last updated
Most of the algorithms used for graph problems are found under Graph instead
DFS/BFS/Topological sort:
Number of vertices is
Number of edges is
Adjacency matrix
Adjacency list
Hash table of hash tables
Tree like diagrams could be a graph with cycles so clarify before assuming
Correctly track visited nodes and not visit each node more than once
Empty graphs
Graph with one or two nodes
Disconnected graphs
Graphs with cycles
Rather than starting from the original problem, try reversing the problem and start with the end state in mind or the other set of elements
This method of traversal is also known as "level-order BFS" but I like to name is as a "virus" traversal as you can imagine it as a virus spreading across the graph.
The infected nodes spread to their neighbors at once, must like how level-order BFS works
Queue all elements that fit a criteria and BFS from that queue at once
Ensure that visited set is maintained so no duplicate elements are queued
Useful for propagating an operation to all neighbors
Each batch of processing of processing is often seen as "1 day" of virus spreading of one step.