Graph problems are not hard

Graph problems have a reputation for being hard and there is a good reason for that.

• First off, graph algorithms are not very popular. In my day job I'm more likely to think about sorting algorithms than Dijkstra's.
• Second, unlike sorting, many languages do not offer native implementation of graphs nor graph algorithms. Solutions to graph problems are tedious because they have to be implemented from scratch.
• Third, even after mastering all graph algorithms, you come across problems that are not obviously graph-related. Problems like Longest subsequence repeated k times look like they could be solved with a Greedy algorithm or Dynamic Programming but the best solution is actually Dijkstra's.

So yes, they are hard. But you have an interview coming up, you're secretly dreading the 10% chance that your interviewer is a fan of graph algorithms. What can you do about it? Aside from trying your luck, you can try something else that is within your control: prepare.

Step 1. Learn

There is a lot to learn about graphs, it can feel overwhelming. It helps to have a map, some sort of decision tree to guide how you classify problems. Graph algorithms can be divided into 3 main categories.

1. Graph traversal
   This class of algorithms traverses a graph for different purposes such as finding a path between nodes, detecting cycles, maximizing flow, performing topological sort etc. They include Breadth First Search (BFS) and Depth First Search (DFS).

2. Shortest Path
   These algorithms aim to minimize the cost of going from one node to another. The cost could be a function of the number of hops or edge weights which can be positive or negative. This category includes popular algorithms such as BFS, Dijkstra's, Bellman Fords, Floyd-Warshall, Informed Search algorithms. Each of them is best suited for specific conditions.

3. Graph connectivity
   This category includes algorithms that test for connectedness of a graph for instance how many connected components it has, the size of the largest component, the minimal spanning tree etc. This class of problems is best solved by Union-Find algorithm or DFS.

Step 2. Practice

Similar to body building, the muscle of problem solving is built from experience. Solve a bunch of problems and you start to see the pattern. You can easily distinguish a BFS problem from a Dijkstra's problem and a graph problem from a tree problem.

There are many resources for learning Graphs ranging to textbook references to interview guides. What will actually help depends on how much you already know and how much time you have. That said, allow me to give you a biased recommendation of my Leanpub book that will be published by the end of this month. A quick and thorough guide to get you interview ready in no time. You are also welcome to check my courses on bit manipulation and dynamic programming.

Till next time, happy coding!