What problems can be solved, or tackled more easily, using graphs and trees? [closed]

Question

What are the most common problems that can be solved with both these data structures?

It would be good for me to have also recommendations on books that:

• Implement the structures
• Implement and explain the reasoning of the algorithms that use them

Answer 1

The first thing I think about when I read this question is: what types of things use graphs/trees? and then I think backwards to how I could use them.

For example, take two common uses of a tree:

• The DOM
• File systems

The DOM, and XML for that matter, resemble tree structures.

It makes sense, too. It makes sense because of how this data needs to be arranged. A file system, too. On a UNIX system there's a root node, and branching down below. When you mount a new device, you're attaching it onto the tree.

You should also be asking yourself: does the data fall into this type of structure? Create data structures that make sense to the problem and the rest will follow.

As far as being easier, I think thats relative. Are you good with recursive functions to traverse a tree/graph? What if you need to balance the tree?

Think about a program that solves a word search puzzle. You could map out all the letters of the word search into a graph and check surrounding nodes to see if that string is matching any of the words. But couldn't you just do the same with with a single array? All you really need to do is move an index to check letters to the left and right, and by the width to check above and below letters. Solving this problem with a graph isn't difficult, but it can create a lot of extra work and difficulty if you're not comfortable with using them - of course that shouldn't discourage you from doing it, especially if you are learning about them.

I hope that helps you think about these structures. As for a book recommendation, I'd have to go with Introduction to Algorithms.

Answer 2

Circuit diagrams.

Compilation (Directed Acyclic graphs)

Maps. Very compact as graphs.

Network flow problems.

Decision trees for expert systems (sic)

Fishbone diagrams for fault finding, process improvment, safety analysis. For bonus points, implement your error recovery code as objects that are the fishbone diagram.