Home » Questions » Computers [ Ask a new question ]

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

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

"Closed. This question needs to be more focused. It is not currently accepting answers.

Want to improve this question? Update the question so it focuses on one problem only by editing this post.

Closed 8 years ago.

Improve this 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"

Asked by: Guest | Views: 115
Total answers/comments: 4
Guest [Entry]

"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:

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."
Guest [Entry]

"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."
Guest [Entry]

Just about every problem can be re-written in terms of graph theory. I'm not kidding, look at any book on NP complete problems, there are some pretty wacky problems that get turned into graph theory because we have good tools for working with graphs...
Guest [Entry]

The Algorithm Design Manual contains some interesting case studies with creative use of graphs. Despite its name, the book is very readable and even entertaining at times.