Kruskal's algorithm sorts edges in ascending order of their weights. What data structure is typically used for this sorting step?
Queue
Heap
Stack
Linked List
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.
The shortest path might involve traversing a cycle repeatedly to minimize the total weight.
Standard shortest path algorithms are not designed to handle cycles.
The presence of cycles makes the graph too complex for efficient shortest path algorithms.
An incidence matrix for a graph with 'V' vertices and 'E' edges will have dimensions:
E x E
V x E
V x V
Depends on the graph's connectivity
Consider a social network graph where vertices are users and edges are friendships. Which representation would be best for quickly finding all the friends of a particular user?
Adjacency List
Adjacency Matrix
Incidence Matrix
Edge List
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)
Undirected Graph
Bipartite Graph
Complete Graph
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
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?
Minimum Spanning Tree
Graph Coloring
Shortest Path
Community Detection
Which of the following algorithms can handle negative weights in a weighted graph without issues?
Bellman-Ford Algorithm
Prim's Algorithm
Dijkstra's Algorithm
Breadth-First Search (BFS)
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?
Depth-First Search (DFS)
What is the purpose of topological sorting in directed acyclic graphs (DAGs)?
Finding the shortest path between any two vertices.
Finding a linear ordering of vertices where for every edge (u, v), u comes before v.
Determining if the graph has a Hamiltonian cycle.
Calculating the minimum spanning tree of the graph.