C++ Graph Visualizer using STL Project

Advanced•1 week•graphs, BFS/DFS, STL containers

Build graphs, run BFS/DFS/Dijkstra, and watch traversals step by step.

What you will build

Create graphs with STL containers, then visualise how algorithms explore them: BFS flooding level by level, DFS diving deep, Dijkstra settling shortest paths. Rendering traversal order as numbered steps turns abstract algorithms into something you can literally watch.

What you will learn

Adjacency-list representation
BFS with a queue, DFS with a stack/recursion
Dijkstra's shortest path with a priority queue
Detecting cycles and connected components

Feature checklist

Add/remove vertices and weighted edges
BFS and DFS with step-by-step visit order
Dijkstra shortest path between two nodes
Cycle detection for directed graphs
Text-grid or coordinate-based visualisation
Load a graph from a file

Starter code

#include <iostream>
#include <vector>
#include <queue>
#include <limits>

using Graph = std::vector<std::vector<std::pair<int,int>>>; // to, weight

std::vector<int> dijkstra(const Graph& g, int src) {
    const int INF = std::numeric_limits<int>::max();
    std::vector<int> dist(g.size(), INF);
    dist[src] = 0;
    using P = std::pair<int,int>;  // distance, vertex
    std::priority_queue<P, std::vector<P>, std::greater<P>> pq;
    pq.push({0, src});
    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if (d != dist[u]) continue;          // stale entry
        for (auto [v, w] : g[u])
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
    }
    return dist;
}

int main() {
    Graph g(4);
    auto add = [&](int u, int v, int w) { g[u].push_back({v, w}); g[v].push_back({u, w}); };
    add(0, 1, 4); add(0, 2, 1); add(2, 1, 2); add(1, 3, 1); add(2, 3, 5);
    auto d = dijkstra(g, 0);
    for (size_t i = 0; i < d.size(); ++i)
        std::cout << "0 -> " << i << " : " << d[i] << "\n";  // 0,3,1,4
}

Full walkthrough

Step 1: Choose the adjacency list representation

A graph is std::vector<std::vector<Edge>> (or map from name to index plus adjacency vectors), where Edge { int to; int weight; }. Adjacency LISTS beat matrices here because real graphs are sparse, and every algorithm in this project iterates 'neighbours of v' — the list makes that the natural operation. Support adding vertices and weighted edges, and loading the whole graph from a file of 'A B 4' lines.

Step 2: BFS: the queue does the thinking

Breadth-first search visits in rings of distance: start with the source in a std::queue, mark it visited ON ENQUEUE (not on dequeue — that detail decides whether vertices enter the queue twice), then repeatedly pop the front, print it, and enqueue its unvisited neighbours. The visit order IS the output the checklist wants narrated step by step.

std::queue<int> q; q.push(s); seen[s] = true;
while (!q.empty()) {
    int v = q.front(); q.pop();
    std::cout << name[v] << ' ';
    for (auto& e : adj[v])
        if (!seen[e.to]) { seen[e.to] = true; q.push(e.to); }
}

Step 3: DFS: the same skeleton with a stack (or recursion)

Depth-first search swaps the queue for a stack — or recursion, which uses the call stack as the stack. Put both side by side in the code and the BFS/DFS difference crystallises: it is ONE data-structure choice, nothing more mystical. Same visited discipline applies.

Step 4: Dijkstra: shortest paths with a priority queue

dist[] starts at infinity (std::numeric_limits<int>::max()) except the source (0); a min-priority queue of (dist, vertex) pairs drives it: pop the closest unsettled vertex, relax each edge — if dist[v] + w < dist[to], update dist[to], record the predecessor, push the new pair. Stale queue entries (a vertex popped with a worse dist than known) are skipped, not feared. The predecessor array is what turns 'distance 4' into the PATH A → C → B → D.

Step 5: Cycle detection for directed graphs

DFS with three states per vertex — unvisited, IN PROGRESS (on the current recursion stack), done. Reaching an IN PROGRESS vertex means a back edge, which means a cycle. Two states are not enough: a done vertex reached again is just a cross edge in a DAG, and flagging it as a cycle is the classic false positive.

Step 6: Visualise as text, honestly

Print the graph as an adjacency listing with weights, and for small graphs an ASCII layout on a coordinate grid if vertices carry positions. The checklist allows text-grid visualisation — a clear adjacency printout plus traversal orders teaches more than a cramped ASCII drawing, so make the listing beautiful instead of the picture ambitious.

Step 7: Test on a graph you can verify by hand

Edges: A-B 4, A-C 1, C-B 2, B-D 1, C-D 5. By hand: BFS from A visits A, then B and C (ring 1), then D. Dijkstra A→D: A→C (1), C→B (3 total), B→D (4 total) beats A→B→D (5) and A→C→D (6) — answer 4 via C, B. If the program disagrees with your hand-derived answers, the program is wrong; hand-verifiable examples are the only honest tests for algorithm code.

Common mistakes

Marking BFS vertices visited when DEQUEUED, so the same vertex is enqueued by several neighbours and printed twice.
Forgetting that std::priority_queue is a MAX-heap — Dijkstra needs std::greater or negated distances for the min-heap behaviour.
Running Dijkstra on a graph with a negative edge weight and trusting the answer; the algorithm's core assumption is non-negative weights.

Compile and run

g++ -std=c++17 -o graph graph.cpp

Sample run

$ ./graph
Loaded graph.txt — 4 vertices, 5 weighted edges
1) BFS  2) DFS  3) Dijkstra  4) Cycle check  0) Exit
> 1
Start vertex:
> A
BFS visit order: A B C D
1) BFS  2) DFS  3) Dijkstra  4) Cycle check  0) Exit
> 2
Start vertex:
> A
DFS visit order: A B D C
> 3
From:
To:
> D
Shortest distance: 4
Path: A -> C -> B -> D  (1 + 2 + 1)
> 0

Try it in your browser

No browser demo is included for this project. Build the C++ version below — that is the real program.

Related Advanced projects

← All 60 projects · Classic site (Learn & Sandbox)