Graph Representation

Graph Representation

In computer science, graphs are used to represent relationships between objects. Graph representation is the method of storing a graph in a data structure so that it can be efficiently manipulated and accessed. There are two primary ways to represent graphs: adjacency lists and adjacency matrices.

Adjacency List

An adjacency list is a collection of lists or arrays. Each list corresponds to a vertex in the graph and contains a list of its adjacent vertices. This representation is efficient in terms of space when the graph is sparse, meaning it has relatively few edges compared to the number of vertices.

Example of an Adjacency List

Consider a simple undirected graph with the following vertices and edges:

• Vertices: A, B, C, D
• Edges: AB, AC, BD, CD

The adjacency list for this graph would look like this:

A: B, C
B: A, D
C: A, D
D: B, C

In this example, vertex A is connected to vertices B and C, while vertex B is connected back to A and to D, and so on.

Adjacency Matrix

An adjacency matrix is a two-dimensional array used to represent a graph. The rows and columns of the matrix correspond to the vertices of the graph. If there is an edge between two vertices, the corresponding cell in the matrix is marked with a 1 (or the weight of the edge if the graph is weighted); otherwise, it is marked with a 0.

Example of an Adjacency Matrix

Using the same graph as before, the adjacency matrix would be:

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

In this matrix, the rows represent the source vertices and the columns represent the destination vertices. For instance, the cell at row A and column B is 1, indicating that there is an edge between A and B.

Comparison of Representations

Both adjacency lists and adjacency matrices have their advantages and disadvantages:

• Space Complexity: An adjacency list uses O(V + E) space, where V is the number of vertices and E is the number of edges. An adjacency matrix uses O(V^2) space, which can be wasteful for sparse graphs.
• Time Complexity: Checking for the existence of an edge in an adjacency matrix is O(1), while in an adjacency list it is O(V) in the worst case. However, iterating over all edges is faster in an adjacency list, which is O(E).

Graph Representation in Programming

When implementing graph representations in a programming language like C++, you can use classes or structures to define the graph. Below is an example of how to implement an adjacency list in C++:

#include 
#include 
#include 
using namespace std;

class Graph {
    int V; // Number of vertices
    vector> adj; // Adjacency list

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

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

void Graph::addEdge(int v, int w) {
    adj[v].push_back(w); // Add w to v's list
    adj[w].push_back(v); // Add v to w's list (for undirected graph)
}

void Graph::printGraph() {
    for (int v = 0; v < V; v++) {
        cout << "Vertex " << v << " : ";
        for (int w : adj[v]) {
            cout << w << " ";
        }
        cout << endl;
    }
}

int main() {
    Graph g(4); // Create a graph with 4 vertices
    g.addEdge(0, 1);
    g.addEdge(0, 2);
    g.addEdge(1, 3);
    g.addEdge(2, 3);

    g.printGraph();
    return 0;
}

In this code, a graph class is created with methods to add edges and print the graph. The adjacency list is represented using a vector of lists.

Weighted Graphs

In some applications, edges have weights. A weighted graph can be represented using both adjacency lists and matrices. For an adjacency list, you would store pairs of vertices and their weights. For an adjacency matrix, you would replace 1s with the actual weights of the edges. If no edge exists, you can use a special value like 0 or infinity.

Example of a Weighted Adjacency List

Consider a weighted graph with the following edges and weights:

• AB (weight 2), AC (weight 3), BD (weight 1), CD (weight 4)

The weighted adjacency list would look like this:

A: (B, 2), (C, 3)
B: (A, 2), (D, 1)
C: (A, 3), (D, 4)
D: (B, 1), (C, 4)

Example of a Weighted Adjacency Matrix

The corresponding weighted adjacency matrix would be:

    A B C D
A [ 0 2 3 0 ]
B [ 2 0 0 1 ]
C [ 3 0 0 4 ]
D [ 0 1 4 0 ]

Conclusion

Graph representation is a crucial concept in computer science. Understanding how to represent graphs using adjacency lists and matrices helps you choose the right structure for your specific needs. Each representation has its own strengths, and the choice depends on the specific characteristics of the graph you are working with.

Check your understanding

1. What is the space complexity of an adjacency list?
2. How would you represent a weighted graph using an adjacency matrix?
3. What are the advantages of using an adjacency list over an adjacency matrix?
4. Provide an example of an undirected graph and show its adjacency list representation.