Graph

In Turkish: Çizge

Updated September 30, 20263 min read

In short

A graph is a data structure made of nodes, called vertices, connected by edges, and is used to model relationships such as roads, friendships, and dependencies.

What is a graph data structure?

A graph is a set of nodes, also called vertices, plus a set of edges that connect pairs of nodes. Unlike a tree, a graph has no root and no parent-child rule: any node can connect to any other, and edges can form cycles. Graphs can be directed, where each edge points one way like a one-way street, or undirected, where edges work in both directions. They can also be weighted, meaning each edge carries a value such as distance, cost, or time.

Programs usually store a graph as an adjacency list, which maps each node to the list of its neighbors and uses O(V + E) memory, where V is the number of vertices and E is the number of edges. The alternative is an adjacency matrix, a V by V grid that checks whether two nodes are connected in O(1) time but always uses O(V^2) memory. Breadth-first search (BFS) and depth-first search (DFS) visit every reachable node in O(V + E) time with an adjacency list; BFS finds the path with the fewest edges, while Dijkstra's algorithm finds the cheapest path when edge weights are non-negative.

A subway map is a good mental model: stations are nodes and the tracks between them are edges. Graphs model social networks (people and friendships), navigation (intersections and roads), the web (pages and links), computer networks, and package managers, which build a dependency graph to decide what to install. Build tools and task schedulers rely on a directed acyclic graph (DAG), a directed graph with no cycles, so tasks can be ordered such that each one runs after everything it depends on.

In computer science, a graph is not a chart or a plot of data; it is a model of connections. A tree is a special case of a graph that is connected and has no cycles. Because general graphs can contain cycles, traversal code must keep track of which nodes it has already visited, or it can loop forever.

Key takeaways

A graph is a set of nodes (vertices) connected by edges.
Edges can be directed or undirected, and weighted or unweighted.
An adjacency list uses O(V + E) memory and is the usual choice for sparse graphs, which have relatively few edges.
BFS and DFS visit every reachable node in O(V + E) time.
Traversals must track visited nodes, because graphs can contain cycles.

Example

Finding every dependency with depth-first searchpython

# A directed graph as an adjacency list: package -> packages it depends on
graph = {"app": ["auth", "db"], "auth": ["db", "crypto"], "db": [], "crypto": []}

def dfs(node, seen):
    # Depth-first search: follow each edge, skipping nodes already visited
    seen.add(node)
    for neighbor in graph[node]:
        if neighbor not in seen:
            dfs(neighbor, seen)
    return seen

print(sorted(dfs("app", set())))  # ['app', 'auth', 'crypto', 'db']

Readers ask

What is the difference between a graph and a tree?

A tree is a graph with extra rules: it is connected, has no cycles, and usually has a single root. A graph can have cycles, several disconnected parts, and any pattern of connections.

What is a directed acyclic graph (DAG)?

A DAG is a directed graph with no cycles, so following the edges can never lead back to where you started. DAGs model dependencies, such as build steps, data pipelines, and the history of commits in Git.

When should I use BFS instead of DFS?

Use breadth-first search when you need the shortest path by number of edges, because it explores nodes in order of distance from the start. Use depth-first search to explore all paths, detect cycles, or order dependencies; both run in O(V + E) time.