Adjacency Matrix and Adjacency List Implementations

Adjacency Matrix and Adjacency List Implementations

Graphs can be represented in two common ways: adjacency matrices and adjacency lists. Each representation has its own advantages and disadvantages, depending on the nature of the graph and the operations being performed.

1. Adjacency Matrix

An adjacency matrix is a 2D array (or matrix) used to represent a graph. For a graph with $n$ vertices, it is an $n \times n$ matrix where each cell $(i, j)$ indicates whether there is an edge from vertex $i$ to vertex $j$.

• Matrix Cell Values:
  • 1 (or true) indicates the presence of an edge.
  • 0 (or false) indicates no edge.

Properties:

• Space Complexity: $O(V^2)$, where $V$ is the number of vertices.
• Fast edge lookup: $O(1)$ to check if an edge exists between two vertices.
• Inefficient for sparse graphs (graphs with relatively few edges compared to vertices).

Example Implementation:

#include <iostream>
#include <vector>
using namespace std;

class Graph {
private:
    vector<vector<int>> adjMatrix;
    int numVertices;

public:
    Graph(int vertices) : numVertices(vertices) {
        adjMatrix.resize(vertices, vector<int>(vertices, 0)); // Initialize to 0
    }

    void addEdge(int u, int v) {
        adjMatrix[u][v] = 1; // Directed graph
        // adjMatrix[v][u] = 1; // Uncomment for undirected graph
    }

    void printGraph() {
        for (int i = 0; i < numVertices; i++) {
            for (int j = 0; j < numVertices; j++) {
                cout << adjMatrix[i][j] << " ";
            }
            cout << endl;
        }
    }
};

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

    g.printGraph();
    return 0;
}

2. Adjacency List

An adjacency list is a more space-efficient way to represent a graph. It uses an array (or vector) of lists (or vectors), where each index represents a vertex and contains a list of all adjacent vertices (i.e., those with which it shares an edge).

Properties:

• Space Complexity: $O(V + E)$, where $E$ is the number of edges. This makes it suitable for sparse graphs.
• Iterating through all edges takes $O(E)$ time, which can be more efficient than using an adjacency matrix.

Example Implementation:

#include <iostream>
#include <vector>
#include <list>
using namespace std;

class Graph {
private:
    vector<list<int>> adjList;
    int numVertices;

public:
    Graph(int vertices) : numVertices(vertices) {
        adjList.resize(vertices);
    }

    void addEdge(int u, int v) {
        adjList[u].push_back(v); // Directed graph
        // adjList[v].push_back(u); // Uncomment for undirected graph
    }

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

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

    g.printGraph();
    return 0;
}

Summary

Both adjacency matrices and adjacency lists are effective ways to represent graphs, but they serve different needs:

• Adjacency Matrix:

  • Use when you need fast edge lookup and the graph is dense (many edges).
  • More straightforward for certain algorithms (e.g., Floyd-Warshall).

• Adjacency List:

  • Use for sparse graphs to save space and time when iterating through edges.
  • Often more flexible and easier to manipulate.

Choosing the right representation depends on the specific use case and the characteristics of the graph being modeled.