How does make/scons manage dependency graph and figure out which file need to be recompiled?
I do not how SCons works in details so I will focus on Make. I am not sure anyone really knows what is the algorithm Make uses because it is so complicated and error-prone, it is loosely described in the manual . But at the high-level, Make takes as input rules as described in the manual of form $$target: dependencies$$
Furthermore, when running make one has to specify one or more targets to build (if you give no target, it builds "default"): make target1 target2 ...
This essentially describes a graph and a set of nodes to be built.
In terms of graph, one could say that Make performs a depth-first search1 from those to-be-built nodes, but this hides many details like PHONY/FORCE rules, intermediate files, secondary-expansions, the fact that a file can actually be built twice, parallel make and more features. Make considers dependency loops to be an error and will break them arbitrarily (and display a warning).

In fact, one could say that Make performs two different (but related) functions: building the dependency graph and rebuilding everything according to the graph. The difference between Make and other tools is that other tools mostly take as input a complete description of the graph. On the other hand, Make provides a whole range of tool to dynamically create the graph. This creates a lot of confusion because you can literally have a 5 lines Makefile that will generate a graph with thousands of nodes and runs all kinds of tools to figure out the dependencies. SCons, CMake and friends will usually let other tools do this work for them and focus on just rebuilding everything. Also Make's approach makes it somewhat inefficient because just building the graph may involve running some tools, and not just reading the Makefiles.

1The order in which Make builds file is completely unspecified, except for the fact that it is a topological order (and even that is not entirely true because Make may actually build some targets more than once)