Make writing a habit together! This is the sixth day of my participation in the “Gold Digging Day New Plan · April More text Challenge”. Click here for more details.

1791. Find the central node of the star chart

【 brush topic diary 】1791. Find the central node of the star graph. Easy

I. Title Description:

Yesterday, I worked overtime too late to brush the daily question. Today, I came back from overtime too late, but I saw a simple picture, so I still brush it

As far as I know, none of my friends will brush the questions related to graph, the reason is that the interview will not test the graph, because the number of coding questions involving graph will be relatively large

However, I believe that learning the map well can solve many problems in life, such as the shortest distance in the city and so on

So let’s take a closer look

2. What ideas does this question examine? What’s your thinking?

Take a closer look at this question and see what it tells us:

  • This is an undirected graph. There are no arrows after nodes and nodes. There are no degrees in and degrees out
  • The graph of an undirected graph is a star, meaning that the number of nodes is always 1 greater than the number of edges, and if the number of nodes is N, then the number of edges is n-1, and vice versa
  • And by looking at the relationship between the edges that they give us, we find the central node

With this important information in mind, we can ask ourselves, ** What is the central node in this case? ** How can we define it digitally?

Let’s take an example to see the effect:

For example, the following star chart:

There are six nodes and five edges, and we can see that all five edges are connected to the central node, so it’s not hard to think about the degree of the node, and of course if you don’t have graph theory, you can supplement that

The simple way to think about it is, for an undirected graph, how many edges are there that a node is connected to, and then the degree of that node is the number of edges

So, based on the figure above, we know that

  • The degree of the four nodes is 5
  • Nodes 1, 2, 3, 5, and 6 all have degrees 1

In fact, through the data, we also know that as long as we find the degree of a node is equal to the number of edges, then we can achieve this problem

Ok, so the next step is to translate the above ideas

Three, coding

According to the above logic and analysis, we can translate it into the following code. When translating the code, we need to pay attention to the way of calculating the node degree and the development of space

The encoding is as follows:

func findCenter(edges [][]int) int {
    // The number of nodes is equal to the number of edges + 1
    length := len(edges) + 1
    
    // The space is length+1, because the number of nodes does not start from 0, but from 1
    g := make([]int,length+1)
    
    // Calculate the degree of each node
    for _,e := range edges {
        g[e[0]]++
        g[e[1]] + +}// Find the node whose degree is -1, then this node is the center node
    for i,num := range g {
        if num == length- 1{
            return i
        }
    }

    return - 1
}
Copy the code

After looking at the above code, we need to note that our index starts from 1 when developing the degree corresponding to the space storage node. For example, if there are four nodes, then our developing help space is 4 + 1

Iv. Summary:

Obviously, here we can see that the time is order n, because we have to go through each node to see if the degree of the node is what we want it to be

The space complexity is also O(n), because we need to open up the help space with + 1 nodes

Find the central node of the star diagram

Today is here, learning, if there is a deviation, please correct

Welcome to like, follow and favorites

Friends, your support and encouragement, I insist on sharing, improve the quality of the power

All right, that’s it for this time

Technology is open, our mentality, should be more open. Embrace change, live in the sun, and strive to move forward.

I am Nezha, welcome to like, see you next time ~