Graphs: Representation and Traversal - Interactive Learning Quizzes

Question 1

What is the main distinction between a directed and an undirected graph?

Accepted Answer

Edges in directed graphs have an assigned direction, while edges in undirected graphs do not.

Answer

Undirected graphs have cycles, while directed graphs do not.

Answer

Directed graphs have vertices with weights, while undirected graphs do not.

Answer

Undirected graphs have multiple edges between vertices, while directed graphs do not.

Question 2

Which of the following is NOT a type of graph representation?

Accepted Answer

Binary tree

Answer

Adjacency list

Answer

Adjacency matrix

Answer

Edge list

Question 3

Which data structure is typically used to store the vertices in an adjacency list representation?

Accepted Answer

Linked list

Answer

Stack

Answer

Queue

Answer

Array

Question 4

A tree is a graph that is:

Accepted Answer

Connected and has no cycles

Answer

Complete and has no cycles

Answer

Weighted and has no cycles

Answer

Directed and has no cycles

Question 5

Which of the following is NOT a valid graph representation?

Accepted Answer

Hash table

Answer

Adjacency matrix

Answer

Adjacency list

Answer

Incidence matrix

Question 6

Which of the following is a characteristic of a directed graph?

Accepted Answer

Edges have a direction

Answer

Graphs are connected

Answer

Vertices are labeled

Answer

Graphs have cycles

Question 7

Which of the following traversal techniques guarantees to find the shortest path between two vertices in a weighted graph?

Accepted Answer

Dijkstra's Algorithm

Answer

Depth-First Search (DFS)

Answer

Breadth-First Search (BFS)

Answer

Prim's Algorithm

Question 8

What is the difference between a cycle and a path in a graph?

Accepted Answer

A cycle has a starting and ending vertex that are the same, while a path does not.

Answer

A path has a starting and ending vertex that are different, while a cycle does not.

Answer

A cycle can contain repeated vertices, while a path cannot.

Answer

A path can contain repeated vertices, while a cycle cannot.

Question 9

Which of the following algorithms can be used to detect cycles in a directed graph?

Accepted Answer

Depth-First Search (DFS)

Answer

Kruskal's Algorithm

Answer

Breadth-First Search (BFS)

Answer

Dijkstra's Algorithm

Question 10

Which graph traversal algorithm explores all the nodes at a given depth before moving to the next depth?

Accepted Answer

Depth-First Search (DFS)

Answer

Breadth-First Search (BFS)

Answer

Topological Sort

Answer

Dijkstra's algorithm

Question 11

Which of the following is a weighted graph?

Accepted Answer

A graph where each edge has a numerical value associated with it

Answer

A graph where each node has a numerical value associated with it

Answer

A graph where the edges are directed

Answer

A graph where the nodes are labeled

Question 12

Which algorithm can be used to find the shortest path between two nodes in a weighted graph?

Accepted Answer

Dijkstra's algorithm

Answer

Depth-First Search (DFS)

Answer

Breadth-First Search (BFS)

Answer

Kruskal's algorithm

Question 13

Consider the following adjacency matrix of a graph: [[0, 1, 0, 0], [1, 0, 1, 0], [0, 1, 0, 1], [0, 0, 1, 0]]. Which of the following edges is NOT present in the graph?

Accepted Answer

A -> D

Answer

A -> B

Answer

B -> C

Answer

C -> D

Question 14

Which of the following is a directed graph?

Accepted Answer

A graph where the edges have  a direction associated with them

Answer

A graph where the nodes have a direction associated with them

Answer

A graph where the edges are weighted

Answer

A graph where the nodes are labeled

Question 15

What is the time complexity of Depth-First Search (DFS) on a graph with V vertices and E edges?

Accepted Answer

O(V + E)

Answer

O(V^2 + E^2)

Answer

O(E log V)

Answer

O(V log E)

Question 16

What is the purpose of a minimum spanning tree (MST) in a graph?

Accepted Answer

To connect all vertices with the fewest possible edges

Answer

To find the shortest path between any two vertices

Answer

To detect cycles in a graph

Answer

To find the longest path between any two vertices

Question 17

What is the key difference between a connected graph and a strongly connected graph?

Accepted Answer

Strongly connected graphs have paths between all vertices in both directions, while connected graphs do not.

Answer

Strongly connected graphs have cycles, while connected graphs do not.

Answer

Connected graphs have paths between all vertices, while strongly connected graphs do not.

Answer

There is no difference between connected graphs and strongly connected graphs.

Question 18

Which of the following graph applications is used for social network analysis?

Accepted Answer

Finding communities within a social network

Answer

Routing traffic in a network of routers

Answer

Scheduling tasks in a computer system

Answer

Representing molecule structures

Question 19

What is the maximum number of edges in a simple undirected graph with n vertices?

Accepted Answer

n (n - 1) / 2

Answer

n - 1

Answer

n

Answer

n^2

Question 20

Which of the following is a key characteristic of a planar graph?

Accepted Answer

It can be drawn without crossing edges.

Answer

It does not contain any cycles.

Answer

It is a complete graph.

Answer

It is a bipartite graph.

Question 21

What distinguishes a spanning tree from a minimum spanning tree in a graph?

Accepted Answer

A minimum spanning tree is a spanning tree with the lowest total weight, while a spanning tree may not have the lowest weight.

Answer

A spanning tree connects all vertices with the least number of edges, while a minimum spanning tree connects all vertices with the shortest path.

Answer

A spanning tree does not have any cycles, whereas a minimum spanning tree can have cycles.

Answer

There is no difference between a spanning tree and a minimum spanning tree.

Question 22

In graph theory, what are connected components, and how can you efficiently identify them using an algorithm?

Accepted Answer

Connected components are subgraphs where every pair of vertices is reachable through a path.

Answer

Connected components are subgraphs where all edges are connected to at least one vertex.

Answer

Connected components are subgraphs where every vertex has a degree of at least one.

Answer

Connected components are only found in directed graphs.

Question 23

Which graph traversal algorithm uses a stack data structure to explore the graph?

Accepted Answer

Depth-First Search (DFS)

Answer

Breadth-First Search (BFS)

Answer

Dijkstra's Algorithm

Answer

Kruskal's Algorithm

Question 24

What is the time complexity of performing Depth-First Search (DFS) on a connected, undirected graph with V vertices and E edges?

Accepted Answer

O(V + E)

Answer

O(V^2)

Answer

O(E log V)

Answer

O(E^2)

Question 25

Which type of graph assigns a weight to each edge?

Accepted Answer

Weighted graph

Answer

Unweighted graph

Answer

Directed graph

Answer

Undirected graph

Question 26

What is the purpose of marking vertices as visited during graph traversal?

Accepted Answer

To avoid revisiting previously explored vertices

Answer

To store the shortest path to each vertex

Answer

To represent the adjacency list of the graph

Answer

To store the weights of the edges in the graph

Question 27

Which algorithm can be used to find the minimum spanning tree of a weighted, connected graph?

Accepted Answer

Kruskal's Algorithm

Answer

Breadth-First Search (BFS)

Answer

Depth-First Search (DFS)

Answer

Dijkstra's Algorithm

Question 28

Which type of directed graph has no directed cycles?

Accepted Answer

Directed Acyclic Graph (DAG)

Answer

Tree

Answer

Cycle

Answer

Undirected graph

Question 29

What is the degree of a vertex in a graph?

Accepted Answer

The number of edges connected to that vertex

Answer

The number of vertices connected to that vertex

Answer

The total weight of the edges connected to that vertex

Answer

The number of cycles that pass through that vertex

Question 30

What is topological sorting and how does it help manage task dependencies in project management?

Accepted Answer

Topological sorting arranges nodes in a directed acyclic graph (DAG) so that edges flow from lower-ranked to higher-ranked nodes.

Answer

Topological sorting finds the shortest path between two nodes in a graph.

Answer

Topological sorting works on both directed and undirected graphs.

Answer

Topological sorting detects cycles in a graph.

Question 31

Identify an application of graph theory primarily used in computer graphics.

Accepted Answer

Modeling 3D Objects

Answer

Managing Relational Databases

Answer

Scheduling Tasks in an Operating System

Question 32

Which graph visualization technique is designed to clearly display hierarchical relationships within a graph, making it easier to recognize nested structures?

Accepted Answer

Tree layout

Answer

Force-directed layout

Answer

Radial layout

Answer

Layered layout

Question 33

Which of the following is NOT a valid representation for graphs?

Accepted Answer

Binary tree

Answer

Adjacency matrix

Answer

Adjacency list

Answer

Incidence matrix

Question 34

Depth-First Search (DFS) has a time complexity of O( ) on a graph with V vertices and E edges

Accepted Answer

O(V + E)

Answer

O(E)

Answer

O(V^2 + E^2)

Answer

O(V)

Question 35

Which of the following traversal techniques ensures visiting all nodes in a graph?

Accepted Answer

Breadth-First Search (BFS)

Answer

Depth-First Search (DFS)

Answer

Prim's algorithm

Answer

Dijkstra's algorithm

Question 36

Which of the following is an example of a graph theory application?

Accepted Answer

Social network analysis

Answer

Quantum mechanics

Answer

Prime factorization

Answer

Calculus optimization

Question 37

In a graph, the degree of a node represents

Accepted Answer

The number of edges connected to the node

Answer

The weight of the node

Answer

The distance to the root node

Question 38

In a graph, what is the purpose of a weighted edge?

Accepted Answer

Representing the cost or distance between two nodes

Answer

Determining the degree of the nodes connected by the edge

Answer

Indicating the direction of the edge

Question 39

In a Depth-First Search (DFS), what is the primary data structure used for traversal?

Accepted Answer

Stack

Answer

Heap

Answer

Trie

Answer

Queue

Question 40

In a Breadth-First Search (BFS), what type of data structure is utilized to store unvisited nodes?

Accepted Answer

Queue

Answer

Tree

Answer

Trie

Answer

Stack

Question 41

Which traversal algorithm is specifically designed to find the shortest path between two nodes in a weighted graph?

Accepted Answer

Dijkstra's Algorithm

Answer

Breadth-First Search

Answer

Prim's Algorithm

Answer

Depth-First Search

Question 42

Which graph traversal algorithm is most suitable for detecting the presence of cycles in a graph?

Accepted Answer

Depth-First Search

Answer

Breadth-First Search

Answer

Topological Sort

Answer

Kruskal's Algorithm

Question 43

Which of the following is NOT a standard graph representation?

Accepted Answer

Ternary tree

Answer

Incidence matrix

Answer

Adjacency matrix

Answer

Adjacency list

Question 44

In an adjacency list representation of a graph, what does each node in the list represent?

Accepted Answer

A vertex adjacent to the current vertex

Answer

The distance to the root vertex from the current vertex

Answer

The weight of an edge connected to the current vertex

Answer

The number of edges connected to the current vertex

Question 45

Which graph traversal technique guarantees visiting all nodes in a graph exactly once, and in the same order every time?

Accepted Answer

None of the above

Answer

Breadth-First Search (BFS)

Answer

Depth-First Search (DFS)

Answer

Random Walk

Question 46

What is the time complexity of Depth-First Search (DFS) on a graph with 'V' vertices and 'E' edges?

Accepted Answer

O(V + E)

Answer

O(V^2)

Answer

O(E^2)

Answer

O(V)

Question 47

Which of the following is a common application of Depth-First Search (DFS)?

Accepted Answer

Cycle detection in a graph

Answer

Topological sorting of a directed acyclic graph (DAG)

Answer

Finding the shortest path between two vertices

Answer

Finding the minimum spanning tree of a graph

Question 48

In an adjacency matrix representation of a weighted graph, what does the value at the intersection of row 'i' and column 'j' represent?

Accepted Answer

The weight of the edge between vertices 'i' and 'j', or 0 if no edge exists

Answer

The vertex label of vertex 'j'

Answer

The distance between vertices 'i' and 'j'

Answer

The number of edges between vertices 'i' and 'j'

Question 49

Which of the following is a significant disadvantage of using an adjacency matrix to represent a graph?

Accepted Answer

High space complexity, O(V^2), especially for sparse graphs

Answer

Not suitable for directed graphs

Answer

Inefficient for adding new vertices

Answer

Difficult to implement

Question 50

When is a topological sorting algorithm most appropriately used on a graph?

Accepted Answer

When the graph is a directed acyclic graph (DAG)

Answer

When the graph represents a social network

Answer

When the graph is undirected

Answer

When the graph is weighted

Question 51

What is the fundamental difference between Depth-First Search (DFS) and Breadth-First Search (BFS) traversal?

Accepted Answer

DFS explores the graph depth-wise, while BFS explores it breadth-wise.

Answer

DFS is recursive, while BFS is iterative.

Answer

DFS can detect cycles, while BFS cannot.

Answer

DFS is faster than BFS for most graphs.

Question 52

Consider a graph with 'n' vertices and 'm' edges. Which of the following operations on the graph can be performed in O(1) time using an adjacency list representation?

Accepted Answer

Adding a new edge between two existing vertices

Answer

Finding the shortest path between two vertices

Answer

Adding a new vertex to the graph

Answer

Finding the number of edges connected to a vertex