Graph problem patterns

Spotting a graph in disguise

Problems rarely say "here is a graph". Ask two questions. What are the things? Those are the vertices. What connects two things? Those are the edges. The edges do not have to be stored anywhere; often you generate them when you need them. Such a graph is called an implicit graph.

Bipartite check: two colours

A graph is bipartite if you can split its vertices into two groups so that every edge goes between the groups, never inside one. Think of planning two exam sessions so that no two students who share a bench sit the same session.

To check it, colour the start vertex 0, colour its neighbours 1, their neighbours 0, and so on, with BFS or DFS. If you ever find an edge whose two ends have the SAME colour, the graph is not bipartite. A graph is bipartite exactly when it has no cycle of odd length; a triangle can never be two-coloured. The graph may have several components, so start a new colouring from every uncoloured vertex. Time O(V + E).

Flood fill

Flood fill is the paint-bucket tool in a drawing app. Start at one pixel, remember its old colour, and repaint every pixel connected to it (up, down, left, right) that has that old colour. It is DFS or BFS on a grid where the edges join neighbouring pixels of the same colour. One trap: if the new colour equals the old colour, nothing should change, but a search that uses "has the old colour" as its visited test would keep finding the same pixels forever. Return straight away in that case.

Cloning a graph

To make a deep copy of a graph of node objects, walk it with BFS or DFS and keep a dictionary from each original node to its copy. Create a copy the first time you see a node; after that, always reuse the copy from the dictionary. The dictionary also works as the visited set, so cycles do not cause an endless loop.

class Node:
    def __init__(self, val, neighbors=None):
        self.val = val
        self.neighbors = neighbors if neighbors is not None else []

def clone_graph(node):
    if node is None:
        return None
    copies = {node: Node(node.val)}
    stack = [node]
    while stack:
        cur = stack.pop()
        for nb in cur.neighbors:
            if nb not in copies:
                copies[nb] = Node(nb.val)
                stack.append(nb)
            copies[cur].neighbors.append(copies[nb])
    return copies[node]

a, b = Node(1), Node(2)
a.neighbors.append(b)
b.neighbors.append(a)
c = clone_graph(a)
print(c.val, c.neighbors[0].val, c is a, c.neighbors[0].neighbors[0] is c)
# Output: 1 2 False True

Word ladder: BFS on an implicit graph

Word ladder: turn "hit" into "cog" by changing one letter at a time, where every word on the way must be in a given word list. Each word is a vertex, and two words are joined when they differ in exactly one letter. The fewest steps is a BFS question. You do not build the edges in advance: for the current word, try every position and every letter a to z, and keep the results that are in the word set. With N words of length L, that is about N × L × 26 candidates, and each set lookup hashes a string of length L.

Remove a word from the set (or mark it visited) when you add it to the queue, so it is never used twice. The usual answer counts WORDS in the sequence, so "hit → hot → dot → dog → cog" has length 5.

Common mistakes

• Checking bipartiteness only from vertex 0 when the graph has several components. Fix: loop over every vertex and colour each uncoloured one.
• Flood fill with the new colour equal to the old colour, which never ends. Fix: return the image unchanged straight away.
• Word ladder: forgetting that the end word must be in the list, or counting steps when the problem counts words. Fix: read the rule and test the smallest case.
• Clone graph: making a new copy every time a node is seen, which breaks shared neighbours and loops forever on cycles. Fix: one dictionary from original to copy.
• Recursive flood fill on a large image, causing RecursionError. Fix: an explicit stack or a queue.