Think together · Start with a story
The robot draws a tree, then adds a line between two branches. The girl realizes that a loop may now be possible.
Break down the process
- Nodes and edgesMake a graph
- Check connectionsAre all nodes reachable?
- Check for cyclesCan a path loop back?
A tree is a special graph: it is connected and has no cycles. A general graph does not have to meet those two rules.
01Are trees and graphs completely different things?
No. A tree is a special case of a graph with additional properties.
02How can a general graph be more complex than a tree?
A general graph may contain cycles or may be disconnected. A tree must be connected and cycle-free.
03Does a tree always have a root?
From a pure graph-theory point of view, an unrooted tree does not have to specify a root.
In programs and algorithms, we often choose one node as the root so that we can describe parents, children, depth, and subtrees.
04Why is there only one simple path between any two tree nodes?
If there were two different simple paths between two nodes, combining them would form a cycle, which contradicts the tree's “no cycles” property.
05Do graph nodes have parents and children?
A general graph does not have a natural parent-child relationship.
We may define “parent nodes” in a search, a spanning tree, or a particular directed structure.
06Why can DFS / BFS traverse both trees and graphs?
Both are connected structures made of nodes and edges.
DFS and BFS both visit nodes by following edges; they differ in the order of visits.
A graph may have cycles, so graph traversal usually needs a visited record to avoid revisiting nodes.
What you have learned
- A tree can be seen as a special graph.
- A tree must be connected and cycle-free.
- A general graph may contain cycles or be disconnected.
- The root of a tree is often chosen as a starting point for viewing it.
- A general graph has no natural parent-child relationship.
- DFS and BFS work for both trees and graphs, but watch for repeated visits in a graph.
Next: How Do You Choose the Right Data Structure for a Problem?
Your turn to try
Can two disconnected nodes with no cycle be called an undirected tree?
Ready? Open to see the explanation
No, because the structure is disconnected. A tree must be both connected and cycle-free.