When you first encounter trees and graphs, it's easy to get bogged down in the academic jargon—vertices, edges, adjacency lists, all of it. But as a software engineer, I want you to think of them more simply: they're just ways to describe things that are connected. Whether it's a folder structure on your hard drive (a tree) or a network of friends on social media (a graph), the core challenge is always the same: how do I navigate from point A to point B without getting lost or going in circles?

To make this concrete, let's build a simple Dependency Resolver. Imagine we're building a tiny package manager. Some software packages depend on other packages, which in turn depend on others. We need to figure out every single piece of software we need to install to make a specific app work.

Mapping the Dependency Web

In Python, the most flexible way to represent a graph is usually a dictionary. I'll use the package names as keys and a list of their dependencies as the values. This is essentially an adjacency list.

dependencies = {
    "WebFramework": ["DatabaseDriver", "TemplateEngine"],
    "DatabaseDriver": ["NetworkLibrary"],
    "TemplateEngine": ["NetworkLibrary", "CacheLayer"],
    "NetworkLibrary": [],
    "CacheLayer": ["NetworkLibrary"],
    "UtilityLib": ["NetworkLibrary"]
}

Looking at this, if I want to install "WebFramework", I can't just install that one package. I have to go down the rabbit hole of its dependencies, and then the dependencies of those dependencies.

Diving Deep into the Tree

The most natural way to solve this is using Depth-First Search (DFS). I'll start with the main package and recursively "dive" into each dependency until I hit a package that has no dependencies of its own.

def resolve_dependencies(package, graph):
    # Start with the package itself
    resolved = [package]
    
    for dep in graph.get(package, []):
        # Recursively find dependencies of the dependency
        resolved.extend(resolve_dependencies(dep, graph))
        
    return resolved

# Let's test it
print(resolve_dependencies("WebFramework", dependencies))
# Expected output: ['WebFramework', 'DatabaseDriver', 'NetworkLibrary', 'TemplateEngine', 'NetworkLibrary', 'CacheLayer', 'NetworkLibrary']

It works... mostly. You'll notice that "NetworkLibrary" appears three times. That's inefficient, but not a deal-breaker. However, I've just walked you straight into a classic trap.

Dealing with the Infinite Loop

Here is where I usually trip up when I'm prototyping these things: circular dependencies. What happens if "NetworkLibrary" suddenly depended on "WebFramework"? My function would call itself, which would call itself, and we'd hit a RecursionError faster than you can say "stack overflow."

To fix this, we need to keep track of where we've already been. I'll use a set to track "visited" nodes. This is the single most important pattern to remember when dealing with graphs.

def resolve_dependencies_fixed(package, graph, visited=None):
    if visited is None:
        visited = set()

    if package in visited:
        return []

    visited.add(package)
    resolved = [package]

    for dep in graph.get(package, []):
        resolved.extend(resolve_dependencies_fixed(dep, graph, visited))

    return resolved

print(resolve_dependencies_fixed("WebFramework", dependencies))
# Output: ['WebFramework', 'DatabaseDriver', 'NetworkLibrary', 'TemplateEngine', 'CacheLayer']

By passing the visited set through the recursive calls, we ensure that we only process each package once. The redundancy is gone, and the risk of an infinite loop is neutralized.

Polishing the Output

One last thing: in a real-world scenario, you can't install the "WebFramework" before you've installed the "NetworkLibrary" it relies on. The order I have right now is "top-down," but for installation, we need "bottom-up."

The trick here is to append the package to our list after the recursive calls return. This is called post-order traversal.

def resolve_dependencies_ordered(package, graph, visited=None, result=None):
    if visited is None:
        visited = set()
    if result is None:
        result = []

    if package not in visited:
        visited.add(package)
        for dep in graph.get(package, []):
            resolve_dependencies_ordered(dep, graph, visited, result)
        # Add the package ONLY after its dependencies are handled
        result.append(package)
        
    return result

print(resolve_dependencies_ordered("WebFramework", dependencies))
# Output: ['NetworkLibrary', 'DatabaseDriver', 'CacheLayer', 'TemplateEngine', 'WebFramework']

Now we have a valid installation order. We've turned a raw graph into a linear sequence of actions. That's the essence of solving graph problems: finding a way to traverse the connections while managing state so you don't repeat yourself or crash the system.

📋 Practical Task

Build a Metro Transit Route Finder

Imagine you are building a navigation app for a city's subway system. You are given a graph where the keys are station names and the values are lists of stations directly connected to them by a single track.

metro_map = {
    "Central Station": ["North Park", "West End"],
    "North Park": ["Central Station", "Airport"],
    "West End": ["Central Station", "South Beach"],
    "Airport": ["North Park"],
    "South Beach": ["West End", "East Harbor"],
    "East Harbor": ["South Beach"]
}

Write a function called can_reach(start, destination, graph) that returns True if there is a path between the two stations, and False otherwise. You must implement a way to track visited stations to avoid infinite loops, as the subway tracks go both ways.