Graph - Quiz | Analytics

Q: What is the Bellman-Ford algorithm used for in graph theory?

A. To find the shortest path between two nodes in a weighted graph
B. To find the longest path between two nodes in a weighted graph
C. To find the minimum spanning tree of a graph
D. To find the maximum flow in a network

Correct Option: A
Explanation: To find the shortest path between two nodes in a weighted graph (it can also detect negative cycles in the graph)

Q: What is a connected graph?

A. A graph in which there are no cycles
B. A graph in which every node has a unique degree
C. A graph in which every node is connected to at least one other node
D. A graph in which every node is connected to every other node

Correct Option: C
Explanation: A graph in which every node is connected to at least one other node

Q: What is a topological sort?

A. A way to sort the vertices of a graph based on their degrees
B. A way to sort the vertices of a graph based on their distances from a particular node
C. A way to sort the vertices of a directed acyclic graph based on their dependencies
D. A way to sort the edges of a graph based on their weights

Correct Option: C
Explanation:

A way to sort the vertices of a directed acyclic graph based on their dependencies.

Note: A topological sort is only possible for a directed acyclic graph (DAG) as there should not be any cycles in it. It provides a linear ordering of the vertices such that for every directed edge uv from vertex u to vertex v, u comes before v in the ordering.

Q: What is a path in a graph?

A. A sequence of nodes in a graph
B. A sequence of edges in a graph
C. A sequence of nodes and edges in a graph
D. A cycle in a graph

Correct Option: C
Explanation: A sequence of nodes and edges in a graph

Q: What is a graph?

A. A linear data structure in which elements are arranged in a sequence
B. A non-linear data structure in which elements are arranged in a hierarchy
C. A non-linear data structure in which elements are arranged in a network
D. A data structure that represents a set of elements and their relationships

Correct Option: C
Explanation: A non-linear data structure in which elements are arranged in a network

Q: What is a spanning tree?

A. A tree that contains all nodes of a graph and a subset of its edges
B. A tree that contains some nodes of a graph and a subset of its edges
C. A tree that contains all nodes of a graph and all of its edges
D. A tree that contains some nodes of a graph and all of its edges

Correct Option: A
Explanation: A tree that contains all nodes of a graph and a subset of its edges

Q: What is a vertex in a graph?

A. A node that has no outgoing edges
B. A node that has no incoming edges
C. A node in a graph
D. A node that is connected to another node by an edge

Correct Option: C
Explanation: A node in a graph

Q: What is a cycle in a graph?

A. A sequence of nodes in a graph
B. A sequence of edges in a graph
C. A sequence of nodes and edges in a graph
D. A path that ends where it starts

Correct Option: D
Explanation: A path that ends where it starts

Q: What is the time complexity of Breadth First Search (BFS) on a graph with V vertices and E edges?

A. O(V+E)
B. O(V^2)
C. O(E^2)
D. O(log V)

Correct Option: A
Explanation: O(V+E)

Q: What is Dijkstra's algorithm used for in graph theory?

A. To find the shortest path between two nodes in a weighted graph
B. To find the longest path between two nodes in a weighted graph
C. To find the minimum spanning tree of a graph
D. To find the maximum flow in a network

Correct Option: A
Explanation: To find the shortest path between two nodes in a weighted graph