Which graph traversal algorithm is most efficient for detecting cycles in a directed graph, crucial for identifying dependencies in a project management system?
Kruskal's Algorithm
Breadth-First Search (BFS)
Prim's Algorithm
Depth-First Search (DFS)
Which of the following algorithms can handle negative weights in a weighted graph without issues?
Dijkstra's Algorithm
Bellman-Ford Algorithm
Why are negative weights problematic for some shortest path algorithms?
Algorithms like Dijkstra's rely on the principle that shorter paths are always discovered before longer ones.
Negative weights can lead to cycles where the total weight decreases with each iteration, confusing the algorithm.
All of the above
These algorithms assume that adding an edge to a path always increases its total weight.
Which algorithm is more suitable for finding the shortest path in a graph with negative edge weights?
Prim's algorithm
Kruskal's algorithm
Dijkstra's algorithm
Bellman-Ford algorithm
What is the purpose of topological sorting in directed acyclic graphs (DAGs)?
Finding the shortest path between any two vertices.
Finding a linear ordering of vertices where for every edge (u, v), u comes before v.
Determining if the graph has a Hamiltonian cycle.
Calculating the minimum spanning tree of the graph.
In a GPS navigation system, what graph algorithm is commonly used to find the shortest route between two locations represented as nodes on a road network?
Floyd-Warshall Algorithm
Topological Sort
A* Search Algorithm
Topological sorting is possible for which type of graph?
Complete graphs
Undirected graphs
Weighted graphs
Directed acyclic graphs (DAGs)
In the context of Kruskal's algorithm, what data structure is commonly used to efficiently detect cycles during edge addition?
Queue
Disjoint Union Set (Union-Find)
Heap
Stack
What is the primary application of topological sorting in computer science?
Detecting cycles in a graph
Scheduling tasks with dependencies
Finding the shortest path between two nodes
Finding the minimum spanning tree of a graph
Which of the following situations would make Bellman-Ford algorithm a better choice than Dijkstra's algorithm?
Finding the shortest path in an unweighted graph
Finding the shortest path in a tree
Finding the shortest path in a dense graph
Finding the shortest path in a graph with negative edge weights