Graph Algorithms
Traversal, shortest paths and connectivity.
2 subjects · 7 topics · 2 cheatsheets
Subjects covering this category
2 subjects- Subject · Intermediate to Advanced
Tracing, implementing and proving the cost of the classic searching, sorting and graph algorithms, and designing new ones with divide and conquer, backtracking, greedy choice and dynamic programming, in Python, Java and TypeScript.
- Searching and Simple Sorting
- Efficient Sorting
- Design Strategies
- Subject · Intermediate to Advanced
Recognising which of the common problem-solving patterns an unseen coding problem needs, and solving it in Python, Java or TypeScript within the time an interview allows.
- Approach
- Array and Number Patterns
- Linked List Patterns
Cheatsheets
2 cheatsheets- Cheatsheet · Algorithms
Traversal, ordering, shortest paths, spanning trees and connectivity on one page: which algorithm a graph question needs and what it costs.
- Cheatsheet · Coding Interview Patterns
Fourteen coding interview patterns on one page: the property that points to each, what it costs, when it fails, and its loop in Python.
In Graph Algorithms itself
7 topics- Algorithms
Shortest paths in weighted graphs, in algorithms: Dijkstra's algorithm, Bellman-Ford and Floyd-Warshall, and how weights and pairs choose between them.
Intermediate to Advanced11 cards · 6 qnot started
- Algorithms
Breadth-first and depth-first search in algorithms, and what they find: components, cycles, bipartite graphs and unweighted shortest paths.
Intermediate to Advanced10 cards · 6 qnot started
- Algorithms
Minimum spanning trees in algorithms: the cut property, Kruskal's algorithm with union-find, Prim's algorithm with a heap, and why neither gives shortest paths.
Intermediate to Advanced9 cards · 4 qnot started
- Algorithms
Ordering tasks so every dependency comes first, in algorithms: Kahn's algorithm, depth-first finishing times, and how each one finds a cycle.
Intermediate to Advanced8 cards · 4 qnot started
- Coding Interview Patterns
Grid traversal: treating a grid of cells as a graph for breadth-first and depth-first search, flood fills and searches from many starting cells.
Intermediate to Advanced8 cards · 4 qnot started
- Coding Interview Patterns
Graph modelling: finding the vertices and edges hidden in a problem's wording, then solving it with a search, a topological sort or union-find.
Intermediate to Advanced8 cards · 4 qnot started
- Algorithms
Graph connectivity in algorithms: strongly connected components with Kosaraju's two passes, bridges and articulation points from low values, and choosing the tool.
Intermediate to Advanced7 cards · 3 qnot started