Tree
A tree is a specific type of connected graph.
- It is acyclic (no cycles) and undirected (though we sometimes think of it as directed when we choose a root).
- A tree has exactly one path between any two nodes.
- In a tree with n nodes, there are exactly n-1 edges.
DAG
A DAG is a Directed Acyclic Graph.
- It is directed and has no cycles.
- Unlike a tree, a DAG can have multiple paths between nodes.
- It is not necessarily connected (but it can be).
- It doesn’t have the strict hierarchy of trees, and nodes can have multiple incoming and outgoing edges.
Example of a DAG that is not a tree:
n = 4, edges = [[0, 1], [0, 2], [1, 2], [2, 3]]
This DAG looks like:
0
/ \
1 → 2 → 3
Why this DAG is not a tree:
- Multiple paths: In this DAG, there are two paths from 0 to 2:
- Direct path: 0 → 2
- Indirect path: 0 → 1 → 2
- This violates the tree property of having exactly one unique path between any two nodes.
- More edges than a tree: In a tree with 4 nodes, there should only be 3 edges (n-1 edges). However, this DAG has 4 edges, indicating that it’s more connected than a tree.
- Not a strict hierarchy: In this DAG, node 2 has two incoming edges, one from 0 and one from 1, meaning it has multiple parents. In a tree, every node except the root has exactly one parent, so a node having multiple parents is not allowed in a tree.