Graph Representations

Graph Representations

A graph is a collection of nodes (or vertices) connected by edges. Graphs can represent many real-world structures, such as networks, social connections, and pathways. Understanding how to represent graphs in a computer program is essential for implementing algorithms that work with them. There are two primary ways to represent graphs: adjacency matrices and adjacency lists.

Adjacency Matrix

An adjacency matrix is a two-dimensional array used to represent a graph. If there are n vertices in the graph, the adjacency matrix will be an n x n matrix. Each cell in the matrix indicates whether a pair of vertices is connected by an edge. The value can be 1 (connected) or 0 (not connected).

For example, consider a graph with four vertices: A, B, C, and D. If the edges are A-B, A-C, and B-D, the adjacency matrix would look like this:

    A B C D
A [ 0 1 1 0 ]
B [ 1 0 0 1 ]
C [ 1 0 0 0 ]
D [ 0 1 0 0 ]

In this matrix:

• The cell (A, B) is 1 because there is an edge between A and B.
• The cell (A, C) is 1 because there is an edge between A and C.
• The cell (B, D) is 1 because there is an edge between B and D.
• All other cells are 0, indicating no edge exists.

Adjacency List

An adjacency list is another way to represent a graph. Instead of using a matrix, an adjacency list uses an array of lists. Each index of the array represents a vertex, and each list at that index contains the vertices connected to it.

Using the same example graph with vertices A, B, C, and D, the adjacency list would look like this:

A: [B, C]
B: [A, D]
C: [A]
D: [B]

In this representation:

• For vertex A, the list contains B and C, indicating that A is connected to both B and C.
• For vertex B, the list contains A and D, indicating that B is connected to A and D.
• For vertex C, the list only contains A, indicating that C is connected to A.
• For vertex D, the list only contains B, indicating that D is connected to B.

Choosing Between Representations

• Density of the Graph: If the graph is dense (many edges), an adjacency matrix may be more efficient. If it is sparse (few edges), an adjacency list is usually better.
• Memory Usage: An adjacency matrix requires O(n^2) space, while an adjacency list requires O(n + m) space, where m is the number of edges.
• Access Speed: An adjacency matrix allows for quicker checks of whether an edge exists between two vertices (O(1) time). An adjacency list needs O(n) time in the worst case to check for an edge.

Example Implementation

Let’s implement both representations in C++. We will create a simple graph class that allows adding edges and displaying the graph.

#include 
#include 
#include 
using namespace std;

class GraphMatrix {
private:
    vector> adjMatrix;
    int numVertices;
public:
    GraphMatrix(int vertices) {
        numVertices = vertices;
        adjMatrix.resize(vertices, vector(vertices, 0));
    }

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

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

class GraphList {
private:
    vector> adjList;
    int numVertices;
public:
    GraphList(int vertices) {
        numVertices = vertices;
        adjList.resize(vertices);
    }

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

    void display() {
        for (int i = 0; i < numVertices; i++) {
            cout << i << ": ";
            for (auto v : adjList[i]) {
                cout << v << " ";
            }
            cout << endl;
        }
    }
};

int main() {
    GraphMatrix g1(4);
    g1.addEdge(0, 1);
    g1.addEdge(0, 2);
    g1.addEdge(1, 3);
    g1.display();

    GraphList g2(4);
    g2.addEdge(0, 1);
    g2.addEdge(0, 2);
    g2.addEdge(1, 3);
    g2.display();

    return 0;
}

This code defines two classes: GraphMatrix and GraphList. Each class has methods to add edges and display the graph. The main function creates instances of both classes, adds edges, and displays the graph.

Conclusion

Graph representations are crucial for implementing graph algorithms. Understanding the differences between adjacency matrices and adjacency lists will help you choose the right representation for your needs. Remember to consider the graph's density, memory usage, and access speed when making your choice.

Check your understanding

• What is an adjacency matrix and how is it structured?
• When would you prefer to use an adjacency list over an adjacency matrix?
• What is the time complexity of checking for the existence of an edge in both representations?
• Provide an example of a graph and create its adjacency list representation.