Which of the following scenarios is particularly well-suited for applying a Depth-First Search (DFS) algorithm?
Solving mazes or navigating through grid-based environments.
Finding the shortest path between two locations on a map.
Crawling and indexing web pages starting from a seed URL.
Simulating the spread of information or a virus in a social network.
What is the time complexity of performing a Breadth-First Search on a graph with 'V' vertices and 'E' edges?
O(V + E)
O(V * E)
O(V)
O(E)
Which of the following is the BEST representation of a graph when the number of edges is much smaller than the number of vertices?
Adjacency List
Adjacency Matrix
Incidence Matrix
Edge List
Which of the following graph traversal algorithms is generally more suitable for finding the shortest path in an unweighted graph?
Both DFS and BFS are equally suitable.
Breadth-First Search (BFS)
Depth-First Search (DFS)
Neither DFS nor BFS can find shortest paths in unweighted graphs.
What is a common way to keep track of visited nodes during graph traversal to avoid cycles and infinite loops?
Maintaining a separate list or set of visited nodes.
Using a special 'visited' flag or attribute within the node's data structure.
Assigning weights to edges based on whether they lead to visited nodes.
Both options 1 and 3 are common and effective approaches.
A cycle in a graph that is not a simple cycle (visits a vertex more than once) is called a:
Path
Trail
Closed Walk
Circuit
What does a '1' represent in an adjacency matrix of an undirected graph?
The weight of the edge.
The presence of an edge between two vertices.
The direction of the edge.
The degree of the vertex.
A graph is said to be __________ if there is a path from any vertex to any other vertex.
Connected
Bipartite
Complete
Disconnected
You are performing a Breadth-First Search on a graph. Which of the following best describes the order in which vertices are visited?
Random order
Increasing order of their degree (number of connections)
Vertices at the same distance from the source vertex are visited before moving to vertices further away
Alphabetical order
Which of these scenarios is BEST represented using a weighted graph?
Storing the friendship relations between people on a social media platform.
Modeling the flow of information in a computer network.
Finding the shortest path between two cities on a road network with distances.
Representing the hierarchical structure of a company.