Google 27 Intern SDE 过经：无向无权图，Alice 和 Bob 到终点的最少共用边

面试概况

2027 年的 Summer Intern，Google 已经发了一波 OA，VO 进度快的已经面完了。今天讲讲遇到的原题。

面试官是白人，出了一道考无向无权图的题，很难。尤其是图论还没复习到这个点的同学，遇到基本就跪了。面试里没让写完，但需要讲得大差不差。

题目

给定一个无向无权图：Alice 的起点是 A，Bob 的起点是 B，两个人的目的地都是 D。

两人各自选一条路径走到 D，把两条路径经过的所有边放进一个集合，求这个集合大小的最小值。

思路：三次 BFS + 枚举汇合点

关键观察：最优方案里，两条路径一定会在某个点 X 汇合，之后一起走到 D，共用的这段边只算一次。

• Alice：A → X
• Bob：B → X
• 两人一起：X → D

所以答案是：

min over X of dist(A, X) + dist(B, X) + dist(X, D)

X 可以是 A、B 或 D 本身，这就涵盖了「两人不共用任何边」的情况（X = D）。

图是无权的，所以分别从 A、B、D 跑三次 BFS 得到距离数组，再枚举所有 X 就行。时间 O(V + E)，空间 O(V)。

from collections import deque

def bfs(adj, src):
    dist = {src: 0}
    q = deque([src])
    while q:
        u = q.popleft()
        for v in adj[u]:
            if v not in dist:
                dist[v] = dist[u] + 1
                q.append(v)
    return dist

def min_union_edges(n, edges, a, b, d):
    adj = [[] for _ in range(n)]
    for u, v in edges:
        adj[u].append(v)
        adj[v].append(u)
    da, db, dd = bfs(adj, a), bfs(adj, b), bfs(adj, d)
    best = min(
        (da[x] + db[x] + dd[x] for x in range(n) if x in da and x in db and x in dd),
        default=-1,
    )
    return best   # -1 表示有人到不了 D

讲题时的要点

• 先 Clarify：图是否连通？A、B、D 是否可能重合？到不了 D 时返回什么？
• 讲清楚「为什么最优解一定是 Y 字形汇合」：两条路径分开后再相交没有好处，可以把后面的路段合并成同一条。
• 这其实是 3 个点的 Steiner Tree 问题，在无权图上可以直接枚举中心点求解。

后面还有 Follow-up，这里不再列举。