找出星型图的中心节点

记牢这条主线:中心出现在每一条边里,叶子只出现在一条边里。所以中心必然同时躺在前两条边里,取这两条边的公共节点即可。下面先用最朴素的数度数法把这个直觉验一遍,再落到只看两条边的写法。

初始 · 5 个节点,度数全为 0：舞台上是 5 个节点,编号 1 到 5,中间的连线就是边。先亮个谜底:这张图的中心是节点 1,等会儿一步步验。第一种最朴素的想法是数度数,也就是每个节点连了几条边。开始时所有度数都是 0,接下来扫每条边,给它的两个端点各加 1。

第 1 / 4 条边 · [1, 2]：看第 1 条边 [1, 2]。高亮的就是眼下这条边,它连着节点 1 和节点 2。数度数很机械,一条边给它的两个端点各记一笔。

边 [1, 2] 数完 · 节点 1 度数到 1,节点 2 度数到 1：两头各加 1:节点 1 的度数变成 1,节点 2 的度数变成 1。你会注意到节点 1 每条边几乎都掺一脚,度数涨得最快,这正是中心的特征。

第 2 / 4 条边 · [5, 1]：看第 2 条边 [5, 1]。高亮的就是眼下这条边,它连着节点 5 和节点 1。数度数很机械,一条边给它的两个端点各记一笔。

边 [5, 1] 数完 · 节点 5 度数到 1,节点 1 度数到 2：两头各加 1:节点 5 的度数变成 1,节点 1 的度数变成 2。你会注意到节点 1 每条边几乎都掺一脚,度数涨得最快,这正是中心的特征。

第 3 / 4 条边 · [1, 3]：看第 3 条边 [1, 3]。高亮的就是眼下这条边,它连着节点 1 和节点 3。数度数很机械,一条边给它的两个端点各记一笔。

边 [1, 3] 数完 · 节点 1 度数到 3,节点 3 度数到 1：两头各加 1:节点 1 的度数变成 3,节点 3 的度数变成 1。你会注意到节点 1 每条边几乎都掺一脚,度数涨得最快,这正是中心的特征。

第 4 / 4 条边 · [1, 4]：看第 4 条边 [1, 4]。高亮的就是眼下这条边,它连着节点 1 和节点 4。数度数很机械,一条边给它的两个端点各记一笔。

边 [1, 4] 数完 · 节点 1 度数到 4,节点 4 度数到 1：两头各加 1:节点 1 的度数变成 4,节点 4 的度数变成 1。你会注意到节点 1 每条边几乎都掺一脚,度数涨得最快,这正是中心的特征。

度数数完 · 节点 1 度数 = 4 = n-1：4 条边全数完了。节点 1 的度数是 4,正好等于 n-1,也就是 5 减 1;其余 4 个节点度数都是 1。度数最高、达到 n-1 的那个就是中心。数度数这条路走得通,但它把每条边都扫了一遍,做了 O(边数) 的功。

观察 · 叶子度数都是 1,中心度数 n-1：停下来品一下这个结构:每个叶子节点只连着中心一条边,所以度数都是 1,只在一条边里露过面;而中心连着全部 4 个叶子,出现在每一条边里。这个「中心出现在每条边、叶子只在一条边」的差别,就是下面把复杂度砍到 O(1) 的钥匙。

优化 · 不用扫完所有边：既然中心出现在每一条边里,那它必然同时出现在最前面的两条边里。反过来,任何叶子只出现在一条边里,不可能既在第一条边又在第二条边。所以第一条边和第二条边的公共节点,只可能是中心。我们连后面的边都不用看了,只盯前两条。

第一条边 edges[0] = [1, 2]：拿出第一条边 edges[0] = [1, 2]。中心既然出现在每条边里,当然也在这条边里,所以中心只可能是 1 或者 2 这两个候选之一。现在还不知道是哪个,得靠第二条边来裁决。

第二条边 edges[1] = [5, 1]：再看第二条边 edges[1] = [5, 1]。中心同样出现在这条边里,所以它也得是 5 或者 1。把两条边一对照,能同时出现在两条边里的,只有节点 1。这就是我们要找的公共节点。

判定 · 拿 edges[0][0] = 1 去第二条边找：具体怎么落到代码:取第一条边的第一个节点 edges[0][0] = 1,去第二条边 [5, 1] 里看它在不在。先跟第二条边的第一个端点 5 比,1 不等于 5,先不下结论,再看另一个端点。

命中 · 1 也是 edges[1] 的端点 → 中心 = 1：再拿 1 跟第二条边的第二个端点比,1 正好等于 1,命中。这说明节点 1 同时出现在前两条边里,它就是那个公共节点,也就是中心。答案锁定为 1,跟开头亮的谜底对上了。

反面 · 如果 edges[0][0] 不在第二条边呢：顺手想想反面情况。如果 edges[0][0] 没在第二条边里出现,说明它只在第一条边露过面,是个叶子,那中心就只能是第一条边的另一个端点 edges[0][1]。代码里就是一个三目:在就取第一个,不在就取第二个。

为什么 2 不可能是中心：看节点 2,它只在第一条边 [1, 2] 里出现过,第二条边里根本没有它。中心得连着 n-1 条边、出现在每一条边里,而 2 只连着一条边,度数是 1,注定是叶子,不可能当中心。这就从反面印证了公共节点法为什么可靠。

道理 · 中心在每条边,叶子在一条边：把道理收成一句:因为 n ≥ 3,星型图至少有 2 条边,中心出现在每一条边里,所以它一定同时在 edges[0] 和 edges[1] 里;而叶子只出现在一条边里,不可能横跨前两条边。于是前两条边唯一的公共节点必然是中心,看这两条边就足够了。

两法对照 · 结论一致 = 1：两条路对照一下:数度数法扫完 4 条边,找出度数 4 的节点 1;两条边法只看前两条边,取公共点也是 1。结论完全一致,但后者只碰了两条边,做的是常数次比较,这就是我们最终要交的解法。

回放 · 返回中心节点 1：整道题回放一遍:星型图的中心连着每个节点,出现在每一条边里。我们只取前两条边 [1, 2] 和 [5, 1],找它们的公共节点,得到 1,直接返回。一次比较搞定,这就是找星型图中心最省事的办法。

边界想清:n=3 只有 2 条边也够用、中心可能是第一条边的任一端点、后面的边完全不影响结果。

面试重点:中心在每条边源于星型图定义、朴素数度数是 O(n) 而两条边法 O(1)、判公共点要和第二条边两个端点都比。