03 - Adjacency Matrix Representation of Graph in C++ | Data Structures | Graph Theory

Summary

This video explains how to represent a graph using an adjacency matrix. It demonstrates how to create a 5x5 matrix for a graph with 5 vertices (0 to 4) and bi-directional edges, outlining the process of adding and removing edges. The script also covers the time and space complexities associated with adjacency matrix representations (O(n^2) space complexity and O(1) time complexity for adding/removing edges). Finally, the video emphasizes how to handle the adjacency matrix and illustrates with practical code examples in C++. The next video will explore graph representation using adjacency lists.

Takeaways

• 😀 **Graph Representation**: A graph can be represented using an adjacency list or an adjacency matrix, with each method having its pros and cons.
• 😀 **Adjacency Matrix Basics**: An adjacency matrix is a square matrix used to represent a graph where each element indicates if an edge exists between two vertices.
• 😀 **Bi-Directional Edges**: In the graph discussed, edges are bi-directional, meaning if an edge exists between vertex i and vertex j, it also exists from vertex j to vertex i.
• 😀 **Matrix Initialization**: To represent the graph as an adjacency matrix, start by initializing a matrix of size `n x n` (where `n` is the number of vertices) and set all values to zero.
• 😀 **Adding Edges**: Once the matrix is initialized, edges are added by setting the appropriate matrix elements to `1` for each pair of connected vertices.
• 😀 **Graph Example**: The graph in the example has 5 vertices (0, 1, 2, 3, 4) with edges between 0-1, 1-4, 1-3, and 2-3, making it a bi-directional graph.
• 😀 **Time Complexity for Edge Operations**: Adding or removing an edge in the adjacency matrix has a time complexity of O(1) as it only requires updating a matrix element.
• 😀 **Space Complexity of Adjacency Matrix**: The space complexity of an adjacency matrix is O(n^2), where `n` is the number of vertices, due to the need for a 2D array.
• 😀 **Printing the Matrix**: The adjacency matrix can be printed row by row, where each value represents the presence (1) or absence (0) of an edge between corresponding vertices.
• 😀 **Edge Removal**: Removing an edge in an adjacency matrix involves setting the corresponding matrix positions to `0` for the bi-directional connection, and this operation also takes O(1) time.

Q & A

What are the two main methods for representing a graph?

The two main methods for representing a graph are the adjacency list and the adjacency matrix.

What is the difference between an adjacency list and an adjacency matrix?

An adjacency list represents the graph using a list of nodes, where each node points to a list of its adjacent nodes, while an adjacency matrix uses a 2D array to indicate the presence or absence of edges between nodes.

How are the vertices of the graph represented in the example?

In the example, the graph has five vertices labeled 0, 1, 2, 3, and 4.

What does a value of 1 in an adjacency matrix indicate?

A value of 1 in an adjacency matrix indicates that there is an edge between the corresponding vertices.

How do you handle bi-directional edges in an adjacency matrix?

For bi-directional edges, both the (i, j) and (j, i) positions in the adjacency matrix are set to 1 to indicate that the edge can be traversed in both directions.

What is the time complexity for adding an edge to an adjacency matrix?

The time complexity for adding an edge in an adjacency matrix is O(1), as it simply involves setting the corresponding matrix element to 1.

What is the space complexity for storing a graph in an adjacency matrix?

The space complexity for an adjacency matrix is O(n^2), where n is the number of vertices, because the matrix is an n x n array.

What happens when an edge is removed from the graph in the adjacency matrix?

When an edge is removed, the corresponding elements in the adjacency matrix are set to 0, both for the edge itself and its reverse (if bi-directional).

How is an edge between a node and itself handled in the adjacency matrix?

An edge between a node and itself (self-loop) is represented by setting the diagonal elements of the matrix (graph[i][i]) to 1.

What is the time complexity of removing an edge from an adjacency matrix?

The time complexity of removing an edge from an adjacency matrix is O(1), as it involves simply setting the relevant matrix positions to 0.