Graph Representation Quiz
Short drills on adjacency list vs adjacency matrix, edge-weight storage, and the memory trade-offs between the two formats.
Question Bank
Easy
JavaScript
3 questions
graph-representation
graphs
quiz
fundamentals
189 views
3
What is the space complexity of an adjacency list versus an adjacency matrix for a graph with V vertices and E edges? State both and say when each one wins.
Fill in addEdge so the adjacency list stores an undirected, unweighted graph. Edges must appear in both endpoint lists.
Examples
Example 1:
Input: new Graph(3); addEdge(0, 1); addEdge(1, 2)
Output: adj = [[1], [0, 2], [1]]
Explanation: An undirected edge {u, v} is two directed edges. Both endpoints must learn about the other, so push twice. Skipping the second push would silently make the graph directed.class Graph {
constructor(n) {
this.adj = Array.from({ length: n }, () => []);
}
addEdge(u, v) {
// TODO
}
}Convert the edge list below into an adjacency matrix for a directed graph with 4 vertices labeled 0..3. Show the matrix.
Examples
Example 1:
Input: edges = [[0, 1], [0, 2], [1, 2], [2, 3], [3, 1]], n = 4 (directed)
Output: [[0, 1, 1, 0], [0, 0, 1, 0], [0, 0, 0, 1], [0, 1, 0, 0]]
Explanation: Each pair [u, v] sets M[u][v] = 1 only (directed, no mirror). Row index is the source; column index is the destination. The diagonal stays 0 because the edge list has no self-loops.const edges = [[0, 1], [0, 2], [1, 2], [2, 3], [3, 1]];