التطبيقات: الاعتماديات والدورات

Written Explanation

Dependencies are a directed graph

Suppose an application needs a web library and a database library, and both of those need a core library. Write each "needs" as an edge from the dependent to what it depends on:

app -> web
app -> db
web -> core
db  -> core

In code this is the directed adjacency list from Lesson 2. We will use a helper that records "a needs b" and registers both nodes:

static Map<String, List<String>> g = new LinkedHashMap<>();

static void needs(String a, String b) {
    g.computeIfAbsent(a, k -> new ArrayList<>()).add(b);
    g.computeIfAbsent(b, k -> new ArrayList<>());
}

The map is a LinkedHashMap so that loops over its keys are in the order we added them, which keeps the output of the examples predictable.

A valid build order puts every library after the libraries it needs. For this graph, core, then web and db in either order, then app.

Why a cycle is a dead end

Add one more fact: core -> app, "core needs app". Now app needs web, web needs core, and core needs app. Starting anywhere, each library waits for another that waits for it. No library can go first, so no valid order exists. A cycle in a dependency graph means the build or startup cannot be done. The only fix is to change the design (usually by extracting the shared piece into a new library that the others both need).

Detecting a cycle with DFS

DFS walks along a path. A directed cycle means that, somewhere along the current path, an edge leads back to a node that is still on the path. So we track two sets:

• onPath: the nodes we have entered and not yet finished. These are the nodes of the current recursion path.
• done: nodes whose exploration has completely finished.

static boolean visit(String n, Set<String> done, Set<String> onPath) {
    if (onPath.contains(n)) return true;    // back to a node on our path: cycle
    if (done.contains(n)) return false;     // already fully explored: safe
    onPath.add(n);
    for (String m : g.get(n)) {
        if (visit(m, done, onPath)) return true;
    }
    onPath.remove(n);
    done.add(n);
    return false;
}

static boolean hasCycle() {
    Set<String> done = new HashSet<>();
    Set<String> onPath = new HashSet<>();
    for (String n : g.keySet()) {
        if (visit(n, done, onPath)) return true;
    }
    return false;
}

hasCycle loops over every node because the graph may have several pieces, and a cycle can hide in a piece you have not visited yet. The same idea appears in algorithm references in the language of three colors: white for unvisited, gray for "entered but not finished" (on the current path), and black for finished. Reaching a gray node signals a cycle. onPath is gray and done is black.

Why "visited" alone is not enough

Beginners often detect a cycle with the plain visited set from the last lesson: "if I reach a node I have already seen, there is a cycle". That is wrong for directed graphs. In our dependency graph, web and db both need core. DFS reaches core through web, finishes it, then reaches it again through db. The second arrival is not a cycle: core is finished, not on the path. A cycle needs the edge to return to a node still on the path. This is why two sets are needed.

A build order from DFS

DFS can also produce the build order. The idea: add a node to the output list when its exploration is finished, that is after all the things it needs have been added.

static List<String> buildOrder() {
    List<String> out = new ArrayList<>();
    Set<String> seen = new HashSet<>();
    for (String n : g.keySet()) post(n, seen, out);
    return out;
}

static void post(String n, Set<String> seen, List<String> out) {
    if (!seen.add(n)) return;
    for (String m : g.get(n)) post(m, seen, out);
    out.add(n);
}

Because a library is added only after all its dependencies were added, every dependency appears before its dependents. This is a standard use of DFS: ordering vertices by finish time yields a topological order, which exists only when the graph has no cycles. The code above assumes no cycle, so run hasCycle first.

Networks and routes: back to BFS

Not every graph application needs cycles. In a network of machines, or a route map, the common question is "how many hops?" That is BFS, which you know. The two tools split the work:

• DFS: cycles, build order, "can I get there at all".
• BFS: fewest hops, "what is within k steps".

For a service graph, both appear together: DFS to check that startup order is possible, BFS to measure how far a failure can spread.