What are good examples of problems that graphs can solve better than the alternative? [closed]

Question

After reading Stevey Yegge's Get That Job At Google article, I found this little quote interesting:

Whenever someone gives you a problem, think graphs. They are the most fundamental and flexible way of representing any kind of a relationship, so it's about a 50–50 shot that any interesting design problem has a graph involved in it. Make absolutely sure you can't think of a way to solve it using graphs before moving on to other solution types. This tip is important!

What are some examples of problems that are best represented and/or solved by graph data structures/algorithms?

One example I can think of: navigation units (ala Garmin, TomTom), that supply road directions from your current location to another, utilize graphs and advanced pathing algorithms.

What are some others?

Answer 1

Computer Networks: Graphs model intuitively model computer networks and the Internet. Often nodes will represent end-systems or routers, while edges represent connections between these systems.

Data Structures: Any data structure that makes use of pointers to link data together is making use of a graph of some kind. This includes tree structures and linked lists which are used all the time.

Pathing and Maps: Trying to find shortest or longest paths from some location to a destination makes use of graphs. This can include pathing like you see in an application like Google maps, or calculating paths for AI characters to take in a video game, and many other similar problems.

Constraint Satisfaction: A common problem in AI is to find some goal that satisfies a list of constraints. For example, for a University to set it's course schedules, it needs to make sure that certain courses don't conflict, that a professor isn't teaching two courses at the same time, that the lectures occur during certain timeslots, and so on. Constraint satisfaction problems like this are often modeled and solved using graphs.

Molecules: Graphs can be used to model atoms and molecules for studying their interaction and structure among other things.

Answer 2

I am very very interested in graph theory and ive used it solved so many different kinds of problem. You can solve a lot of Path related problem, matching problem, structure problems using graph.

• Path problems have a lot of applications.

  This was in a career cup's interview question. Say you want to find the longest sum of a sub array. For example, [1, 2, 3, -1] has the longest sum of 6. Model it as a Directed Acyclic Graph (DAG), add a dummy source, dummy destination. Connect each node with an edge which has a weight corresponding to the number. Now use the Longest Path algorithm in the DAG to solve this problem.

  Similarly, Arbitrage problems in financial world or even geometry problems of finding the longest overlapping structure is a similar path problem.

• Some obvious ones would be the network problems (where your network could have computers people, organisation charts, etc).
  You can glean a lot of structural information like

  • which point breaks the graph into two pieces
  • what is the best way to connect them
  • what is the best way to reach one place to another
  • is there a way to reach one place from another, etc.

• I've solved a lot of project management related problems using graphs. A sequence of events can be pictured as a directed graph (if you don't have cycles then thats even better). So, now you can

  • sort the events according to their priority
  • you can find the event that is the most crucial (that is would free a lot of other projects)
  • you can find the duration needed to solve the total project (path problem), etc.

• A lot of matching problems can be solved by graph. For example, if you need to match processors to the work load or match workers to their jobs. In my final exam, I had to match people to tables in restaurants. It follows the same principle (bipartite matching -> network flow algorithms). Its simple yet powerful.

• A special graph, a tree, has numerous applications in the computer science world. For example, in the syntax of a programming language, or in a database indexing structure.

• Most recently, I also used graphs in compiler optimization problems. I am using Morgan's Book, which is teaching me fascinating techniques.

The list really goes on and on and on. Graphs are a beautiful math abstraction for relation. You really can do wonders, if you can model it correctly. And since the graph theory has found so many applications, there are many active researches in the field. And because of numerous researches, we are seeing even more applications which is fuelling back researches.

If you want to get started on graph theory, get a good beginner discrete math book (Rosen comes to my mind), and you can buy books from authors like Fould or Even. CLRS also has good graph algorithms.