Which of the following situations would make Bellman-Ford algorithm a better choice than Dijkstra's algorithm?
Finding the shortest path in a dense graph
Finding the shortest path in an unweighted graph
Finding the shortest path in a graph with negative edge weights
Finding the shortest path in a tree
In the context of Kruskal's algorithm, what data structure is commonly used to efficiently detect cycles during edge addition?
Disjoint Union Set (Union-Find)
Queue
Stack
Heap
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 least overall travel time, considering delays.
Finding the path with the shortest geographical distance.
Finding the path with the lowest fuel consumption.
Finding the path with the fewest road closures.
Which of the following is NOT a characteristic of a minimum spanning tree (MST)?
It has the minimum total edge weight
It connects all vertices in the graph
It may contain cycles
It is a tree (acyclic)
Which of the following real-world scenarios is best modeled using a weighted graph with potentially negative edge weights?
Tracking the spread of information in a social network
Modeling financial transactions where profits and losses are possible
Finding the shortest route between two cities on a map
Representing relationships in a family tree
Topological sorting is possible for which type of graph?
Undirected graphs
Complete graphs
Weighted graphs
Directed acyclic graphs (DAGs)
If you need to perform frequent edge insertions and deletions in a graph, which representation might be preferred?
Adjacency Matrix
Edge List
Incidence Matrix
It depends on the specific graph operations
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.
Calculating the minimum spanning tree of the graph.
Determining if the graph has a Hamiltonian cycle.
What is the primary application of topological sorting in computer science?
Detecting cycles in a graph
Scheduling tasks with dependencies
Finding the minimum spanning tree of a graph
Finding the shortest path between two nodes
What is the primary distinction between an unweighted graph and a weighted graph?
Unweighted graphs represent connections, while weighted graphs represent connections with associated costs or distances.
Unweighted graphs are used for simple relationships, while weighted graphs are used for complex mathematical computations.
Unweighted graphs are always undirected, while weighted graphs are always directed.
Unweighted graphs have a fixed number of vertices, while weighted graphs can have a variable number of vertices.