Connected components and topological sort
Two applications of traversals: labelling the connected components of an undirected graph, and ordering the vertices of a directed acyclic graph (Kahn by in-degrees, or reverse finish order of a depth-first search); a circuit makes the sort impossible.
- 28 cards
- 6 topics
- Free
The outline, topic by topic
Each topic is weighted the way the exam weighs it.
- Concepts
- Questions
- Sort and link
- The numbers
- Scenarios
- Understand
A few cards from the deck
Connected component: what is it?
Show the answer
A maximal set of vertices of an undirected graph, all linked to each other by paths.
A traversal from a vertex discovers exactly its component. A graph is connected when it has just one.
Seven modules: A and B with no prerequisite; C requires A; D requires A and B; E requires C and D; F requires B; G requires E and F. Which order is a topological sort?
- A B D C F E G
- A C D E B F G
- F B A D C E G
- A B C E D F G
Show the answer
A B D C F E G
In the right answer, each module comes after its prerequisites. In A C D E B F G, D comes before B; in F B A D C E G, F comes before B; in A B C E D F G, E comes before D.
To label connected components, a traversal is started from each … vertex: each start discovers ….
Show the answer
To label connected components, a traversal is started from each not yet visited vertex: each start discovers one whole component.
The number of starts is the number of components. The traversal can be breadth-first or depth-first, the result is the same.
Directed acyclic graph: what is it?
Show the answer
A directed graph in which no path comes back to its starting point.
It is the natural shape of dependencies (prerequisites, tasks, files to compile). It is abbreviated DAG.