Introductions
Graph representation means storing the vertices and edges of a graph inside a program. The common graph representation methods include Adjacency List, Adjacency Matrix, and Edge List. In this chapter, we will practice graph representation through practical solved questions. Each question is designed to test a different concept, helping you learn how to efficiently represent and modify graphs. Data Structure Graph Representation practice questions with solutions help to build concepts.
Question 1: Create an Edge List for a Graph
Question
Given the following undirected graph edges:
A-B
A-C
B-D
C-D
Create an Edge List using JavaScript.
Solution
An Edge List stores every edge as a pair of vertices.
const edges = [
["A", "B"],
["A", "C"],
["B", "D"],
["C", "D"]
];
console.log(edges);
Output
[
[ 'A', 'B' ],
[ 'A', 'C' ],
[ 'B', 'D' ],
[ 'C', 'D' ]
]
Answer
The graph is represented using an array where each inner array contains the two vertices connected by an edge.
Question 2: Convert Edge List into an Adjacency List
Question
Convert the following Edge List into an Adjacency List:
[
["A", "B"],
["A", "C"],
["B", "D"]
]
Solution
const edges = [
["A", "B"],
["A", "C"],
["B", "D"]
];
const graph = {};
for (const [u, v] of edges) {
if (!graph[u]) graph[u] = [];
if (!graph[v]) graph[v] = [];
graph[u].push(v);
graph[v].push(u);
}
console.log(graph);
Output
{
A: [ 'B', 'C' ],
B: [ 'A', 'D' ],
C: [ 'A' ],
D: [ 'B' ]
}
Answer
Each vertex stores an array containing its directly connected vertices.
Question 3: Build an Adjacency Matrix from an Edge List
Question
Represent this undirected graph using an Adjacency Matrix:
Vertices: A, B, C, D
Edges:
A-B
A-D
B-C
Solution
First assign indexes:
A → 0
B → 1
C → 2
D → 3
Then create a 4 × 4 matrix.
const vertices = ["A", "B", "C", "D"];
const edges = [
["A", "B"],
["A", "D"],
["B", "C"]
];
const matrix = Array.from(
{ length: vertices.length },
() => Array(vertices.length).fill(0)
);
for (const [u, v] of edges) {
const i = vertices.indexOf(u);
const j = vertices.indexOf(v);
matrix[i][j] = 1;
matrix[j][i] = 1;
}
console.log(matrix);
Output
[
[0, 1, 0, 1],
[1, 0, 1, 0],
[0, 1, 0, 0],
[1, 0, 0, 0]
]
Answer
Because the graph is undirected, both [i][j] and [j][i] are set to 1.
Question 4: Add a New Edge to an Adjacency List
Question
You have the following graph:
const graph = {
A: ["B"],
B: ["A", "C"],
C: ["B"]
};
Add a new undirected edge between A and C.
Solution
const graph = {
A: ["B"],
B: ["A", "C"],
C: ["B"]
};
graph.A.push("C");
graph.C.push("A");
console.log(graph);
Output
{
A: [ 'B', 'C' ],
B: [ 'A', 'C' ],
C: [ 'B', 'A' ]
}
Answer
For an undirected graph, adding A-C requires updating both vertices.
Question 5: Remove an Edge from an Adjacency Matrix
Question
Consider this adjacency matrix:
[
[0, 1, 1],
[1, 0, 1],
[1, 1, 0]
]
Remove the edge between vertex A and vertex C.
Solution
Assume:
A → 0
B → 1
C → 2
For an undirected graph, remove the connection from both positions.
const matrix = [
[0, 1, 1],
[1, 0, 1],
[1, 1, 0]
];
matrix[0][2] = 0;
matrix[2][0] = 0;
console.log(matrix);
Output
[
[0, 1, 0],
[1, 0, 1],
[0, 1, 0]
]
Answer
The A-C connection is removed by changing both corresponding matrix cells from 1 to 0.
Question 6: Represent a Weighted Graph Using an Adjacency List
Question
Represent the following weighted graph using an Adjacency List:
A → B (5)
A → C (2)
B → C (4)
Solution
Instead of storing only the connected vertex, store both the vertex and its weight.
const graph = {
A: [
{ node: "B", weight: 5 },
{ node: "C", weight: 2 }
],
B: [
{ node: "C", weight: 4 }
],
C: []
};
console.log(graph);
Output
{
A: [
{ node: 'B', weight: 5 },
{ node: 'C', weight: 2 }
],
B: [
{ node: 'C', weight: 4 }
],
C: []
}
Answer
A weighted graph needs additional information for every edge, such as { node, weight }.
Question 7: Represent a Directed Graph Without Adding Reverse Edges
Question
Create an Adjacency List for this directed graph:
A → B
B → C
C → A
Make sure reverse edges are NOT added.
Solution
const graph = {
A: ["B"],
B: ["C"],
C: ["A"]
};
console.log(graph);
Output
{
A: [ 'B' ],
B: [ 'C' ],
C: [ 'A' ]
}
Answer
In a directed graph, A → B does not automatically mean B → A. Therefore, only the specified direction is stored.
Question 8: Convert an Adjacency Matrix into an Adjacency List
Question
Convert this matrix into an Adjacency List:
[
[0, 1, 1],
[1, 0, 0],
[1, 0, 0]
]
Vertices are:
A, B, C
Solution
const vertices = ["A", "B", "C"];
const matrix = [
[0, 1, 1],
[1, 0, 0],
[1, 0, 0]
];
const graph = {};
for (let i = 0; i < vertices.length; i++) {
graph[vertices[i]] = [];
for (let j = 0; j < vertices.length; j++) {
if (matrix[i][j] === 1) {
graph[vertices[i]].push(vertices[j]);
}
}
}
console.log(graph);
Output
{
A: [ 'B', 'C' ],
B: [ 'A' ],
C: [ 'A' ]
}
Answer
Every 1 in a matrix represents a connection, which is converted into a neighboring vertex in the Adjacency List.
Question 9: Store Graph Edges Using an Edge List and Count Them
Question
Create an Edge List for the following graph and find the total number of stored edges:
P-Q
P-R
Q-S
R-S
S-T
Solution
const edges = [
["P", "Q"],
["P", "R"],
["Q", "S"],
["R", "S"],
["S", "T"]
];
console.log("Edges:", edges);
console.log("Total edges:", edges.length);
Output
Edges: [
[ 'P', 'Q' ],
[ 'P', 'R' ],
[ 'Q', 'S' ],
[ 'R', 'S' ],
[ 'S', 'T' ]
]
Total edges: 5
Answer
The Edge List contains 5 edge pairs, so the graph has 5 stored edges.
Question 10: Create a Reusable Graph Representation Class
Question
Create a JavaScript Graph class that allows you to:
- Add vertices
- Add undirected edges
- Display the graph
Solution
class Graph {
constructor() {
this.graph = {};
}
addVertex(vertex) {
if (!this.graph[vertex]) {
this.graph[vertex] = [];
}
}
addEdge(vertex1, vertex2) {
this.addVertex(vertex1);
this.addVertex(vertex2);
this.graph[vertex1].push(vertex2);
this.graph[vertex2].push(vertex1);
}
display() {
console.log(this.graph);
}
}
const g = new Graph();
g.addVertex("A");
g.addVertex("B");
g.addVertex("C");
g.addEdge("A", "B");
g.addEdge("A", "C");
g.display();
Output
{
A: [ 'B', 'C' ],
B: [ 'A' ],
C: [ 'A' ]
}
Answer
The class provides a reusable way to create and maintain an undirected graph using an Adjacency List.
Key Takeaways
- An Edge List stores graph connections as pairs of vertices.
- An Adjacency List stores neighbors for each vertex.
- An Adjacency Matrix uses a 2D array to represent connections.
- Weighted graphs need additional weight information.
- Undirected edges are generally stored in both directions.
- Directed edges maintain their specified direction.
- An Adjacency Matrix can be converted into an Adjacency List.
- An Edge List can be converted into other graph representations.
- Graph representations can be implemented using JavaScript objects and classes.
- Choosing the right representation depends on how the graph will be used.
FAQs
1. What is graph representation?
Graph representation is a method of storing vertices and edges of a graph in a data structure so that a program can work with them.
2. What are the main graph representation methods?
The commonly used methods are Adjacency List, Adjacency Matrix, and Edge List.
3. What is an Edge List?
An Edge List stores every graph edge as a pair of connected vertices, such as ["A", "B"].
4. Why is an Adjacency List useful?
An Adjacency List stores only the connections that actually exist, making it useful for graphs with relatively few edges.
5. What does 1 mean in an Adjacency Matrix?
Usually, 1 means that a connection exists between two vertices, while 0 means there is no connection.
6. How are weighted graphs represented?
A weighted graph can store the neighboring vertex together with its weight, for example { node: "B", weight: 5 }.
7. Which graph representation should beginners learn first?
Beginners should understand Edge List, Adjacency List, and Adjacency Matrix because these three representations form the foundation for working with graphs in programming.
Written by Shubhranshu Shekhar, who has trained 20000+ students in coding.
