Topological sorting is possible for which type of graph?
Undirected graphs
Directed acyclic graphs (DAGs)
Complete graphs
Weighted graphs
Which representation would be most suitable for a graph where you primarily need to iterate over all edges efficiently?
Adjacency Matrix
Adjacency List
Edge List
Incidence Matrix
Why are negative weights problematic for some shortest path algorithms?
All of the above
Algorithms like Dijkstra's rely on the principle that shorter paths are always discovered before longer ones.
Negative weights can lead to cycles where the total weight decreases with each iteration, confusing the algorithm.
These algorithms assume that adding an edge to a path always increases its total weight.
Which of the following is NOT a characteristic of a minimum spanning tree (MST)?
It has the minimum total edge weight
It is a tree (acyclic)
It may contain cycles
It connects all vertices in the graph
In a graph with a large number of vertices but relatively few edges (sparse graph), which representation would be most space-efficient?
None of the above
How does the concept of 'distance' in a weighted graph differ from that in an unweighted graph?
In a weighted graph, 'distance' represents the sum of edge weights along a path, while in an unweighted graph, it's the number of edges.
In weighted graphs, 'distance' always refers to geographical distance, while in unweighted graphs, it can represent abstract relationships.
Distance is only defined for unweighted graphs.
There is no difference; 'distance' has the same meaning in both types of graphs.
What value is stored in the cells of an incidence matrix to represent that a vertex is NOT incident to an edge?
-1
0
1
Infinity
Which algorithm efficiently calculates the shortest paths between all pairs of nodes in a weighted graph, useful for analyzing network connectivity in social networks?
Dijkstra's Algorithm
Bellman-Ford Algorithm
Kruskal's Algorithm
Floyd-Warshall Algorithm
What is the primary distinction between an unweighted graph and a weighted graph?
Unweighted graphs are always undirected, while weighted graphs are always directed.
Unweighted graphs represent connections, while weighted graphs represent connections with associated costs or distances.
Unweighted graphs have a fixed number of vertices, while weighted graphs can have a variable number of vertices.
Unweighted graphs are used for simple relationships, while weighted graphs are used for complex mathematical computations.
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?