这是一道 Google 图算法面试题。题目本质是：把“顺方向免费、反方向代价为 1”抽象成带权图，然后求从起点到终点的最小总代价。

CsoaHelp 提供海外大厂算法面试实时辅助服务，适合准备 Google、Meta、Amazon、TikTok、Stripe 等公司的候选人。面试过程中，我们可以通过文本形式帮助你快速理解题意、判断算法方向、组织解题思路和复杂度表达。

Problem

You are given a graph with N nodes numbered from 0 to N - 1.

You are also given a list of directed edges:

edges = [[u1, v1], [u2, v2], ...]

Each edge u -> v can be traveled in both directions.

Traveling in the original direction costs 0.

Traveling in the opposite direction costs 1.

Given start and end, return the minimum total cost needed to travel from start to end.

Example

N = 5
edges = [[0, 1], [2, 1], [2, 3], [4, 3]]
start = 0
end = 4

The original directions are:

0 -> 1
2 -> 1
2 -> 3
4 -> 3

One valid path from 0 to 4 is:

0 -> 1 -> 2 -> 3 -> 4

The costs are:

0 -> 1: 0
1 -> 2: 1
2 -> 3: 0
3 -> 4: 1

So the output is:

2

思路

这道题的关键是建图。

对于每条原始边：

u -> v

可以转换成两条带权边：

u -> v, cost = 0
v -> u, cost = 1

也就是说，沿着原方向走不产生 violation，反方向走会产生一次 violation。

转换之后，题目就变成了：在一个边权只有 0 和 1 的图中，求 start 到 end 的最短路径。

这种题最适合用 0-1 BFS。

为什么用 0-1 BFS

普通 BFS 不适合，因为普通 BFS 默认每条边的代价都相同，只能求最少经过几条边。

这道题要求的是最少 violation 次数，不是最少边数。

Dijkstra 可以做，但因为边权只有 0 和 1，使用 0-1 BFS 更合适。

在 0-1 BFS 中：

cost = 0 的边：加入队首
cost = 1 的边：加入队尾

这样可以保证每次优先处理当前代价更小的路径。

示例解释

输入：

edges = [[0, 1], [2, 1], [2, 3], [4, 3]]

可以理解成：

0 -> 1, cost = 0
1 -> 0, cost = 1

2 -> 1, cost = 0
1 -> 2, cost = 1

2 -> 3, cost = 0
3 -> 2, cost = 1

4 -> 3, cost = 0
3 -> 4, cost = 1

从 0 到 4 的路径：

0 -> 1 -> 2 -> 3 -> 4

对应代价：

0 -> 1: cost = 0
1 -> 2: cost = 1
2 -> 3: cost = 0
3 -> 4: cost = 1

所以最小总代价是：

2

面试中容易错的地方

第一，很多人会直接用普通 BFS。这样只能得到最短边数路径，不能保证 violation 最少。

第二，有人会把输入当成普通有向图，只允许从 u 走到 v，忽略了题目中“每条边可以双向走”的条件。

第三，建图时只加入一条边。正确做法是每条输入边都要加入两条边：原方向代价为 0，反方向代价为 1。

复杂度

假设有 N 个节点，M 条边。

时间复杂度：

O(N + M)

空间复杂度：

O(N + M)

面试官关注点

这道 Google 面试题主要考察候选人能不能把业务描述快速抽象成图模型。

真正的重点不是写 BFS 模板，而是看出：

顺方向走 = cost 0
反方向走 = cost 1

然后进一步识别出这是一个典型的 0-1 BFS 问题。

在面试中，能清楚解释建图方式、为什么不能用普通 BFS、为什么 0-1 BFS 比 Dijkstra 更适合，会比单纯写出代码更重要。

CsoaHelp 的面试辅助服务可以在真实面试中帮助你快速判断题型、梳理解题路径，并通过文本形式实时辅助你完成题意理解、算法选择、复杂度分析和 follow-up 应对。

我们也有代面试，面试辅助，OA代写等服务助您早日上岸~