What is the primary application of topological sorting in computer science?
Finding the minimum spanning tree of a graph
Detecting cycles in a graph
Finding the shortest path between two nodes
Scheduling tasks with dependencies
What is the primary distinction between an unweighted graph and a weighted graph?
Unweighted graphs have a fixed number of vertices, while weighted graphs can have a variable number of vertices.
Unweighted graphs represent connections, while weighted graphs represent connections with associated costs or distances.
Unweighted graphs are always undirected, while weighted graphs are always directed.
Unweighted graphs are used for simple relationships, while weighted graphs are used for complex mathematical computations.
In a weighted graph representing a road network with construction delays (represented by negative weights), what does finding the 'shortest path' mean?
Finding the path with the fewest road closures.
Finding the path with the shortest geographical distance.
Finding the path with the lowest fuel consumption.
Finding the path with the least overall travel time, considering delays.
What is the purpose of topological sorting in directed acyclic graphs (DAGs)?
Determining if the graph has a Hamiltonian cycle.
Finding a linear ordering of vertices where for every edge (u, v), u comes before v.
Finding the shortest path between any two vertices.
Calculating the minimum spanning tree of the graph.
Which of the following situations would make Bellman-Ford algorithm a better choice than Dijkstra's algorithm?
Finding the shortest path in a graph with negative edge weights
Finding the shortest path in an unweighted graph
Finding the shortest path in a dense graph
Finding the shortest path in a tree
Which graph traversal algorithm is most efficient for detecting cycles in a directed graph, crucial for identifying dependencies in a project management system?
Depth-First Search (DFS)
Prim's Algorithm
Kruskal's Algorithm
Breadth-First Search (BFS)
Why are negative weights problematic for some shortest path algorithms?
These algorithms assume that adding an edge to a path always increases its total weight.
All of the above
Negative weights can lead to cycles where the total weight decreases with each iteration, confusing the algorithm.
Algorithms like Dijkstra's rely on the principle that shorter paths are always discovered before longer ones.
Topological sorting is possible for which type of graph?
Weighted graphs
Complete graphs
Undirected graphs
Directed acyclic graphs (DAGs)
You are building a flight routing system. What graph algorithm can you use to find the cheapest flight itinerary with potentially multiple layovers?
A* Search Algorithm
Bellman-Ford Algorithm
Dijkstra's Algorithm
Which graph representation is particularly well-suited for representing graphs with parallel edges (multiple edges between the same pair of vertices)?
Incidence Matrix
Adjacency Matrix
None of the above
Edge List