Topological sorting is possible for which type of graph?
Complete graphs
Undirected graphs
Directed acyclic graphs (DAGs)
Weighted graphs
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
If you need to perform frequent edge insertions and deletions in a graph, which representation might be preferred?
Edge List
Adjacency Matrix
Incidence Matrix
It depends on the specific graph operations
Which of the following is NOT a characteristic of a minimum spanning tree (MST)?
It has the minimum total edge weight
It is a tree (acyclic)
It may contain cycles
It connects all vertices in the graph
What is the primary application of topological sorting in computer science?
Scheduling tasks with dependencies
Detecting cycles in a graph
Finding the shortest path between two nodes
Finding the minimum spanning tree of a graph
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
Which of the following operations is typically less efficient with an edge list representation compared to an adjacency matrix?
Determining the degree of a vertex
Checking if the graph is connected
Finding all edges connected to a specific vertex
Adding a new edge
How does the concept of 'distance' in a weighted graph differ from that in an unweighted graph?
Distance is only defined for unweighted 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.
There is no difference; 'distance' has the same meaning in both types of graphs.
Which of the following algorithms is typically used for topological sorting?
Prim's algorithm
Kruskal's algorithm
Dijkstra's algorithm
Which algorithm efficiently calculates the shortest paths between all pairs of nodes in a weighted graph, useful for analyzing network connectivity in social networks?
Dijkstra's Algorithm
Floyd-Warshall Algorithm
Bellman-Ford Algorithm