找出星型图的中心节点
难度:
标签:
题目描述
有一个无向的 星型 图,由 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 <= 105
edges.length == n - 1
edges[i].length == 2
1 <= ui, vi <= n
ui != vi
- 题目数据给出的
edges
表示一个有效的星型图
代码结果
运行时间: 48 ms, 内存: 39.6 MB
/*
* Approach: In a star graph, one node is the center, connected to all others.
* We find the center by looking at the first two edges. The common node in these two edges is the center.
* Using Java Streams, we can find this node efficiently.
*/
import java.util.Arrays;
public class Solution {
public int findCenter(int[][] edges) {
return Arrays.stream(edges)
.flatMapToInt(e -> Arrays.stream(new int[]{e[0], e[1]}))
.distinct()
.filter(n -> Arrays.stream(edges)
.allMatch(e -> e[0] == n || e[1] == n))
.findFirst()
.getAsInt();
}
}
解释
方法:
此题解利用了星型图的特性:中心节点会与其他所有节点都有连接。因此,只需要检查图中的前两条边就足够确定中心节点。如果第一条边的任一节点与第二条边的任一节点相同,那么这个相同的节点就是中心节点。这种方法非常高效,因为它不需要检查所有的边,只需比较前两条边。
时间复杂度:
O(1)
空间复杂度:
O(1)
代码细节讲解
🦆
为什么只比较前两条边就足以确定中心节点,而不需要查看更多的边?
▷🦆
假设第一条和第二条边没有共同的节点,这种情况下该如何处理?
▷🦆
此算法在处理边的信息时是否考虑了所有边的节点都是有效的,即不存在孤立的节点或额外的边?
▷🦆
如果输入的边并不构成一个标准的星型图,而是存在环或其他结构,该算法的输出结果会是什么?
▷