In an undirected graph represented using an incidence matrix, what would be the sum of the values in a single column?
0
V (number of vertices)
2
1
What is the primary application of topological sorting in computer science?
Scheduling tasks with dependencies
Finding the shortest path between two nodes
Detecting cycles in a graph
Finding the minimum spanning tree of a graph
Which of the following algorithms can handle negative weights in a weighted graph without issues?
Prim's Algorithm
Bellman-Ford Algorithm
Breadth-First Search (BFS)
Dijkstra's Algorithm
Which graph representation is particularly well-suited for representing graphs with parallel edges (multiple edges between the same pair of vertices)?
Edge List
Incidence Matrix
None of the above
Adjacency Matrix
Which of the following situations would make Bellman-Ford algorithm a better choice than Dijkstra's algorithm?
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
Finding the shortest path in a tree
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
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 connects all vertices in the graph
It may contain cycles
Which algorithm is more suitable for finding the shortest path in a graph with negative edge weights?
Bellman-Ford algorithm
Kruskal's algorithm
Dijkstra's algorithm
Prim's algorithm
In a graph with a large number of vertices but relatively few edges (sparse graph), which representation would be most space-efficient?
Prim's algorithm for finding the MST starts with an arbitrary vertex. Does the choice of the starting vertex affect the final MST found?
Yes, different starting vertices may lead to different MSTs
No, the MST is unique for a given graph