In an undirected graph represented using an incidence matrix, what would be the sum of the values in a single column?
2
V (number of vertices)
0
1
What is the purpose of topological sorting in directed acyclic graphs (DAGs)?
Finding a linear ordering of vertices where for every edge (u, v), u comes before v.
Calculating the minimum spanning tree of the graph.
Finding the shortest path between any two vertices.
Determining if the graph has a Hamiltonian cycle.
In the context of Kruskal's algorithm, what data structure is commonly used to efficiently detect cycles during edge addition?
Queue
Stack
Disjoint Union Set (Union-Find)
Heap
Which graph traversal algorithm is most efficient for detecting cycles in a directed graph, crucial for identifying dependencies in a project management system?
Prim's Algorithm
Depth-First Search (DFS)
Breadth-First Search (BFS)
Kruskal's Algorithm
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?
Complete Graph
Undirected Graph
Bipartite Graph
Directed Acyclic Graph (DAG)
Which of the following situations would make Bellman-Ford algorithm a better choice than Dijkstra's algorithm?
Finding the shortest path in a tree
Finding the shortest path in a graph with negative edge weights
Finding the shortest path in an unweighted graph
Finding the shortest path in a dense graph
Which algorithm efficiently calculates the shortest paths between all pairs of nodes in a weighted graph, useful for analyzing network connectivity in social networks?
Floyd-Warshall Algorithm
Dijkstra's Algorithm
Bellman-Ford Algorithm
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?
Incidence Matrix
Adjacency Matrix
Adjacency List
Edge List
Which of the following algorithms is typically used for topological sorting?
Dijkstra's algorithm
Kruskal's algorithm
Prim's algorithm
Which of the following algorithms can handle negative weights in a weighted graph without issues?