Kruskal's algorithm sorts edges in ascending order of their weights. What data structure is typically used for this sorting step?
Heap
Linked List
Stack
Queue
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 lowest fuel consumption.
Finding the path with the shortest geographical distance.
Finding the path with the least overall travel time, considering delays.
Finding the path with the fewest road closures.
What is the purpose of topological sorting in directed acyclic graphs (DAGs)?
Finding the shortest path between any two vertices.
Calculating the minimum spanning tree of the graph.
Determining if the graph has a Hamiltonian cycle.
Finding a linear ordering of vertices where for every edge (u, v), u comes before v.
Which graph representation is particularly well-suited for representing graphs with parallel edges (multiple edges between the same pair of vertices)?
None of the above
Edge List
Adjacency Matrix
Incidence Matrix
If a graph has negative weight cycles, what can we say about finding the shortest path?
Bellman-Ford algorithm will take significantly longer to find the shortest path.
Dijkstra's algorithm will always find the correct shortest path.
The graph must be undirected to have negative weight cycles.
The shortest path is undefined as we can keep traversing the cycle, decreasing the path length infinitely.
If you need to perform frequent edge insertions and deletions in a graph, which representation might be preferred?
It depends on the specific graph operations
How does the concept of 'distance' in a weighted graph differ from that in an unweighted graph?
There is no difference; 'distance' has the same meaning in both types of graphs.
In a weighted graph, 'distance' represents the sum of edge weights along a path, while in an unweighted graph, it's the number of edges.
In weighted graphs, 'distance' always refers to geographical distance, while in unweighted graphs, it can represent abstract relationships.
Distance is only defined for unweighted graphs.
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)
Breadth-First Search (BFS)
Kruskal's Algorithm
Prim's Algorithm
Consider a social network graph where vertices are users and edges are friendships. Which representation would be best for quickly finding all the friends of a particular user?
Adjacency List
You are tasked with designing a system to schedule tasks with dependencies between them. What graph data structure would be most appropriate to represent these dependencies?
Undirected Graph
Directed Acyclic Graph (DAG)
Complete Graph
Bipartite Graph