A graph is a network of connections, made up of points called vertices joined together by lines called edges. Each vertex can connect to any other vertex in the network, which makes graphs versatile for real-world problems like mapping roads between cities or modeling friendships on social media. Unlike trees, where connections flow in one direction from parent to child, graphs can have connections going any way between their vertices.

Graphs let us modify and analyze the connections in our network. Common tasks include adding new edges, removing connections, and finding paths between vertices. The efficiency of these operations depends on how we store the graph and which algorithms we use.

Some graph algorithms use a mathematical concept called the Inverse Ackermann function, written as α(n). The math itself isn't important here. What matters is that the function grows so slowly that an O(α(n)) algorithm is practically as fast as an instant operationfor any input you'll encounter.

Think of a graph like a map where vertices are locations and edges are the roads connecting them. Each vertex (or location) can store information, and it keeps track of all the other vertices it's directly connected to. Those are called adjacent vertices. Just like you can follow roads from one place to another, you can follow edges to trace a path through the graph.

class GraphNode:
    def __init__(self, val: int):
        self.val = val
        self.neighbors = []  # List of adjacent vertices

Sometimes a path leads you back to where you started. That's called a cycle. In a social network, it would be like starting at one friend, walking through their connections, and eventually arriving back at the original friend through a chain of mutual friendships.

Adjacency lists are one way to represent a graph. Think of a contact list in your phone: each person (vertex) has their own list of friends (adjacent vertices). We build it with a hashmap, where the key is the person's name and the value is their list of friends. Finding all of someone's connections is just a hashmap lookup.

# Building adjacency list from edges - O(E)
def buildAdjacencyList(edges: List[List[int]]) -> Dict[int, List[int]]:
    adjacencyList = defaultdict(list)
    for src, dst in edges:
        adjacencyList[src].append(dst)
    return adjacencyList

# Example: edges = [[0,1], [0,2], [1,2], [2,3]]
# Result: {0: [1, 2], 1: [2], 2: [3]}

To build the list, we start with a list of edges: pairs of source and destination vertices. Each pair tells us that two vertices are connected, the same way you'd build a social network one friendship at a time. The result is a clean, lookup-friendly view of every connection in the graph.

An adjacency matrix is like a giant checklist showing who's connected to whom. Imagine a spreadsheet where both rows and columns list all the people (vertices), with a 1 in cells where two people are friends and 0where they're not. Since every vertex needs a row and column to show every possible connection, the result is a square grid.

Adjacency matrices are like using an entire phone book to store just a handful of phone numbers. They waste a lot of space. Most cells contain zeros because in real networks, each vertex is only connected to a few others. Adjacency lists are usually the better choice: each person keeps their own contact list of just their friends, which saves both space and time.

Think of graph directionality like different types of relationships. In undirected graphs, connections work both ways. Friendship on Facebook is a good example: if you're friends with someone, they're also friends with you. These two-way relationships are shown as simple lines between vertices.

Directed graphs (or digraphs) have one-way connections. Following someone on Twitter is a good example: you can follow them, but they might not follow you back. These one-way relationships are shown as arrows pointing from one vertex to another. The vertex where the arrow starts is called the source, and where it ends is the destination.

This difference in direction changes how we work with graphs. In undirected graphs, we can travel along any edge in either direction. In directed graphs, we can only follow the arrows in their specified direction. This matters when finding paths or checking whether two vertices are connected. Just because you can reach vertex B from vertex Adoesn't mean you can get back to A from B in a directed graph.

Think of weighted graphs like a map where each road (edge) has extra information attached. Just like roads have distances, speed limits, or toll costs, weighted graphs assign values to their connections. These weights could represent anything measurable: miles between cities, minutes to travel, or dollars to spend.

# Building weighted adjacency list - O(E)
def buildWeightedGraph(edges: List[List[int]]) -> Dict[int, List[tuple]]:
    adjacencyList = defaultdict(list)
    for src, dst, weight in edges:
        adjacencyList[src].append((dst, weight))
    return adjacencyList

# Example: edges = [[0,1,4], [0,2,1], [2,1,2]]
# Result: {0: [(1, 4), (2, 1)], 2: [(1, 2)]}

Weighted graphs solve real-world problems like finding the shortest route between two locations or building the cheapest network of connections. The weights can be any number, even negative in some cases, and they change how you approach the problem entirely. Instead of finding any path between two points, you now need to consider the total weight of the path to find the optimal route.

A cycle in a graph is a circular path. You can start at any vertex, follow the connections, and eventually return to where you started. Think of visiting different friends' houses and eventually arriving back at the first one. Cycles matter because they often represent patterns or dependencies in the graph.

Cycles behave differently in directed and undirected graphs. In undirected graphs, cycles are easier to detect because we can move in any direction. In directed graphs, cycles are trickier because we have to follow the direction of the arrows. We often detect cycles in directed graphs using topological sorting, which fails the moment it hits a cycle since you can't order vertices that depend on each other in a loop.

# Detect cycle in directed graph using DFS - O(V + E)
def hasCycle(adjacencyList: Dict[int, List[int]], n: int) -> bool:
    # 0: unvisited, 1: in current path, 2: completed
    state = [0] * n

    def dfs(node: int) -> bool:
        state[node] = 1  # Mark as in current path

        for neighbor in adjacencyList.get(node, []):
            if state[neighbor] == 1:  # Found cycle
                return True
            if state[neighbor] == 0 and dfs(neighbor):
                return True

        state[node] = 2  # Mark as completed
        return False

    # Check all nodes (graph might be disconnected)
    for node in range(n):
        if state[node] == 0 and dfs(node):
            return True
    return False

One common way to find cycles is a depth-first searchthat tracks the nodes we're currently visiting. If we hit a node that's already on the current path, we've found a cycle. This is essential for task scheduling (where cycles cause deadlocks) and dependency management (where circular dependencies have to be caught early).

Graphs are flexible enough to represent almost any kind of relationship, which is why they show up so often in coding interviews. Here are a few tips for solving graph problems well:

Graphs feel intimidating until you realize most problems boil down to "traverse the right nodes in the right order." Work through these to build intuition for representing graphs, detecting cycles, and applying the classic patterns that make hard problems collapse: