【刷题日记】1791. 找出星型图的中心节点

本次刷题日记的第 26 篇，力扣题为：【刷题日记】1791. 找出星型图的中心节点 ，简单

一、题目描述：

昨天加班比较晚来不及刷每日一题，今天加班也回来晚了点，但是看到是一个简单的图，那么还是刷刷吧

据我所知，我身边的朋友都不会刷图相关的题，原因是因为面试不会考图，因为涉及图的题目编码量也会相对较大

但是我认为学会学好了图，其实在生活中能够解决很多问题，例如 城市最短近距离等等

咱们还是来认真看看题目

二、这道题考察了什么思想？你的思路是什么？

仔细看这道题，给我们透露了哪些重要的信息呢：

• 这是一个无向图，节点和节点之后是没有箭头的，没有入度和出度一说
• 无向图组成的图形是一个星型，意味着节点的数量总是比边的数量大 1 ，如果节点数量为 n，那么边的数量就为 n-1 ， 反过来也一样
• 通过题目给出的边的关系，我们找出中心节点

得到如上重要信息之后，我们可以思考一下，**在上述的情况中，什么才叫做中心节点呢？**我们可以如何用数字化的方式来进行定义呢？

咱们举一个例子来看看效果：

例如下面的这个星型图：

总共是 6 个节点， 5 条边 ，我们可以发现这 5 条边都会连接到中心节点，那么我们就不难想到节点的度，当然如果没有图论基础的话，可以去补充一下

简单理解就是，对于无向图，有多少个边某一节点连接，那么这个节点的度就是 边的个数

那么，基于上图，我们就知道

• 4 节点的度是 5
• 1 ， 2， 3， 5， 6 节点的度都是 1

通过数据我们其实也明确了，我们只要找到一个节点的度，是等于边的条数的，那么就可以实现这个题解了

好，那么接下来就是将上述思路，进行翻译了

三、编码

根据上述逻辑和分析，我们就可以翻译成如下代码，翻译代码的时候需要注意我们计算节点度的方式，以及空间的开辟

编码如下：

func findCenter(edges [][]int) int {
    // 得到节点的数量，等于边的数量 + 1
    length := len(edges) + 1
    // 此处开辟的空间是 length+1 ， 是因为节点的数字不是从 0 开始的，而是从 1 开始的
    g := make([]int,length+1)
    // 计算每一个节点的 度
    for _,e := range edges {
        g[e[0]]++
        g[e[1]]++
    }
    // 找到节点度为 节点数 -1 的节点，则这个节点就是中心节点
    for i,num := range g {
        if num == length-1{
            return i
        }
    }
    return -1
}

看了上述代码，我们需要注意在开辟空间存储节点对应的度的时候，咱们的索引是从 1 开始的，例如如果有 4 个节点的话，那么我们的开辟的帮助空间是 4 + 1

四、总结：

很明显，这里我们可以看出来时间复杂度是 O(n)，因为需要遍历每一个节点，来判断节点的度是否符合我们的要求

空间复杂度也是  O(n) ，因为我们需要开辟节点个数 + 1 的帮助空间

原题地址：1791. 找出星型图的中心节点

今天就到这里，学习所得，若有偏差，还请斧正

欢迎点赞，关注，收藏

朋友们，你的支持和鼓励，是我坚持分享，提高质量的动力

好了，本次就到这里

技术是开放的，我们的心态，更应是开放的。拥抱变化，向阳而生，努力向前行。

我是阿兵云原生，欢迎点赞关注收藏，下次见~