What is the time complexity of the A* search algorithm in the worst case, assuming a consistent heuristic?
O(V + E), where V is the number of vertices and E is the number of edges
O(E log V), where V is the number of vertices and E is the number of edges
It depends on the heuristic function and can be exponential in the worst case.
O(V^2), where V is the number of vertices
What is the relationship between A* search and Dijkstra's algorithm?
A* is a generalization of Dijkstra's algorithm.
Dijkstra's algorithm is a special case of A* search.
A* and Dijkstra's algorithm are entirely unrelated.
A* is only applicable to unweighted graphs, while Dijkstra's algorithm works for weighted graphs.
In a directed graph, what is the necessary and sufficient condition for the existence of an Eulerian path?
The graph is strongly connected.
All vertices have the same in-degree and out-degree.
The graph has no cycles.
At most two vertices have a difference of 1 between their in-degree and out-degree, and all other vertices have equal in-degree and out-degree.
Which of the following statements is NOT TRUE about a graph with a Hamiltonian cycle?
The graph is planar.
The number of vertices is greater than or equal to 3.
The graph is connected.
Every vertex has a degree of at least 2.
Dijkstra's algorithm can be considered a special case of which algorithm when applied to graphs with non-negative edge weights?
Breadth First Search
Bellman-Ford Algorithm
Depth First Search
A* Search
In a graph coloring problem, what scenario leads to the requirement of an additional color?
Removing an edge between two vertices with the same color.
Adding an edge between two vertices with different colors.
Adding a new vertex and connecting it to an existing vertex.
Adding a new vertex and connecting it to all existing vertices.
In A* search, what does the heuristic function estimate?
The cost of the cheapest path from the current node to the goal node
The total cost of the path from the start node to the current node
The depth of the current node in the search tree
The number of nodes that are yet to be explored
What is the primary advantage of using the Floyd-Warshall algorithm over Dijkstra's algorithm for finding shortest paths in a graph?
It can detect negative weight cycles.
It can handle graphs with negative edge weights.
It only requires a single source vertex as input.
It is more efficient for sparse graphs.
What is a potential drawback of using A* search in practice?
It can only be applied to problems in two-dimensional space.
It is not guaranteed to find a solution even if one exists.
It can be computationally expensive for large graphs with complex heuristics.
It always requires an admissible heuristic, which can be difficult to define.
In the context of the Floyd-Warshall algorithm, what does a diagonal element of the distance matrix represent after the algorithm has completed?
The shortest distance from a vertex to itself.
Infinity if there is no path from the vertex to itself.
The shortest distance from the source vertex to that vertex.
The number of edges in the shortest path from a vertex to itself.