Understanding Adjacency Matrices in C++: A Beginner’s Guide

by | C++, DSA, Graphs

In this guide, we’ll explore how to implement an adjacency matrix in C++, a fundamental data structure for representing graphs. We’ll cover both the theoretical aspects and practical implementation, including common operations and optimizations.

Table of Contents

Introduction

An adjacency matrix is a square matrix used to represent a finite graph. The elements of the matrix indicate whether pairs of vertices are adjacent or not in the graph. This representation allows us to perform various graph operations efficiently and is particularly useful for dense graphs.

Key Concepts

  • For an unweighted graph, matrix elements are typically 1 (adjacent) or 0 (not adjacent)
  • For a weighted graph, matrix elements represent edge weights
  • For an undirected graph, the matrix is symmetric
  • For a directed graph, the matrix may be asymmetric
📚 Key Terms: Adjacency Matrix Concepts
Adjacency Matrix
A square matrix used to represent a finite graph, where entries indicate whether pairs of vertices are adjacent or not. For an n-vertex graph, it is an n × n matrix.
Dense Graph
A graph where the number of edges is close to the maximum possible number of edges. Adjacency matrices are particularly efficient for dense graphs.
Sparse Graph
A graph where the number of edges is much less than the maximum possible number of edges (|E| ≪ |V|²). Consider using adjacency lists for sparse graphs.
Edge Weight
A numerical value associated with an edge, representing distance, cost, capacity, or any other metric. In weighted graphs, matrix entries store these weights instead of boolean values.
Vertex Degree
The number of edges connected to a vertex. In an adjacency matrix, it’s the sum of either a row or column (for undirected graphs) or both (for directed graphs).
Self-Loop
An edge that connects a vertex to itself. Represented by non-zero elements on the main diagonal of the adjacency matrix.
Symmetric Matrix
A matrix equal to its transpose. The adjacency matrix of an undirected graph is always symmetric because if vertex i connects to j, j also connects to i.
Space Complexity
The amount of memory required to store the graph. For an adjacency matrix, it’s O(V²) where V is the number of vertices, regardless of the number of edges.
Time Complexity
The time required for graph operations. Edge queries take O(1) time, while vertex operations like finding all neighbors take O(V) time.
Directed Graph
A graph where edges have direction. The adjacency matrix of a directed graph may be asymmetric, as an edge from i to j doesn’t imply an edge from j to i.
Path
A sequence of vertices connected by edges. In an adjacency matrix, paths of length k between vertices can be found using matrix multiplication k times.
Connected Component
A subset of vertices where every vertex is reachable from every other vertex. Can be identified using operations on the adjacency matrix.

Mathematical Background

An adjacency matrix is simply a way to represent connections between vertices in a graph using a 2D grid of numbers. Let’s look at a simple example:

0 1 2 3 0 1 1 0 1 0 1 1 1 1 0 1 0 1 1 0

How to Read the Matrix

Reading an adjacency matrix is straightforward:

  • Each row and column represents a vertex (numbered from 0 to n-1)
  • A 1 in position \([i][j]\) means there’s an edge from vertex i to vertex j
  • A 0 means there’s no edge between those vertices

For example, in the matrix above:

  • Position \([0][1]\) is 1, showing vertex 0 connects to vertex 1
  • Position \([0][3]\) is 0, showing no direct connection between vertices 0 and 3
  • The matrix is symmetric (same values on both sides of the diagonal) because this is an undirected graph

Key Properties

  1. Symmetry (Undirected Graphs):

    For an undirected graph, if there’s an edge from i to j, there’s also one from j to i: \[ A_{ij} = A_{ji} \]

  2. Diagonal Elements:

    For simple graphs (no self-loops), diagonal elements are zero: \[ A_{ii} = 0 \]

  3. Vertex Degree:

    The sum of any row (or column in undirected graphs) gives the vertex’s degree: \[ \text{degree}(v_i) = \sum_{j=1}^{|V|} A_{ij} \]

Space and Time Complexity

  • Space Required: \( O(|V|^2) \) where |V| is the number of vertices
  • Edge Query Time: \( O(1) \) – constant time to check if two vertices are connected
  • Memory Usage:
    • Unweighted: \( |V|^2 \) bits
    • Weighted: \( |V|^2 \times \text{size of weight type} \)

Note: While adjacency matrices provide constant-time edge queries, they may not be memory-efficient for sparse graphs where |E| ≪ |V|². For sparse graphs, consider using adjacency lists instead.

Implementation

Now that we understand how adjacency matrices work conceptually, let’s implement one in C++. We’ll take a structured approach, starting with a basic implementation and gradually adding more sophisticated features. Our implementation will use modern C++ practices and focus on clarity and reliability.

Basic Implementation

We’ll start by creating a Graph class that encapsulates our adjacency matrix. The class will support both directed and undirected graphs, with the latter being the default. Here’s what our implementation includes:

  • A 2D vector to store the adjacency matrix
  • Basic operations like adding and removing edges
  • Safety checks to prevent invalid operations
  • A way to visualize the matrix through console output
Basic Adjacency Matrix Class
// Required standard libraries
#include <vector>     // For adjacency matrix storage using 2D vector
#include <iostream>   // For matrix printing functionality
#include <stdexcept>  // For throwing out_of_range exceptions

// Graph class implementing a basic adjacency matrix representation
// Supports both directed and undirected graphs with fundamental operations
class Graph {
private:
    std::vector<std::vector<int>> adjacencyMatrix;  // 2D vector for storing edges (0 or 1)
    int numVertices;                            // Total number of vertices in the graph
    bool isDirected;                           // Flag indicating if graph is directed

public:
    // Constructor creates an empty graph with specified number of vertices
    // Parameters:
    //   vertices: Number of vertices in the graph
    //   directed: Whether the graph is directed (default: false)
    Graph(int vertices, bool directed = false)
        : numVertices(vertices), isDirected(directed) {
        // Create a vertices × vertices matrix initialized with zeros
        // Each element [i][j] represents an edge from vertex i to vertex j
        adjacencyMatrix.resize(vertices, std::vector<int>(vertices, 0));
    }

    // Adds an edge between two vertices
    // Parameters:
    //   from: Source vertex
    //   to: Destination vertex
    // Throws:
    //   std::out_of_range if either vertex index is invalid
    void addEdge(int from, int to) {
        // Validate both vertex indices
        if (from >= numVertices || to >= numVertices || from < 0 || to < 0) {
            throw std::out_of_range("Vertex index out of bounds");
        }

        // Add edge from source to destination
        adjacencyMatrix[from][to] = 1;

        // For undirected graphs, also add edge from destination to source
        // This maintains symmetry in the adjacency matrix
        if (!isDirected) {
            adjacencyMatrix[to][from] = 1;
        }
    }

    // Checks if an edge exists between two vertices
    // Parameters:
    //   from: Source vertex
    //   to: Destination vertex
    // Returns:
    //   true if edge exists, false otherwise or if indices invalid
    bool hasEdge(int from, int to) const {
        // Return false for invalid indices instead of throwing
        // This makes the method more convenient for queries
        if (from >= numVertices || to >= numVertices || from < 0 || to < 0) {
            return false;
        }
        return adjacencyMatrix[from][to] == 1;
    }

    // Removes an edge between two vertices
    // Parameters:
    //   from: Source vertex
    //   to: Destination vertex
    // Throws:
    //   std::out_of_range if either vertex index is invalid
    void removeEdge(int from, int to) {
        // Validate both vertex indices
        if (from >= numVertices || to >= numVertices || from < 0 || to < 0) {
            throw std::out_of_range("Vertex index out of bounds");
        }

        // Remove edge from source to destination
        adjacencyMatrix[from][to] = 0;

        // For undirected graphs, also remove edge from destination to source
        // This maintains symmetry in the adjacency matrix
        if (!isDirected) {
            adjacencyMatrix[to][from] = 0;
        }
    }

    // Prints the adjacency matrix representation of the graph
    // Output format:
    //   - One row per line
    //   - Elements separated by spaces
    //   - 1 indicates edge presence, 0 indicates no edge
    void print() const {
        // Iterate through each row and column
        for (int i = 0; i < numVertices; i++) {
            for (int j = 0; j < numVertices; j++) {
                // Print each element followed by a space
                std::cout << adjacencyMatrix[i][j] << " ";
            }
            // Start new line after each row
            std::cout << "\n";
        }
    }
};

Let's break down the key components of this implementation:

  • The constructor takes the number of vertices and an optional parameter for directed/undirected nature
  • addEdge and removeEdge methods handle both directed and undirected cases automatically
  • The hasEdge method provides a safe way to check for connections
  • All methods include bounds checking to prevent buffer overflows

Usage Example

To demonstrate how our implementation works in practice, let's create the same graph we visualized earlier. This example shows how to:

  • Initialize a new graph
  • Add edges to create our desired structure
  • Query the graph for information about its connections
Example Usage
int main() {
    // Create an undirected graph with 4 vertices
    Graph g(4);

    // Add edges to create the graph from our visual example
    g.addEdge(0, 1);  // Connect vertex 0 to 1
    g.addEdge(0, 2);  // Connect vertex 0 to 2
    g.addEdge(1, 2);  // Connect vertex 1 to 2
    g.addEdge(1, 3);  // Connect vertex 1 to 3
    g.addEdge(2, 3);  // Connect vertex 2 to 3

    std::cout << "Adjacency Matrix:\n";
    g.print();

    std::cout << "\nEdge between 0 and 1: "
              << (g.hasEdge(0, 1) ? "Yes" : "No") << "\n";
    std::cout << "Edge between 0 and 3: "
              << (g.hasEdge(0, 3) ? "Yes" : "No") << "\n";

    return 0;
}
Adjacency Matrix:
0 1 1 0
1 0 1 1
1 1 0 1
0 1 1 0

Edge between 0 and 1: Yes
Edge between 0 and 3: No

Extended Functionality

While our basic implementation is functional, real-world applications often require more sophisticated analysis capabilities. Let's enhance our graph implementation with robust features for analyzing graph structure.

Understanding Graph Connectivity

In directed graphs, we have two important types of connectivity:

  • Strongly Connected: A directed graph is strongly connected if there exists a path between any two vertices in both directions. This means for every pair of vertices u and v:
    • You can reach v from u
    • You can also reach u from v
  • Weakly Connected: A directed graph is weakly connected if it would be connected when you ignore the direction of edges (treat them as undirected). This is a weaker condition because:
    • It only requires the existence of paths when edge direction is ignored
    • A strongly connected graph is always weakly connected, but not vice versa
Enhanced Graph Class Implementation
// Graph class implementing an adjacency matrix representation
// Supports both directed and undirected graphs with various analysis features
class Graph {
private:
    std::vector<std::vector<int>> adjacencyMatrix;  // 2D vector representing the graph
    int numVertices;                            // Total number of vertices
    bool isDirected;                           // Whether the graph is directed

    // Helper method to validate vertex indices
    void validateVertex(int vertex) const {
        if (vertex >= numVertices || vertex < 0) {
            throw std::out_of_range("Vertex index out of bounds");
        }
    }

    // Unified DFS implementation that can be used for multiple purposes:
    // - Basic graph traversal
    // - Kosaraju's algorithm (with order tracking)
    // - Custom adjacency matrix traversal
    void dfs(int vertex,                            // Current vertex
             std::vector<bool>& visited,            // Track visited vertices
             const std::vector<std::vector<int>>& matrix,  // Adjacency matrix to use
             std::vector<int>* order = nullptr) const {     // Optional: track vertex order
        visited[vertex] = true;  // Mark current vertex as visited

        // Explore all adjacent vertices
        for (int i = 0; i < numVertices; i++) {
            if (matrix[vertex][i] && !visited[i]) {  // If edge exists and vertex unvisited
                dfs(i, visited, matrix, order);      // Recursive DFS call
            }
        }

        // If order tracking is enabled (for Kosaraju's algorithm)
        if (order) {
            order->push_back(vertex);  // Add vertex to order after exploring all neighbors
        }
    }

    // Creates the transpose of the graph (reverses all edges)
    // Used in Kosaraju's algorithm for strong connectivity testing
    std::vector<std::vector<int>> getTranspose() const {
        std::vector<std::vector<int>> transpose(numVertices,
            std::vector<int>(numVertices, 0));

        // Swap indices to reverse edges
        for (int i = 0; i < numVertices; i++) {
            for (int j = 0; j < numVertices; j++) {
                transpose[j][i] = adjacencyMatrix[i][j];
            }
        }
        return transpose;
    }

    // Creates an undirected version of the graph
    // Used for weak connectivity testing
    std::vector<std::vector<int>> getUndirected() const {
        auto undirected = adjacencyMatrix;
        // If either direction has an edge, add edges in both directions
        for (int i = 0; i < numVertices; i++) {
            for (int j = 0; j < numVertices; j++) {
                if (adjacencyMatrix[i][j] || adjacencyMatrix[j][i]) {
                    undirected[i][j] = undirected[j][i] = 1;
                }
            }
        }
        return undirected;
    }

public:
    // Enum for specifying edge direction when getting neighbors
    enum class EdgeType {
        OUTGOING,    // Only outgoing edges
        INCOMING,    // Only incoming edges
        BOTH        // Both incoming and outgoing edges
    };

    // Constructor initializes an empty graph
    Graph(int vertices, bool directed = false)
        : numVertices(vertices), isDirected(directed) {
        adjacencyMatrix.resize(vertices,
            std::vector<int>(vertices, 0));  // Initialize with zeros
    }

    // Gets neighbors of a vertex based on specified edge direction
    std::vector<int> getNeighbors(int vertex, EdgeType type = EdgeType::OUTGOING) const {
        validateVertex(vertex);
        std::vector<int> neighbors;

        // Handle outgoing edges if requested
        if (type == EdgeType::OUTGOING || type == EdgeType::BOTH) {
            for (int i = 0; i < numVertices; i++) {
                if (adjacencyMatrix[vertex][i] == 1) {
                    neighbors.push_back(i);
                }
            }
        }

        // Handle incoming edges if requested
        if (type == EdgeType::INCOMING || type == EdgeType::BOTH) {
            for (int i = 0; i < numVertices; i++) {
                // Add incoming edge if:
                // 1. It's not the same vertex
                // 2. Edge exists
                // 3. Either we don't want both directions OR it's not already counted
                if (i != vertex && adjacencyMatrix[i][vertex] == 1 &&
                    (type != EdgeType::BOTH || adjacencyMatrix[vertex][i] != 1)) {
                    neighbors.push_back(i);
                }
            }
        }

        return neighbors;
    }

    // Counts outgoing edges from a vertex
    int getOutDegree(int vertex) const {
        validateVertex(vertex);
        return std::count(adjacencyMatrix[vertex].begin(),
                         adjacencyMatrix[vertex].end(), 1);
    }

    // Counts incoming edges to a vertex
    int getInDegree(int vertex) const {
        validateVertex(vertex);
        return std::count_if(adjacencyMatrix.begin(), adjacencyMatrix.end(),
            [vertex](const auto& row) { return row[vertex] == 1; });
    }

    // Gets total degree based on graph type:
    // - For undirected: same as out-degree
    // - For directed: sum of in-degree and out-degree
    int getDegree(int vertex) const {
        return !isDirected ? getOutDegree(vertex)
                         : getInDegree(vertex) + getOutDegree(vertex);
    }

    // Checks if graph is connected:
    // - For undirected: simple DFS
    // - For directed: uses Kosaraju's algorithm for strong connectivity
    bool isConnected() const {
        std::vector<bool> visited(numVertices, false);

        if (!isDirected) {
            // For undirected graphs, single DFS is sufficient
            dfs(0, visited, adjacencyMatrix);
            return std::all_of(visited.begin(), visited.end(),
                             [](bool v) { return v; });
        }

        // Kosaraju's algorithm for directed graphs
        std::vector<int> order;
        dfs(0, visited, adjacencyMatrix, &order);  // First DFS

        // Early exit if not all vertices reachable from vertex 0
        if (!std::all_of(visited.begin(), visited.end(),
                        [](bool v) { return v; })) {
            return false;
        }

        // Reset visited array for second DFS
        std::fill(visited.begin(), visited.end(), false);
        auto transpose = getTranspose();
        dfs(order.back(), visited, transpose);  // Second DFS on transpose

        // Check if all vertices were visited in second DFS
        return std::all_of(visited.begin(), visited.end(),
                          [](bool v) { return v; });
    }

    // Checks if directed graph would be connected if we ignored edge directions
    bool isWeaklyConnected() const {
        if (!isDirected) {
            return isConnected();  // Same as regular connectivity for undirected
        }

        // Create undirected version and run simple DFS
        std::vector<bool> visited(numVertices, false);
        auto undirected = getUndirected();
        dfs(0, visited, undirected);

        // Check if all vertices were visited
        return std::all_of(visited.begin(), visited.end(),
                          [](bool v) { return v; });
    }
};

Understanding Advanced Graph Features

Our enhanced implementation adds several crucial features for analyzing graph structure:

  • Degree Calculations:
    • Out-degree: The number of edges leaving a vertex (in a directed graph, these are edges where the vertex is the source)
    • In-degree: The number of edges entering a vertex (in a directed graph, these are edges where the vertex is the destination)
    • Total degree: For undirected graphs, this is simply the number of connected edges. For directed graphs, it's the sum of in-degree and out-degree
  • Direction-Aware Features:
    • All methods properly handle both directed and undirected graphs
    • Flexible neighbor retrieval with options for incoming, outgoing, or both types of edges
    • Support for converting between directed and undirected representations
  • Connectivity Analysis:
    • Kosaraju's Algorithm: An efficient method for checking if a directed graph is strongly connected by:
      1. Performing a first DFS to order vertices
      2. Creating a transposed graph (reversing all edges)
      3. Performing a second DFS on the transpose
    • Weak Connectivity: Checks if a directed graph would be connected if we ignored edge directions
  • Efficient Implementation:
    • Uses STL algorithms for optimized counting operations
    • Single, flexible DFS implementation that handles all traversal needs
    • Consistent vertex validation across all operations

Let's see how to use these enhanced features with examples:

Examples Using Enhanced Features
int main() {
    std::cout << "Testing Undirected Graph:\n";
    std::cout << "------------------------\n";
    Graph g(4);  // Undirected graph

    // Create a simple undirected graph
    g.addEdge(0, 1);
    g.addEdge(0, 2);
    g.addEdge(1, 2);
    g.addEdge(1, 3);
    g.addEdge(2, 3);

    // Test various features
    std::cout << "Vertex 1 degree: " << g.getDegree(1) << "\n";

    auto neighbors = g.getNeighbors(1, Graph::EdgeType::BOTH);
    std::cout << "Vertex 1 neighbors: ";
    for (int neighbor : neighbors) {
        std::cout << neighbor << " ";
    }
    std::cout << "\n";

    std::cout << "\nTesting Directed Graph:\n";
    std::cout << "----------------------\n";
    Graph dg(4, true);  // Directed graph

    // Create a strongly connected directed graph
    dg.addEdge(0, 1);
    dg.addEdge(1, 2);
    dg.addEdge(2, 3);
    dg.addEdge(3, 0);  // Creates a cycle

    // Test directed graph features
    std::cout << "Vertex 1 in-degree: " << dg.getInDegree(1) << "\n";
    std::cout << "Vertex 1 out-degree: " << dg.getOutDegree(1) << "\n";

    auto inNeighbors = dg.getNeighbors(1, Graph::EdgeType::INCOMING);
    std::cout << "Vertex 1 incoming neighbors: ";
    for (int neighbor : inNeighbors) {
        std::cout << neighbor << " ";
    }
    std::cout << "\n";

    std::cout << "Is strongly connected: "
              << (dg.isConnected() ? "Yes" : "No") << "\n";
    std::cout << "Is weakly connected: "
              << (dg.isWeaklyConnected() ? "Yes" : "No") << "\n";

    return 0;
}
Testing Undirected Graph:
------------------------
Vertex 1 degree: 3
Vertex 1 neighbors: 0 2 3

Testing Directed Graph:
----------------------
Vertex 1 in-degree: 1
Vertex 1 out-degree: 1
Vertex 1 incoming neighbors: 0
Is strongly connected: Yes
Is weakly connected: Yes

Key Implementation Features

  • Efficient DFS Implementation: Single DFS method handles all graph traversal needs
  • Flexible Direction Handling: Support for incoming, outgoing, or both edge types
  • Advanced Connectivity Checking: Implements Kosaraju's algorithm for strong connectivity
  • STL Integration: Uses STL algorithms for efficient counting and checking

Implementation Tips:

  • Use a single DFS implementation to maintain consistency and reduce code duplication
  • Implement helper methods for graph transformations (transpose, undirected conversion)
  • Leverage STL algorithms for better performance and cleaner code
  • Use validation helpers to ensure consistent error checking
  • Consider memory usage with adjacency matrices for large graphs

Remember: While this implementation is efficient for small to medium-sized graphs, consider using adjacency lists for very large, sparse graphs.

This enhanced implementation provides a solid foundation for graph analysis. Consider extending it further with:

  • Cycle detection algorithms
  • Shortest path finding using Dijkstra's or Floyd-Warshall algorithms
  • Strongly connected component identification
  • Topological sorting for directed acyclic graphs (DAGs)

With these enhanced features, you can now perform sophisticated graph analysis. Consider extending the implementation further with:

  • Cycle detection algorithms
  • Shortest path finding (Dijkstra's or Floyd-Warshall)
  • Strongly connected component identification
  • Topological sorting for directed acyclic graphs

Weighted Graphs

So far, we've worked with simple graphs where edges either exist or don't exist. However, in many real-world scenarios, we need to attach values to these connections. Think of:

  • Road networks where edges represent distances between cities
  • Computer networks where edges represent bandwidth or latency
  • Social networks where edges might represent interaction strengths

These scenarios require weighted graphs, where each edge carries a numerical value. Let's modify our implementation to handle these more complex relationships.

Implementation

Our weighted graph implementation will differ from the basic graph in several important ways:

  • We'll use double instead of int to store edge weights
  • Instead of 0/1 for no edge/edge, we'll use infinity/weight
  • We'll need new methods to handle and analyze weights

Here's our enhanced implementation that supports weighted edges:

Weighted Graph Class
// Required standard libraries
#include <vector>     // For adjacency matrix storage
#include <iostream>   // For output operations
#include <limits>     // For infinity representation
#include <iomanip>    // For formatted output of weights

// WeightedGraph class implementing an adjacency matrix for weighted graphs
// Supports both directed and undirected weighted graphs where edges have
// associated weights (e.g., distances, costs, capacities)
class WeightedGraph {
private:
    std::vector<std::vector<double>> adjacencyMatrix;  // 2D vector storing edge weights
    int numVertices;                              // Total number of vertices
    bool isDirected;                             // Whether graph is directed
    const double INF = std::numeric_limits<double>::infinity();  // Represents no connection

public:
    // Constructor creates an empty weighted graph
    // Parameters:
    //   vertices: Number of vertices in the graph
    //   directed: Whether the graph is directed (default: false)
    // Notes:
    //   - Initializes matrix with infinity for no connections
    //   - Sets diagonal elements to 0 (distance from vertex to itself)
    WeightedGraph(int vertices, bool directed = false)
        : numVertices(vertices), isDirected(directed) {
        // Initialize all elements to infinity, indicating no connections
        adjacencyMatrix.resize(vertices,
            std::vector<double>(vertices, INF));

        // Set diagonal elements to 0 (vertex to itself)
        // This is a common convention in weighted graphs
        for (int i = 0; i < vertices; i++) {
            adjacencyMatrix[i][i] = 0;
        }
    }

    // Adds a weighted edge between two vertices
    // Parameters:
    //   from: Source vertex
    //   to: Destination vertex
    //   weight: Edge weight (e.g., distance, cost)
    // Throws:
    //   std::out_of_range if either vertex index is invalid
    void addEdge(int from, int to, double weight) {
        if (from >= numVertices || to >= numVertices ||
            from < 0 || to < 0) {
            throw std::out_of_range("Vertex index out of bounds");
        }

        adjacencyMatrix[from][to] = weight;
        if (!isDirected) {
            adjacencyMatrix[to][from] = weight;  // Mirror edge for undirected graphs
        }
    }

    // Gets the weight of an edge between two vertices
    // Parameters:
    //   from: Source vertex
    //   to: Destination vertex
    // Returns:
    //   Weight of the edge (or infinity if no edge exists)
    // Throws:
    //   std::out_of_range if either vertex index is invalid
    double getWeight(int from, int to) const {
        if (from >= numVertices || to >= numVertices ||
            from < 0 || to < 0) {
            throw std::out_of_range("Vertex index out of bounds");
        }
        return adjacencyMatrix[from][to];
    }

    // Checks if an edge exists between two vertices
    // Parameters:
    //   from: Source vertex
    //   to: Destination vertex
    // Returns:
    //   true if edge exists (weight != infinity), false otherwise
    bool hasEdge(int from, int to) const {
        if (from >= numVertices || to >= numVertices ||
            from < 0 || to < 0) {
            return false;
        }
        return adjacencyMatrix[from][to] != INF;
    }

    // Removes an edge between two vertices
    // Parameters:
    //   from: Source vertex
    //   to: Destination vertex
    // Throws:
    //   std::out_of_range if either vertex index is invalid
    void removeEdge(int from, int to) {
        if (from >= numVertices || to >= numVertices ||
            from < 0 || to < 0) {
            throw std::out_of_range("Vertex index out of bounds");
        }

        adjacencyMatrix[from][to] = INF;
        if (!isDirected) {
            adjacencyMatrix[to][from] = INF;  // Mirror removal for undirected graphs
        }
    }

    // Calculates total weight of all edges connected to a vertex
    // Parameters:
    //   vertex: The vertex to calculate total weight for
    // Returns:
    //   Sum of weights of all non-infinite edges connected to vertex
    // Notes:
    //   - Excludes self-loops (diagonal elements)
    //   - Only counts finite weights
    double getTotalWeight(int vertex) const {
        if (vertex >= numVertices || vertex < 0) {
            throw std::out_of_range("Vertex index out of bounds");
        }

        double total = 0;
        for (int i = 0; i < numVertices; i++) {
            // Add weight if edge exists and isn't a self-loop
            if (adjacencyMatrix[vertex][i] != INF &&
                vertex != i) {
                total += adjacencyMatrix[vertex][i];
            }
        }
        return total;
    }

    // Prints the weighted adjacency matrix
    // Output format:
    //   - Infinite weights shown as '∞'
    //   - Finite weights shown with 1 decimal place
    //   - Elements separated by spaces
    void print() const {
        for (int i = 0; i < numVertices; i++) {
            for (int j = 0; j < numVertices; j++) {
                if (adjacencyMatrix[i][j] == INF) {
                    std::cout << "∞ ";  // Unicode infinity symbol
                } else {
                    // Format weights with fixed precision (1 decimal place)
                    std::cout << std::fixed << std::setprecision(1)
                             << adjacencyMatrix[i][j] << " ";
                }
            }
            std::cout << "\n";
        }
    }
};

Let's examine the key differences from our unweighted implementation:

  • The matrix now stores double values instead of binary 0/1
  • We use infinity (∞) to represent missing edges instead of 0
  • The diagonal is initialized to 0, representing the "distance" from a vertex to itself
  • We've added methods specifically for working with weights

Usage Example

To demonstrate how weighted graphs work in practice, let's create a small network with various edge weights. This example will show how to:

  • Create a weighted graph
  • Add edges with different weights
  • Query and analyze the weight information
Weighted Graph Example
int main() {
    // Create a weighted graph with 4 vertices
    WeightedGraph g(4);

    // Add weighted edges
    g.addEdge(0, 1, 2.5);  // Edge from 0 to 1 with weight 2.5
    g.addEdge(0, 2, 1.0);  // Edge from 0 to 2 with weight 1.0
    g.addEdge(1, 2, 3.5);  // Edge from 1 to 2 with weight 3.5
    g.addEdge(1, 3, 4.0);  // Edge from 1 to 3 with weight 4.0
    g.addEdge(2, 3, 2.0);  // Edge from 2 to 3 with weight 2.0

    std::cout << "Weighted Adjacency Matrix:\n";
    g.print();

    // Get weight of edge between vertices 1 and 3
    std::cout << "\nWeight of edge (1,3): "
              << g.getWeight(1, 3) << "\n";

    // Get total weight of edges connected to vertex 1
    std::cout << "Total weight of edges at vertex 1: "
              << g.getTotalWeight(1) << "\n";

    return 0;
}

When we run this code, we get:

Weighted Adjacency Matrix:
0.0 2.5 1.0 ∞
2.5 0.0 3.5 4.0
1.0 3.5 0.0 2.0
∞ 4.0 2.0 0.0

Weight of edge (1,3): 4.0
Total weight of edges at vertex 1: 10.0

Key Features of Weighted Graphs

Our weighted graph implementation provides several important capabilities:

  • Infinity Values: Uses ∞ to clearly indicate absence of connections between vertices
  • Zero Diagonal: The diagonal elements are set to 0, representing the distance from a vertex to itself
  • Double Precision: Weights are stored as double values to handle decimal weights accurately
  • Total Weight: Added functionality to calculate the sum of weights for edges connected to a vertex

Implementation Tips:

  • Use std::numeric_limits<double>::infinity() for representing no connection - it's more semantically correct than a magic number
  • Consider using a custom Weight type if you need to represent more complex weight attributes (like cost and distance together)
  • Be careful with floating-point comparisons when checking for infinity - use appropriate epsilon values if needed
  • Use appropriate precision when printing weights to maintain readability while showing meaningful decimal places

This weighted graph implementation serves as a foundation for more advanced algorithms like Dijkstra's shortest path or Prim's minimum spanning tree algorithm. These algorithms specifically work with weighted graphs to solve real-world optimization problems.

Advanced Topics and Optimizations

While our implementation provides a solid foundation for working with adjacency matrices, there are several advanced considerations for real-world applications:

Memory Optimization

  • Sparse Matrix Representations: For graphs where most vertices aren't connected (sparse graphs), consider using compressed storage formats like CSR (Compressed Sparse Row) or COO (Coordinate format)
  • Bit Matrices: For unweighted graphs, use bit vectors to reduce memory usage by a factor of 8
  • Dynamic Sizing: Implement efficient strategies for growing and shrinking the matrix as vertices are added or removed

Performance Enhancements

  • Cache Optimization: Organize matrix data to maximize cache hits during common traversal patterns
  • Parallelization: Implement parallel algorithms for operations on large graphs
  • SIMD Operations: Use vectorized instructions for batch operations on adjacency matrices

Extended Functionality

  • Multi-edge Support: Modify the matrix to handle multiple edges between the same vertices
  • Edge Properties: Extend the implementation to store additional edge attributes beyond weights
  • Versioning: Implement efficient ways to track graph changes over time

Further Exploration: Each of these topics deserves its own deep dive, particularly for specific use cases like social networks, transportation systems, or computer networks.

Conclusion

Adjacency matrices provide a powerful and intuitive way to represent graphs in C++. We've covered the essential concepts and implementations, from basic unweighted graphs to weighted variations. While this representation excels in dense graphs and offers constant-time edge queries, it's important to consider your specific use case when choosing between adjacency matrices and other graph representations like adjacency lists.

Key takeaways from this guide:

  • Adjacency matrices offer O(1) edge lookups but require O(V²) space
  • They're particularly effective for dense graphs and weighted edges
  • The implementation can be extended to support various graph types and operations
  • Consider optimization techniques for large-scale applications

The implementations we've covered form a solid foundation for working with graphs in C++. You can build upon these examples to create more specialized graph structures for your specific needs, whether you're working on:

  • Social network analysis
  • Route planning systems
  • Network optimization
  • Game development pathfinding

Congratulations on reading to the end of this comprehensive guide! If you found this guide valuable for your C++ journey, please consider citing or sharing it with fellow developers. Your support helps us continue creating comprehensive C++ resources for the development community.

Be sure to explore the Further Reading section for additional resources on graph theory, adjacency matrices, and modern C++ practices.

Have fun and happy coding!

Further Reading

Graph Implementation Guides

Development Tools and Libraries

  • Eigen: Sparse Matrix Guide

    Learn how to use Eigen's sparse matrix capabilities for efficient graph operations in large-scale applications.

  • Boost Graph Library Documentation

    Explore advanced graph algorithms and data structures in C++, including specialized implementations for sparse graphs.

  • Online C++ Compiler

    Write, compile, and run your C++ code directly in your browser. Perfect for experimenting with graph algorithms and testing code snippets without setting up a local development environment.

Performance and Optimization

  • Cache-Efficient Graph Algorithms

    Techniques for optimizing graph algorithms for modern hardware, focusing on memory layout and access patterns in sparse data structures.

  • Parallel Graph Algorithms

    Research paper on parallel implementations of graph algorithms, with special attention to sparse graph representations.

  • DirectXMath Library

    Explore efficient mathematical operations that can be applied to graph algorithms in performance-critical applications.

Attribution and Citation

If you found this guide and tools helpful, feel free to link back to this page or cite it in your work!

Profile Picture
Senior Advisor, Data Science | [email protected] |  + posts

Suf is a senior advisor in data science with deep expertise in Natural Language Processing, Complex Networks, and Anomaly Detection. Formerly a postdoctoral research fellow, he applied advanced physics techniques to tackle real-world, data-heavy industry challenges. Before that, he was a particle physicist at the ATLAS Experiment of the Large Hadron Collider. Now, he’s focused on bringing more fun and curiosity to the world of science and research online.

Buy Me a Coffee ✨

© 2024 The Research Scientist Pod. All rights reserved.