Data Structure Graphs Practice Questions with Solutions

By /

Introductions

A Graph is a data structure used to represent relationships between objects. A graph contains vertices (nodes) and edges (connections). Graphs can be directed or undirected, weighted or unweighted, and connected or disconnected. In this chapter, you will practice graph concepts by solving problems such as identifying vertices and edges, calculating degree, representing graphs using adjacency matrices and adjacency lists, checking connections, and understanding simple graph traversal. Data Structure Graphs practice questions with solutions help to understand the concepts.

Question 1: Identify Vertices and Edges

Question

Consider the following undirected graph:

A ----- B
|       |
|       |
C ----- D

Identify all vertices and edges.

Solution

A vertex represents a node in the graph.

The vertices are:

A, B, C, D

Now identify the connections:

A — B
A — C
B — D
C — D

Therefore, there are 4 vertices and 4 edges.

Output

Vertices: A, B, C, D

Edges:
A-B
A-C
B-D
C-D

Answer

The graph contains:

4 vertices
4 edges

Question 2: Count the Number of Edges

Question

How many edges are present in this undirected graph?

      A
     / \
    B---C
     \ /
      D

Solution

List every connection:

A-B
A-C
B-C
B-D
C-D

Now count them:

1. A-B
2. A-C
3. B-C
4. B-D
5. C-D

Output

5

Answer

The graph contains 5 edges.

Question 3: Find the Degree of a Vertex

Question

Find the degree of vertex B in this undirected graph:

      A
      |
      B ----- C
     / \
    D   E

Solution

The degree of a vertex is the number of edges connected to it.

Vertex B is connected to:

A
C
D
E

Count the connections:

4

Output

Degree of B = 4

Answer

The degree of vertex B is 4.

Question 4: Create an Adjacency List

Question

Create an adjacency list for this undirected graph:

A ----- B
|       |
|       |
C ----- D

Solution

The connections are:

A-B
A-C
B-D
C-D

Because the graph is undirected, each connection appears for both vertices.

For example:

A → B, C
B → A, D

Therefore, the complete adjacency list is:

const graph = {
    A: ["B", "C"],
    B: ["A", "D"],
    C: ["A", "D"],
    D: ["B", "C"]
};

console.log(graph);

Output

{
    A: [ "B", "C" ],
    B: [ "A", "D" ],
    C: [ "A", "D" ],
    D: [ "B", "C" ]
}

Answer

The adjacency list is:

A → B, C
B → A, D
C → A, D
D → B, C

Question 5: Create an Adjacency Matrix

Question

Create an adjacency matrix for this undirected graph:

A ----- B
|       
|
C

Solution

The vertices are:

A, B, C

The edges are:

A-B
A-C

Create rows and columns for every vertex.

If two vertices are connected, store 1.

If they are not connected, store 0.

    A B C
A   0 1 1
B   1 0 0
C   1 0 0

JavaScript:

const graph = [
    [0, 1, 1],
    [1, 0, 0],
    [1, 0, 0]
];

console.log(graph);

Output

[
    [0, 1, 1],
    [1, 0, 0],
    [1, 0, 0]
]

Answer

The adjacency matrix is:

    A B C
A   0 1 1
B   1 0 0
C   1 0 0

Question 6: Check Whether Two Vertices are Connected

Question

Consider this graph:

A ----- B
|       |
|       |
C ----- D

Are vertices A and D directly connected?

Solution

Check the edges:

A-B
A-C
B-D
C-D

There is no direct edge:

A-D

However, A can reach D through another vertex.

For example:

A → B → D

So A and D are not directly connected, but they are connected through a path.

Output

Direct connection: No
Path exists: Yes

Answer

A and D do not have a direct edge, but a path exists between them.

Question 7: Represent a Directed Graph

Question

Create an adjacency list for this directed graph:

A → B
↓
C → D

Solution

The directed edges are:

A → B
A → C
C → D

Unlike an undirected graph, the reverse connection is not automatically added.

Therefore:

const graph = {
    A: ["B", "C"],
    B: [],
    C: ["D"],
    D: []
};

console.log(graph);

Output

{
    A: [ "B", "C" ],
    B: [],
    C: [ "D" ],
    D: []
}

Answer

The directed adjacency list is:

A → B, C
B → 
C → D
D →

Question 8: Perform BFS on a Graph

Question

Perform Breadth-First Search (BFS) starting from vertex A.

A ----- B
|       |
C ----- D

Solution

The adjacency list is:

const graph = {
    A: ["B", "C"],
    B: ["A", "D"],
    C: ["A", "D"],
    D: ["B", "C"]
};

BFS uses a queue.

Start from:

A

Queue:

[A]

Visit A and add its neighbors:

B, C

Then visit B and add D.

Next, visit C.

Finally, visit D.

JavaScript:

function bfs(graph, start) {

    let queue = [start];
    let visited = new Set();

    visited.add(start);

    while (queue.length > 0) {

        let vertex = queue.shift();

        console.log(vertex);

        for (let neighbor of graph[vertex]) {

            if (!visited.has(neighbor)) {

                visited.add(neighbor);
                queue.push(neighbor);
            }
        }
    }
}

bfs(graph, "A");

Output

A
B
C
D

Answer

The BFS traversal is:

A → B → C → D

Question 9: Perform DFS on a Graph

Question

Perform Depth-First Search (DFS) starting from vertex A.

A ----- B
|       |
C ----- D

Use this adjacency list:

const graph = {
    A: ["B", "C"],
    B: ["A", "D"],
    C: ["A", "D"],
    D: ["B", "C"]
};

Solution

DFS explores one path as deeply as possible before going back.

Start at:

A

From A, go to B.

From B, go to D.

From D, C is the remaining unvisited neighbor.

Therefore, one valid DFS order is:

A → B → D → C

JavaScript:

function dfs(graph, vertex, visited = new Set()) {

    if (visited.has(vertex)) {
        return;
    }

    visited.add(vertex);

    console.log(vertex);

    for (let neighbor of graph[vertex]) {
        dfs(graph, neighbor, visited);
    }
}

dfs(graph, "A");

Output

A
B
D
C

Answer

One valid DFS traversal is:

A → B → D → C

The exact DFS order can differ depending on the order in which neighbors are stored.

Question 10: Find Whether a Graph is Connected

Question

Check whether this undirected graph is connected:

A ----- B

C ----- D

Solution

A graph is connected when every vertex can be reached from every other vertex through some path.

Here, we have two separate groups:

A — B

and

C — D

There is no connection between these two groups.

Starting from A, we can reach:

A, B

But we cannot reach:

C, D

Therefore, the graph is disconnected.

JavaScript:

const graph = {
    A: ["B"],
    B: ["A"],
    C: ["D"],
    D: ["C"]
};

function isConnected(graph, start) {

    let visited = new Set();
    let stack = [start];

    while (stack.length > 0) {

        let vertex = stack.pop();

        if (visited.has(vertex)) {
            continue;
        }

        visited.add(vertex);

        for (let neighbor of graph[vertex]) {
            stack.push(neighbor);
        }
    }

    return visited.size === Object.keys(graph).length;
}

console.log(isConnected(graph, "A"));

Output

false

Answer

The graph is not connected because there is no path between the groups A-B and C-D.

Key Takeaways

  • A Graph contains vertices (nodes) and edges (connections).
  • An undirected edge works in both directions.
  • A directed edge has a specific direction.
  • A graph can be represented using an adjacency list or adjacency matrix.
  • An adjacency list stores the neighbors of each vertex.
  • An adjacency matrix uses rows and columns to represent connections.
  • The degree of an undirected vertex is the number of edges connected to it.
  • A path is a sequence of vertices connected by edges.
  • A connected graph allows every vertex to be reached from other vertices.
  • BFS uses a queue and explores a graph level by level.
  • DFS explores deeply before returning to previous vertices.
  • A visited set is useful for preventing repeated visits during graph traversal.
  • Graphs are used in maps, social networks, computer networks, recommendation systems, and many other real-world applications.

FAQs

1. What is a Graph in data structures?

A Graph is a non-linear data structure consisting of vertices and edges that represent objects and relationships between them.

2. What is a vertex in a Graph?

A vertex is a node or point in a graph. For example, in a social network, a person can be represented as a vertex.

3. What is an edge in a Graph?

An edge represents a connection between two vertices. For example, a friendship between two people can be represented as an edge.

4. What is the difference between directed and undirected Graphs?

A directed graph has edges with a specific direction, such as A → B. An undirected graph has connections that work in both directions, such as A — B.

5. What is an adjacency list?

An adjacency list stores each vertex along with the vertices directly connected to it.

Example:

A → B, C
B → A
C → A

6. What is an adjacency matrix?

An adjacency matrix is a two-dimensional array where rows and columns represent vertices. A value such as 1 can indicate that two vertices are connected, while 0 indicates no direct connection.

7. What is the difference between BFS and DFS?

BFS explores a graph level by level and commonly uses a queue. DFS explores one path deeply before backtracking and can be implemented using recursion or a stack.

Written by Shubhranshu Shekhar, who has trained 20000+ students in coding.

Related Posts

Scroll to Top