Graphs: The Interview Perspective
Explore core graph concepts for coding interviews, including how to model problems as graphs, differentiate graph types, and apply DFS and BFS traversals. Understand common pitfalls and best practices in Go to build efficient graph solutions that meet interview expectations.
Graphs show up in interviews across a wide range of problems: finding the shortest path between two nodes, detecting cycles in a dependency system, counting connected components in a network, and determining whether a schedule is valid. They’re the most general data structure we’ll encounter. Trees are a special case of graphs, and many real-world problems that seem unrelated to graphs are solved by modeling them as one.
Why interviewers reach for graphs
A graph problem is almost always a problem about relationships. When the data involves connections between entities—whether those connections are roads, dependencies, friendships, or transitions—a graph is the right structure to model it. Interviewers use graph problems to test whether we can recognize that structure and apply the right traversal.
Candidates who do well on graph problems build the graph first, then apply DFS or BFS to answer the question. Candidates who struggle try to solve graph problems without explicitly modeling the graph, which leads to solutions that are harder to reason about and generalize.
Interview lens: When an interviewer gives us a graph problem, they watch whether we identify the graph structure immediately and reach for the right traversal. A candidate who says, "I’ll model this as an adjacency list and run BFS to find the shortest path," signals strong problem-modeling instincts. That’s the reasoning interviewers want to hear.
Directed vs. undirected, weighted vs. unweighted
Every graph problem specifies, explicitly or implicitly, whether the graph is directed and whether it is weighted. These two properties determine which algorithms apply and what the solution looks like.
In a directed graph, edges have a direction. An edge from A to B does not imply an edge from B to A. Directed graphs model one-way relationships: course prerequisites, task dependencies, and web page links. In an undirected graph, every edge is bidirectional. An edge between A and B means we can travel in either direction. Undirected graphs model mutual relationships: friendships, roads, and network connections.
In a weighted graph, each edge carries a numerical value representing cost, distance, or time. Shortest-path algorithms like Dijkstra's operate on weighted graphs. In an unweighted graph, all edges are equal. BFS finds the shortest path in an unweighted graph in
Graph types
Switch between graph types to see how direction and weight change the structure and which algorithms apply.
Graph representations
A graph can be stored in two standard ways: an adjacency list or an ...