3 ms·
I thought it was odd to treat trees as graphs. They are, but they're different enough that you don't use the same tools on them.
by twic 9y ago
I thought it was odd to treat trees as graphs. They are, but they're different enough that you don't use the same tools on them.
- coldtea 9y agoHmm? Trees are just acyclic and connected graphs in graph theory. Why wouldn't you use the same tools that apply to graphs in general?
- yorwba 9y agoAcyclicity usually makes it possible to come up with a specialized algorithm that works better on trees than an algorithm that needs to handle all possible graphs. For example, many NP-complete problems become fixed-parameter tractable if you fix the tree-width of the graph (essentially, how many nodes you have to bag together until the graph looks like a tree). Because of this, algorithms on trees are often very different from general graph algorithms in practice. You could use the same tools, but it would be unnecessarily slow and/or complex.