C++ Program to Implement a Graph Using Adjacency List

by

Introduction

Graphs are fundamental data structures used to represent networks of connected nodes. Whether you’re modeling a social network, transportation routes, or the relationships between tasks in a project, graphs are a powerful way to represent these connections. One common way to implement a graph in programming is through an adjacency list. In this article you will learn how to implement a graph using an adjacency list in C++ we will write three real examples with their outputs.

Prerequisites

Before diving into the examples, it’s important to understand the following concepts:

  • Graph: A collection of nodes (vertices) and edges connecting some or all of them.
  • Adjacency List: A way to represent a graph where each vertex has a list of all the vertices it is connected to.
  • Directed and Undirected Graphs: In a directed graph, edges have a direction, while in an undirected graph, edges do not.

Familiarity with C++ programming, including standard libraries like <iostream>, <vector>, and <list>, will be beneficial.

Implementing a Graph Using Adjacency List

To represent a graph using an adjacency list in C++, we typically use a vector of lists. Each index of the vector represents a vertex, and the list at each index contains the vertices adjacent to that vertex.

Pseudocode for Graph Representation

  1. Define a class for the graph.
  2. Initialize a vector of lists.
  3. Implement methods to add edges and display the graph.

Examples

Example 1: Simple Undirected Graph

Graph Representation

Consider a simple undirected graph with four vertices:

C++
    (A)---(B)
     |     |
    (C)---(D)

C++ Program

C++
#include <iostream>
#include <vector>
#include <list>

using namespace std;

class Graph {
    int V; // Number of vertices
    vector<list<int>> adjList;

public:
    Graph(int V);
    void addEdge(int v, int w);
    void printGraph();
};

Graph::Graph(int V) {
    this->V = V;
    adjList.resize(V);
}

void Graph::addEdge(int v, int w) {
    adjList[v].push_back(w);
    adjList[w].push_back(v);
}

void Graph::printGraph() {
    for (int v = 0; v < V; ++v) {
        cout << "Vertex " << v << ":";
        for (auto x : adjList[v])
            cout << " -> " << x;
        cout << endl;
    }
}

int main() {
    Graph g(4);
    g.addEdge(0, 1);
    g.addEdge(0, 2);
    g.addEdge(1, 3);
    g.addEdge(2, 3);

    g.printGraph();

    return 0;
}

Output

C++
Vertex 0: -> 1 -> 2
Vertex 1: -> 0 -> 3
Vertex 2: -> 0 -> 3
Vertex 3: -> 1 -> 2

Example 2: Directed Graph

Graph Representation

Consider a directed graph with four vertices:

C++
    (A)---->(B)
     ^      /|
     |     / |
    (C)<--/  |
         \   v
          ->(D)

C++ Program

C++
#include <iostream>
#include <vector>
#include <list>

using namespace std;

class Graph {
    int V;
    vector<list<int>> adjList;

public:
    Graph(int V);
    void addEdge(int v, int w);
    void printGraph();
};

Graph::Graph(int V) {
    this->V = V;
    adjList.resize(V);
}

void Graph::addEdge(int v, int w) {
    adjList[v].push_back(w);
}

void Graph::printGraph() {
    for (int v = 0; v < V; ++v) {
        cout << "Vertex " << v << ":";
        for (auto x : adjList[v])
            cout << " -> " << x;
        cout << endl;
    }
}

int main() {
    Graph g(4);
    g.addEdge(0, 1);
    g.addEdge(1, 3);
    g.addEdge(1, 2);
    g.addEdge(2, 0);
    g.addEdge(3, 2);

    g.printGraph();

    return 0;
}

Output

C++
Vertex 0: -> 1
Vertex 1: -> 3 -> 2
Vertex 2: -> 0
Vertex 3: -> 2

Example 3: Graph with Weighted Edges

Graph Representation

Consider a graph with weighted edges:

C++
    (A)--2--(B)
     |      /|
    4|     3 |
     |    /  |
    (C)--5--(D)

C++ Program

C++
#include <iostream>
#include <vector>
#include <list>
#include <utility>

using namespace std;

class Graph {
    int V;
    vector<list<pair<int, int>>> adjList;

public:
    Graph(int V);
    void addEdge(int v, int w, int weight);
    void printGraph();
};

Graph::Graph(int V) {
    this->V = V;
    adjList.resize(V);
}

void Graph::addEdge(int v, int w, int weight) {
    adjList[v].push_back(make_pair(w, weight));
    adjList[w].push_back(make_pair(v, weight));
}

void Graph::printGraph() {
    for (int v = 0; v < V; ++v) {
        cout << "Vertex " << v << ":";
        for (auto x : adjList[v])
            cout << " -> " << x.first << " (weight " << x.second << ")";
        cout << endl;
    }
}

int main() {
    Graph g(4);
    g.addEdge(0, 1, 2);
    g.addEdge(0, 2, 4);
    g.addEdge(1, 3, 3);
    g.addEdge(2, 3, 5);

    g.printGraph();

    return 0;
}

Output

C++
Vertex 0: -> 1 (weight 2) -> 2 (weight 4)
Vertex 1: -> 0 (weight 2) -> 3 (weight 3)
Vertex 2: -> 0 (weight 4) -> 3 (weight 5)
Vertex 3: -> 1 (weight 3) -> 2 (weight 5)

Conclusion

Implementing a graph using an adjacency list in C++ is a versatile and efficient way to represent complex networks. Through the provided examples, we’ve demonstrated how to implement and use adjacency lists for both undirected and directed graphs, as well as graphs with weighted edges