VietMX Staff asked 3 years ago
Whenever someone gives you a problem, think graphs. They are the most fundamental and flexible way of representing any kind of a relationship.
- 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.
- Project management related problems. 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, find the event that is the most crucial (that is would free a lot of other projects), find the duration needed to solve the total project (path problem), etc.
- Your source code is tree structured, and a tree is a type of graph. Whenever you hear people talking about an AST (Abstract Syntax Tree), they’re talking about a kind of graph.
- State machines are graphs. State machines are used in network protocols, regular expressions, games, and all kinds of other fields.
- Program optimization algorithms that compilers use are based on graphs (e.g., figure out call graph, flow control, lots of static analysis).
- Optical character recognition. Picture a page of text scanned at an angle, with some noise in the image, where you must find the space between lines of text.
- Dependence graphs. Graphs can be used to represent dependences or precedences among items. Such graphs are often used in large projects in laying out what components rely on other components and used to minimize the total time or cost to completion while abiding by the dependences.
