Practice question · Multiple choice
A social network is a graph, a filesystem is a tree, and a tree is a graph. What does the extra restriction buy the filesystem?
Hints
- Ask what a cycle would mean in a filesystem, and what it would do to a recursive delete.
- How many paths exist between two nodes in a tree?
Show the answer
A. Guarantees that simplify algorithms: one path, no cycles, n−1 edges
Why
No cycles means recursive traversal terminates without tracking visits, and a unique path means one canonical location per file. Symbolic links break the guarantee and reintroduce exactly those problems, which is why find has loop detection and why the restriction is worth having.
Practise Graphs and Trees
The app has 4 more questions on this lesson, and keeps your place in the course. Computer Science I is free to start.
More questions on Graphs and Trees
- Select every statement that must be true of any tree with n vertices.
- Sort each term or description by what it is a property of.
- The handshaking lemma says the degrees of all vertices sum to twice the number of edges. Why must the total…
- A connected graph with 8 vertices and 8 edges must contain a cycle.