How to Implement Graph in C++: Syntax and Example

To implement a graph in C++, use an adjacency list represented by a vector of vectors or a vector of lists. Each index represents a node, and the inner container holds connected nodes. You can add edges by updating these lists to represent connections.

Syntax

A graph can be represented using an adjacency list in C++ as std::vector>. Each vector index corresponds to a node, and the inner vector stores its neighbors.

To add an edge, push the connected node into the vector of the source node. For undirected graphs, add edges in both directions.

cpp

std::vector<std::vector<int>> graph(n); // n is number of nodes
// Add edge from node u to node v
graph[u].push_back(v);
// For undirected graph, also add:
graph[v].push_back(u);

Example

This example creates an undirected graph with 5 nodes and adds edges between them. It then prints the adjacency list showing each node's neighbors.

cpp

#include <iostream>
#include <vector>

int main() {
    int n = 5; // number of nodes
    std::vector<std::vector<int>> graph(n);

    // Adding edges (undirected)
    graph[0].push_back(1);
    graph[1].push_back(0);

    graph[0].push_back(4);
    graph[4].push_back(0);

    graph[1].push_back(2);
    graph[2].push_back(1);

    graph[1].push_back(3);
    graph[3].push_back(1);

    graph[1].push_back(4);
    graph[4].push_back(1);

    graph[2].push_back(3);
    graph[3].push_back(2);

    graph[3].push_back(4);
    graph[4].push_back(3);

    // Print adjacency list
    for (int i = 0; i < n; i++) {
        std::cout << "Node " << i << ": ";
        for (int neighbor : graph[i]) {
            std::cout << neighbor << " ";
        }
        std::cout << "\n";
    }

    return 0;
}

Output

Node 0: 1 4 
Node 1: 0 2 3 4 
Node 2: 1 3 
Node 3: 1 2 4 
Node 4: 0 1 3 

Common Pitfalls

• Forgetting to add edges in both directions in undirected graphs causes incomplete connections.
• Using incorrect indices outside the vector size causes runtime errors.
• Confusing adjacency matrix with adjacency list; adjacency list is more memory efficient for sparse graphs.

cpp

/* Wrong: Only one direction added in undirected graph */
graph[u].push_back(v); // Missing graph[v].push_back(u);

/* Right: Add edges both ways */
graph[u].push_back(v);
graph[v].push_back(u);

Quick Reference

Use std::vector> for adjacency list. Add edges with push_back(). Remember to add edges both ways for undirected graphs. Access neighbors by iterating inner vectors.

Operation	Code Example	Description
Create graph	std::vector> graph(n);	Create graph with n nodes
Add edge (directed)	graph[u].push_back(v);	Add edge from u to v
Add edge (undirected)	graph[u].push_back(v); graph[v].push_back(u);	Add edges both ways
Iterate neighbors	for (int nbr : graph[u]) { ... }	Access neighbors of node u

Key Takeaways

Use adjacency list with vectors to represent graphs efficiently in C++.

Add edges in both directions for undirected graphs to maintain correct connections.

Always check node indices to avoid out-of-range errors.

Iterate inner vectors to access neighbors of each node.

Adjacency lists save memory compared to adjacency matrices for sparse graphs.