Kruskal's algorithm sorts edges in ascending order of their weights. What data structure is typically used for this sorting step?
Queue
Linked List
Heap
Stack
What is the primary distinction between an unweighted graph and a weighted graph?
Unweighted graphs are used for simple relationships, while weighted graphs are used for complex mathematical computations.
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.
What value is stored in the cells of an incidence matrix to represent that a vertex is NOT incident to an edge?
-1
Infinity
1
0
Which algorithm efficiently calculates the shortest paths between all pairs of nodes in a weighted graph, useful for analyzing network connectivity in social networks?
Bellman-Ford Algorithm
Floyd-Warshall Algorithm
Dijkstra's Algorithm
Kruskal's Algorithm
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?
Topological Sort
A* Search Algorithm
What is the primary challenge in finding shortest paths in graphs with negative weight cycles?
Negative weights make it impossible to define a meaningful concept of 'shortest' path.
Standard shortest path algorithms are not designed to handle cycles.
The presence of cycles makes the graph too complex for efficient shortest path algorithms.
The shortest path might involve traversing a cycle repeatedly to minimize the total weight.
Which of the following real-world scenarios is best modeled using a weighted graph with potentially negative edge weights?
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
Tracking the spread of information in a social network
You are building a flight routing system. What graph algorithm can you use to find the cheapest flight itinerary with potentially multiple layovers?
Depth-First Search (DFS)
Which representation would be most suitable for a graph where you primarily need to iterate over all edges efficiently?
Adjacency Matrix
Edge List
Incidence Matrix
Adjacency List
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