ELEVATE SKILLS!
Which of the following is true for adjacency matrix representation of a graph with n vertices?
Space complexity is O(n)
Can not be used for directed graph
Space complexity is O(n2)
Can not be used for weighted graphs
[ Option C ]
In an adjacency matrix, we represent a graph using a two-dimensional array of size n×n, where n is the number of vertices. Each row and column correspond to a vertex, and the value stored in a cell tells us whether an edge exists between two vertices.
If the graph is weighted, the cell stores the weight instead of just 0 or 1. Since the matrix always needs space for n2 entries, the space complexity is O(n2). This representation can be used for directed or undirected graphs as well as weighted or unweighted graphs.
The only drawback is that it uses more memory for sparse graphs, but it provides quick access to check if an edge exists between two vertices.
Thank you so much for taking the time to read my Computer Science MCQs section carefully. Your support and interest mean a lot, and I truly appreciate you being part of this journey. Stay connected for more insights and updates! If you'd like to explore more tutorials and insights, check out my YouTube channel.
Don’t forget to subscribe and stay connected for future updates.
| Student Name | |
|---|---|
| College |
| What's Say |
|---|