Graphs

Beginner · 18 min read · Data Structures Basics, Trees, Heaps & Graphs

Nodes and edges: directed, weighted, cyclic; adjacency lists vs matrices; BFS and DFS.

A graph is the most general way to describe things and the connections between them: cities and roads, people and friendships, web pages and links, courses and prerequisites, cells in a maze. Trees and linked lists are special cases.

Types of graph

The vocabulary to know:

How a graph is stored

There are three representations. Interviews almost always want the first:

The two traversals

BFS reaches nodes in order of distance, so the first time it sees a node, it has found the fewest edges to it. Use it for shortest paths in unweighted graphs and anything "level by level".

Operations and their cost (adjacency list)

Which graph algorithm when?

Interview questions

• When would you use an adjacency matrix instead of an adjacency list?
• Why does BFS find shortest paths in an unweighted graph but DFS doesn't?

Further reading

Key takeaways

• A graph is nodes plus edges between any pairs: directed or undirected, weighted or not, cyclic or acyclic.
• Store it as an adjacency list (O(V + E)); build one from the edge list first. Grids are implicit graphs.
• BFS uses a queue, explores ring by ring, and gives the fewest edges.
• DFS uses recursion or a stack, goes deep, and finds components and cycles.
• Both are O(V + E). Always keep a visited set, and start from every node if the graph may be disconnected.

Previous: Heaps & Priority Queues · Next: Choosing a Data Structure