Graphs: The Interview Perspective
Graphs are a fundamental data structure used to model relationships between entities, appearing frequently in coding interviews. They can be directed or undirected, weighted or unweighted, influencing the choice of algorithms for traversal and problem-solving. Key traversal methods include Depth-First Search (DFS) and Breadth-First Search (BFS), both requiring a visited set to prevent infinite loops due to cycles. Common pitfalls include neglecting the visited set, misrepresenting graph directionality, and assuming connectivity. Properly identifying graph structures and employing the right algorithms is crucial for effective problem-solving in interviews.
Graphs appear 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 are the most general data structures we will encounter. Trees are a special case of graphs, and many real-world problems that appear 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 to it.
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 will model this as an adjacency list and run BFS to find the shortest path," signals strong problem-modeling instincts. That is 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 ...