What is the main purpose of performing a topological sort on a directed graph?
Think about how tasks with dependencies should be arranged.
Topological sorting arranges nodes in a linear order respecting the direction of edges, so that each node appears before all nodes it points to. This is useful for scheduling tasks with dependencies.
Which condition must a directed graph satisfy to have a valid topological ordering?
Think about what happens if there is a cycle in the graph.
A graph must be a Directed Acyclic Graph (DAG) to have a valid topological ordering. Cycles prevent a linear ordering that respects all edges.
Given the directed graph with edges: A → B, A → C, B → D, C → D, which of the following is a valid topological order?
Remember that a node must come before all nodes it points to.
In the graph, A points to B and C, so A must come before B and C. Both B and C point to D, so B and C must come before D. The order [A, B, C, D] respects all these constraints.
What does it indicate if a topological sort algorithm cannot include all nodes of a directed graph in its ordering?
Think about why some nodes might never get placed in the order.
If a topological sort cannot include all nodes, it means some nodes are part of a cycle. Cycles prevent nodes from having zero incoming edges, so they never get added to the order.
Consider a directed acyclic graph with nodes A, B, C, and edges A → B and A → C only. How many different valid topological orders exist for this graph?
Think about the positions of B and C relative to each other.
Since A must come before B and C, A is fixed first. B and C have no order between them, so they can appear in either order after A. Thus, there are 2 valid orders: [A, B, C] and [A, C, B].