What is the primary application of topological sorting in computer science?
Finding the shortest path between two nodes
Detecting cycles in a graph
Finding the minimum spanning tree of a graph
Scheduling tasks with dependencies
Prim's algorithm for finding the MST starts with an arbitrary vertex. Does the choice of the starting vertex affect the final MST found?
No, the MST is unique for a given graph
Yes, different starting vertices may lead to different MSTs
Kruskal's algorithm sorts edges in ascending order of their weights. What data structure is typically used for this sorting step?
Queue
Heap
Linked List
Stack
Which of the following real-world scenarios is best modeled using a weighted graph with potentially negative edge weights?
Representing relationships in a family tree
Modeling financial transactions where profits and losses are possible
Tracking the spread of information in a social network
Finding the shortest route between two cities on a map
Which of the following algorithms can handle negative weights in a weighted graph without issues?
Dijkstra's Algorithm
Bellman-Ford Algorithm
Prim's Algorithm
Breadth-First Search (BFS)
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
A* Search Algorithm
Topological Sort
Which of the following algorithms is typically used for topological sorting?
Depth-First Search (DFS)
Kruskal's algorithm
Dijkstra's algorithm
Prim's algorithm
What value is stored in the cells of an incidence matrix to represent that a vertex is NOT incident to an edge?
-1
Infinity
0
1
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.
You are designing a social network and want to recommend friends to users. What graph algorithm would be most suitable for identifying potential friends based on shared connections?