把京东面试官电话当成送快递的了，让他帮我放门口，哈哈 太尴尬了

我先假装咱俩在工位边上聊天哈，不整那些特别官方的口吻，就当是在聊题。

一、先把“有向图访问计数”讲人话

你可以把这个题脑补成「任务依赖」的场景：

有一堆任务，用 1…N 编号。每条有向边 u -> v 表示：做 v 之前必须先做 u。 现在我们从若干个起点任务出发（比如只有 1 号，或者有多个源头），每走一条合法路径都算一次「访问」，问：每个点一共会被多少条路径访问到？

举个特别小的例子：

• 边：1 → 2，1 → 3，2 → 4，3 → 4
• 从 1 出发 所有路径是：1-2-4 和 1-3-4

那访问计数就是：

• 1：1（只有起点那一条路径）
• 2：1（只有 1-2-4 里经过一次）
• 3：1
• 4：2（两条路径都走到它）

这个本质上就是：有向无环图（DAG）上的路径计数问题。

二、暴力 DFS 为啥不香

最直接的想法就是： 从起点 DFS，走到一个点就给它计数 +1，走完所有路径。

问题是，有向图的路径数可能是指数级的：

• 你看着只有一两千个点、一两万条边
• 但路径数可能是「2 的多少次方」这种夸张的
• DFS 把每条路径都走一遍，时间直接爆炸，线上肯定扛不住

而且很多子路径是重复访问的，比如 1→2→4 和 3→2→4，走到 2 后面那一截其实是一样的，暴力 DFS 每次都重新算一遍，浪费。

所以我们得利用一个关键信息：图是有向无环的（DAG），没有环就可以「自底向上」做动态规划。

三、DAG 上最顺手的思路：拓扑排序 + DP

既然没有环，就一定能排出一个拓扑序，比如：1, 2, 3, 4, ...，满足所有的边都从前往后。

然后我们搞一个数组 dp[i] 表示「到达 i 的路径数量」。

思路就变得很自然：

• 起点 s：dp[s] = 1（从自己到自己有一条“空路径”）

• 按拓扑序从前往后扫：

• 对每条边 u -> v，把到达 u 的路径数，全部“传递”给 v
• 公式就是：dp[v] += dp[u]

这样，每条路径只在“边”这一步被算一次，时间复杂度就是 O(N + M)，非常稳。

四、用 Java 写一个完整一点的实现

下面写个比较通用的版本：

• 节点从 1 到 n
• 边用 List<int[]> edges 表示，每个 int[2] 是 {u, v}
• 支持多个起点，比如很多源任务一起触发

import java.util.*;

publicclassDirectedGraphVisitCounter{

/**
     * n: 节点个数，默认编号 1..n
     * edges: 有向边列表，每个元素是 {u, v}
     * sources: 所有起点节点
     * 返回：每个节点被“路径访问”的次数，下标 1..n 有效
     */
publicstaticlong[] countVisits(int n, List<int[]> edges, List<Integer> sources) {
// 1. 建邻接表 & 入度表
        List<List<Integer>> graph = new ArrayList<>();
for (int i = 0; i <= n; i++) {
            graph.add(new ArrayList<>());
        }
int[] indegree = newint[n + 1];

for (int[] e : edges) {
int u = e[0];
int v = e[1];
            graph.get(u).add(v);
            indegree[v]++;
        }

// 2. 拓扑排序（Kahn 算法）
        Queue<Integer> queue = new ArrayDeque<>();
// 初始访问计数数组，用 long 防止溢出
long[] dp = newlong[n + 1];

// 多个起点：它们的 dp 初始为 1，并且直接入队
for (int s : sources) {
            dp[s] = 1;
if (indegree[s] == 0) {
                queue.offer(s);
            }
        }

// 还有一些非起点、但入度为 0 的点，也要入队（否则 topo 不完整）
for (int i = 1; i <= n; i++) {
if (indegree[i] == 0 && dp[i] == 0) {
                queue.offer(i);
            }
        }

int visitedCount = 0;

while (!queue.isEmpty()) {
int u = queue.poll();
            visitedCount++;

for (int v : graph.get(u)) {
// 把到达 u 的路径数，加到 v 上
                dp[v] += dp[u];

// 维护入度，做拓扑排序
                indegree[v]--;
if (indegree[v] == 0) {
                    queue.offer(v);
                }
            }
        }

// 简单做一下环检测：如果没处理完所有点，说明图里有环
if (visitedCount != n) {
thrownew IllegalArgumentException("图中存在环，无法用这种方式做访问计数");
        }

return dp;
    }

// 简单测一下
publicstaticvoidmain(String[] args){
int n = 4;
        List<int[]> edges = new ArrayList<>();
        edges.add(newint[]{1, 2});
        edges.add(newint[]{1, 3});
        edges.add(newint[]{2, 4});
        edges.add(newint[]{3, 4});

        List<Integer> sources = Collections.singletonList(1);

long[] result = countVisits(n, edges, sources);
for (int i = 1; i <= n; i++) {
            System.out.println("node " + i + " -> " + result[i]);
        }
// 预期：
// node1 -> 1
// node2 -> 1
// node3 -> 1
// node4 -> 2
    }
}

这个实现你可以直接丢到本地跑跑，逻辑就几步：

1. 图建成邻接表，顺便算每个点的入度
2. Kahn 拓扑排序，队列里永远放「当前入度为 0」的点
3. 每弹出一个点 u，把 dp[u] 往所有出边邻居 v 上传递
4. 最后 dp[i] 就是从所有起点出发，到 i 的路径数量

五、如果图里有环怎么办

上面代码里我刻意加了个 visitedCount != n 的判断：

• DAG 是没有环的，所以 Kahn 拓扑排序一定能把所有点都处理完
• 如果剩下点没处理到，说明存在环，这种情况「路径数量」就可能是无限的
• 一般这种题会直接限制「图是 DAG」，或者你在业务里发现有环就当配置错了，直接报错

要真想在有环的图上做“访问计数”，那就不是这道题的范畴了，要么：

• 做强连通分量缩点，把环缩成一个超级点，再在 DAG 上算
• 要么把问题从「路径条数」改成「可达性」之类的

这个就有点重了，一般面试 / 日常开发里，上面那版 DAG + 拓扑 DP 就够用了。

六、最后随口叨两句小细节

• 计数用 long，别用 int，路径数累一累很容易爆 int
• 多个起点就都把 dp[start] = 1，别忘了
• 如果节点编号不是 1..n，而是字符串 ID，那就外面套一层 Map<String, Integer> 做映射

大概就这样，核心思路就一句话：有向无环图上想算节点的“访问次数”，最稳的套路就是「拓扑排序 + 动态规划」。

-END-

我为大家打造了一份RPA教程，完全免费：songshuhezi.com/rpa.html