Which of the following graph algorithms is best suited for finding the shortest path in a weighted graph?
Depth-First Search
Breadth-First Search
Topological Sort
Dijkstra's Algorithm
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.
Representing the hierarchical structure of a company.
Finding the shortest path between two cities on a road network with distances.
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(E)
O(V)
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
Vertices at the same distance from the source vertex are visited before moving to vertices further away
Alphabetical order
Increasing order of their degree (number of connections)
In the context of graph traversal, what does 'backtracking' refer to in Depth-First Search (DFS)?
Skipping certain branches of the graph to improve efficiency.
Returning to the parent node after exploring all descendants of a node.
Revisiting already explored nodes to find alternative paths.
Using a heuristic function to guide the search towards the goal node.
Consider a graph where you want to find if a path exists between two given nodes. Which traversal algorithm would be generally more efficient for this task?
Depth-First Search (DFS)
Both DFS and BFS have the same efficiency for this task.
Neither DFS nor BFS can determine if a path exists between two nodes.
Breadth-First Search (BFS)
How does the iterative implementation of Depth-First Search (DFS) typically differ from its recursive counterpart?
The iterative approach is not suitable for traversing graphs with cycles.
The iterative approach is generally less efficient in terms of space complexity than recursion.
The iterative approach uses a stack to mimic the function call stack used in recursion.
The iterative and recursive approaches produce fundamentally different traversal orders.
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.
Simulating the spread of information or a virus in a social network.
Finding the shortest path between two locations on a map.
Crawling and indexing web pages starting from a seed URL.
Which of the following graph representations is most efficient for checking if two vertices are adjacent?
Adjacency Matrix
Adjacency List
Incidence Matrix
Edge List
A cycle in a graph that is not a simple cycle (visits a vertex more than once) is called a:
Path
Closed Walk
Trail
Circuit