Which of the following algorithms is typically used for topological sorting?
Depth-First Search (DFS)
Kruskal's algorithm
Dijkstra's algorithm
Prim's algorithm
Why are negative weights problematic for some shortest path algorithms?
All of the above
Algorithms like Dijkstra's rely on the principle that shorter paths are always discovered before longer ones.
These algorithms assume that adding an edge to a path always increases its total weight.
Negative weights can lead to cycles where the total weight decreases with each iteration, confusing the algorithm.
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 may contain cycles
It connects all vertices in the graph
Which representation would be most suitable for a graph where you primarily need to iterate over all edges efficiently?
Edge List
Adjacency Matrix
Adjacency List
Incidence Matrix
Social media platforms utilize graph analysis to detect communities or clusters of users with shared interests. What graph concept is employed to identify these densely connected groups?
Community Detection
Minimum Spanning Tree
Shortest Path
Graph Coloring
Kruskal's algorithm sorts edges in ascending order of their weights. What data structure is typically used for this sorting step?
Linked List
Queue
Stack
Heap
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?
Directed Acyclic Graph (DAG)
Bipartite Graph
Undirected Graph
Complete Graph
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 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.
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
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