Lecture 368:- Representation of Undirected Graph

There are several ways to represent an undirected graph in computer memory, each with its own advantages and disadvantages depending on the operations that need to be performed on the graph. The three most common representations are:

1. Adjacency Matrix: An adjacency matrix is a 2D array of size V x V, where V is the number of vertices in the graph. The entry at position (i, j) in the matrix represents whether there is an edge between vertex i and vertex j. If there is an edge, the value at (i, j) will be 1 (or the weight of the edge, if the graph is weighted). If there is no edge, the value will be 0. For an undirected graph, the matrix is symmetric (i.e., adj[i][j] = adj[j][i] for all i and j).

Advantages:

• Checking if there is an edge between two vertices takes O(1) time.
• Space-efficient for dense graphs (with many edges).

Disadvantages:

• Consumes O(V^2) space even for sparse graphs (with fewer edges).
• Adding or removing vertices is expensive, as it requires resizing the matrix.

1. Adjacency List: An adjacency list is an array of linked lists (or vectors) where each element of the array represents a vertex, and the linked list (or vector) contains the vertices that are adjacent to it (i.e., connected by an edge). In the case of weighted graphs, each element of the linked list can store a pair of the adjacent vertex and the weight of the edge.

Advantages:

• Space-efficient for sparse graphs, as it only stores information about existing edges.
• Adding or removing vertices and edges is relatively easy and efficient.

Disadvantages:

• Checking if there is an edge between two vertices may take O(V) time in the worst case.
• Less space-efficient for dense graphs compared to the adjacency matrix.

1. Edge List: An edge list is simply a list of all the edges in the graph. Each edge is represented as a pair (u, v), where u and v are the two vertices connected by the edge. If the graph is weighted, the pair can also contain the weight of the edge.

Advantages:

• Compact representation for both sparse and dense graphs.
• Easy to iterate over all the edges in the graph.

Disadvantages:

• Checking if there is an edge between two vertices may require iterating through the entire edge list in the worst case, resulting in O(E) time complexity (E being the number of edges).
• Not suitable for certain graph algorithms that require fast access to neighbors of a vertex.

The choice of representation depends on the specific use case, the size and density of the graph, and the operations that need to be performed on the graph. Each representation has its trade-offs in terms of space complexity and time complexity for various operations.