LeetCode 题解工作台
找出星型图的中心节点
有一个无向的 星型 图，由 n 个编号从 1 到 n 的节点组成。星型图有一个 中心 节点，并且恰有 n - 1 条边将中心节点与其他每个节点连接起来。 给你一个二维整数数组 edges ，其中 edges[i] = [u i , v i ] 表示在节点 u i 和 v i 之间存在一条边。请你找出…
1
题型
7
代码语言
3
相关题
当前训练重点
简单 · 图
答案摘要
中心点的特点是，它与其他所有点都相连，因此只要比较前两条边的点，如果有相同的点，那么这个点就是中心点。 时间复杂度 ，空间复杂度 。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 图 题型思路
题目描述
有一个无向的 星型 图，由 n 个编号从 1 到 n 的节点组成。星型图有一个 中心 节点，并且恰有 n - 1 条边将中心节点与其他每个节点连接起来。
给你一个二维整数数组 edges ，其中 edges[i] = [ui, vi] 表示在节点 ui 和 vi 之间存在一条边。请你找出并返回 edges 所表示星型图的中心节点。
示例 1：
输入：edges = [[1,2],[2,3],[4,2]] 输出：2 解释：如上图所示，节点 2 与其他每个节点都相连，所以节点 2 是中心节点。
示例 2：
输入：edges = [[1,2],[5,1],[1,3],[1,4]] 输出：1
提示：
3 <= n <= 105edges.length == n - 1edges[i].length == 21 <= ui, vi <= nui != vi- 题目数据给出的
edges表示一个有效的星型图
解题思路
方法一：直接比较前两条边的点
中心点的特点是，它与其他所有点都相连，因此只要比较前两条边的点，如果有相同的点，那么这个点就是中心点。
时间复杂度 ，空间复杂度 。
class Solution:
def findCenter(self, edges: List[List[int]]) -> int:
return edges[0][0] if edges[0][0] in edges[1] else edges[0][1]
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | O(1) |
| 空间 | O(1) |
面试官常问的追问
外企场景- question_mark
Look for recognition of the graph structure and the center node's properties.
- question_mark
Test if the candidate can propose an efficient solution with minimal edge checking.
- question_mark
Evaluate the candidate's ability to leverage graph patterns for an O(1) solution.
常见陷阱
外企场景- error
Focusing on complex graph traversal methods when the problem can be solved with simple edge checks.
- error
Overcomplicating the solution by analyzing all nodes or edges when only two edges are needed.
- error
Misunderstanding the star graph's structure and attempting to identify the center through unnecessary computations.
进阶变体
外企场景- arrow_right_alt
What if the graph had a different structure, like a tree or cyclic graph?
- arrow_right_alt
How would you solve this if the graph were directed?
- arrow_right_alt
How would your approach change if there were more than one center node?