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?
Edge List
Incidence Matrix
Adjacency List
Adjacency Matrix
What is the primary application of topological sorting in computer science?
Finding the minimum spanning tree of a graph
Scheduling tasks with dependencies
Detecting cycles in a graph
Finding the shortest path between two nodes
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.
The graph must be undirected to have negative weight cycles.
The shortest path is undefined as we can keep traversing the cycle, decreasing the path length infinitely.
Bellman-Ford algorithm will take significantly longer to find the shortest path.
Topological sorting is possible for which type of graph?
Directed acyclic graphs (DAGs)
Weighted graphs
Complete graphs
Undirected graphs
Which algorithm is more suitable for finding the shortest path in a graph with negative edge weights?
Dijkstra's algorithm
Kruskal's algorithm
Bellman-Ford algorithm
Prim's algorithm
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.
Standard shortest path algorithms are not designed to handle cycles.
The presence of cycles makes the graph too complex for efficient shortest path algorithms.
The shortest path might involve traversing a cycle repeatedly to minimize the total weight.
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
Which of the following is NOT a characteristic of a minimum spanning tree (MST)?
It is a tree (acyclic)
It may contain cycles
It connects all vertices in the graph
It has the minimum total edge weight
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?
Breadth-First Search (BFS)
Dijkstra's Algorithm
Bellman-Ford Algorithm
Depth-First Search (DFS)
Which representation would be most suitable for a graph where you primarily need to iterate over all edges efficiently?