Z

Graph Algorithms

BFS, DFS, Dijkstra & A* — pathfinding and traversal, visualized

A graph is just a set of nodes connected by edges — it models road networks, social connections, dependency chains and game maps alike. Graph algorithms answer two recurring questions: can I reach this node? and what is the cheapest way to get there?

Traversal: BFS vs DFS

Breadth-first search (BFS) explores a graph layer by layer using a queue, visiting all neighbours at distance 1 before distance 2. On an unweighted graph this finds the shortest path in terms of edge count. Depth-first search (DFS) instead follows one branch as far as it can using a stack (or recursion) before backtracking — ideal for cycle detection, topological sorting and maze generation. Both run in O(V + E) time.

Shortest paths: Dijkstra & A*

When edges carry weights (distances, costs, times), Dijkstra’s algorithm greedily settles the nearest unvisited node, guaranteeing the shortest path from a source to every other node in O((V + E) log V) with a priority queue. A* speeds this up for point-to-point queries by adding a heuristic that biases the search toward the goal — the same core relaxation step, just better-informed.

Where graphs show up

GPS routing, network packet forwarding, social-graph friend suggestions, build-system dependency ordering and game-AI pathfinding are all graph problems underneath. Master the four algorithms below and you have the toolkit for most of them. Drive each one yourself and watch the frontier expand in real time.

Try it interactively

Breadth-First Search (BFS) Visualizer

Interactive breadth-first search on a grid — draw walls, move start/goal, generate mazes, step through the level-by-level expansion. Runs in your browser.

Open tool

Depth-First Search (DFS) Visualizer

Interactive depth-first search on a grid — draw walls, move start/goal, generate mazes, step through the deep-dive exploration. Runs in your browser.

Open tool

Dijkstra's Algorithm Visualizer

Interactive Dijkstra pathfinding on a grid — draw walls, move start/goal, generate mazes, step through the search. Runs in your browser.

Open tool

A* Pathfinding Visualizer

Interactive A* pathfinding on a grid with a Manhattan heuristic — draw walls, move start/goal, generate mazes, step through the search. Runs in your browser.

Open tool

Maze Generator

Animated maze generator using recursive division — step through the wall carving, adjust speed, regenerate. Pairs with the pathfinding visualizers. Runs in your browser.

Open tool

Prefer a focused tool?

Frequently asked questions

What is the difference between BFS and DFS?

BFS explores a graph level by level using a queue and finds the shortest path on unweighted graphs; DFS dives down one branch at a time using a stack or recursion and is better suited to cycle detection and topological sorting. Both visit every node and edge once, so both run in O(V + E) time.

When should I use A* instead of Dijkstra?

Use Dijkstra when you need shortest paths from one source to all nodes, or when no good heuristic exists. Use A* for point-to-point pathfinding where you can estimate the remaining distance to the goal (e.g. straight-line distance on a map) — the heuristic lets A* explore far fewer nodes.

Why does Dijkstra need a priority queue?

Dijkstra always expands the closest unsettled node next. A priority queue (min-heap) returns that node in O(log V), giving the overall O((V + E) log V) runtime. Without it you would scan all nodes each step, degrading to O(V²).

Does Dijkstra work with negative edge weights?

No. Dijkstra assumes that once a node is settled its distance is final, which breaks when a negative edge could later offer a cheaper path. Use the Bellman–Ford algorithm for graphs with negative weights.