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 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.
Unweighted graphs are used for simple relationships, while weighted graphs are used for complex mathematical computations.
Kruskal's algorithm sorts edges in ascending order of their weights. What data structure is typically used for this sorting step?
Heap
Queue
Stack
Linked List
If you need to perform frequent edge insertions and deletions in a graph, which representation might be preferred?
Edge List
Adjacency Matrix
It depends on the specific graph operations
Incidence Matrix
Which of the following is NOT a characteristic of a minimum spanning tree (MST)?
It is a tree (acyclic)
It has the minimum total edge weight
It connects all vertices in the graph
It may contain cycles
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)
Which of the following algorithms is typically used for topological sorting?
Dijkstra's algorithm
Depth-First Search (DFS)
Prim's algorithm
Kruskal's algorithm
What is the primary application of topological sorting in computer science?
Finding the minimum spanning tree of a graph
Scheduling tasks with dependencies
Detecting cycles in a graph
Finding the shortest path between two nodes
Topological sorting is possible for which type of graph?
Undirected graphs
Directed acyclic graphs (DAGs)
Complete graphs
Weighted graphs
In a graph with a large number of vertices but relatively few edges (sparse graph), which representation would be most space-efficient?
None of the above
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
Tracking the spread of information in a social network
Representing relationships in a family tree