How is graph theory applied to programming?

Question

Counts

I constantly see that in order to correctly understand the basics of programming, you need to know a bunch of sections of discrete mathematics, including the above-mentioned graph theory. Please explain to a beginner why you need to study it and how and where it is applied.

Answer 1

First of all, I want to note that the lion's share of programmers do not directly deal with theory and mathematics. It is possible to be a successful professional without ever writing your own implementation of Dijkstra's algorithm, or even having an idea of ​​how it works. But still, it is worth at least superficially getting acquainted with graphs, since this is one of the main data structures. The scope of their application is very extensive, often these are algorithms for finding solutions - the shortest path along the route, the effective location of tracks on the diagram, the winning game strategy, etc. A real life example of using graphs is the sea-of-nodes of the JIT compiler.JIT compilerbuilds a data flow graph and a flow graph, in which nodes are program instructions, and edges are the order in which instructions are called and the order in which data is assigned to variables, then looks for ways to optimize this graph and generates a binary code using the optimized graph.

int average(int a, int b) {
  return (a + b) / 2;
}

Answer 2

Well, for example, to answer correctly in an interview. :)
Many companies ask this at least at some basic level.
In general, sometimes they ask for classic puzzles from Computer Science.
Well, or to successfully perform at the Olympics - there it is all the time.
An example that would be closest to what most developers encounter every day is a dependency builder (package manager, bundler or whatever you want to call it) before compiling/running.
The so-called DAG is being built - https://en.wikipedia.org/wiki/Directed_acyclic_graph so that there are no loops.

Answer 3

https://habr.com/post/65367/ 30 seconds of searching for "graph theory in programming". There is a brief application.

Answer 4

A simple example that comes to my mind is resolving dependencies, say, when an application is initialized. So, when components depend on each other, and they need to be loaded in the correct order, then topological sorting is necessary.