Which of the following algorithms can handle negative weights in a weighted graph without issues?
Dijkstra's Algorithm
Breadth-First Search (BFS)
Bellman-Ford Algorithm
Prim's Algorithm
In an undirected graph represented using an incidence matrix, what would be the sum of the values in a single column?
2
1
0
V (number of vertices)
What is the purpose of topological sorting in directed acyclic graphs (DAGs)?
Finding the shortest path between any two vertices.
Calculating the minimum spanning tree of the graph.
Finding a linear ordering of vertices where for every edge (u, v), u comes before v.
Determining if the graph has a Hamiltonian cycle.
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
Incidence Matrix
Adjacency Matrix
Edge List
Which graph representation is particularly well-suited for representing graphs with parallel edges (multiple edges between the same pair of vertices)?
None of the above
An incidence matrix for a graph with 'V' vertices and 'E' edges will have dimensions:
V x E
E x E
Depends on the graph's connectivity
V x V
If a graph has negative weight cycles, what can we say about finding the shortest path?
Dijkstra's algorithm will always find the correct shortest path.
Bellman-Ford algorithm will take significantly longer to find the shortest path.
The shortest path is undefined as we can keep traversing the cycle, decreasing the path length infinitely.
The graph must be undirected to have negative weight cycles.
Which of the following algorithms is typically used for topological sorting?
Dijkstra's algorithm
Kruskal's algorithm
Prim's algorithm
Depth-First Search (DFS)
Which representation would be most suitable for a graph where you primarily need to iterate over all edges efficiently?
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)
Heap
Queue
Stack