Vultr DocsLatest Content

Find Center of Star Graph

Updated on 28 May, 2025
Find Center of Star Graph header image

Problem Statement

In an undirected star graph consisting of n nodes labeled sequentially from 1 to n, we define a structural pattern where one node is the center, directly connected to every other node by n-1 edges. Essentially, this architecture shapes the graph such that one node (the center) universally connects with all others, forming a star-like topology. Given a 2D integer array, edges, with each element edges[i] = [ui, vi] signifying a direct connection between the nodes ui and vi, the task is to identify and return this central node in the graph configuration described.

Examples

Example 1

Input:

edges = [[1,2],[2,3],[4,2]]

Output:

2

Explanation:

As shown in the figure above, node 2 is connected to every other node, so 2 is the center.

Example 2

Input:

edges = [[1,2],[5,1],[1,3],[1,4]]

Output:

1

Constraints

  • 3 <= n <= 105
  • edges.length == n - 1
  • edges[i].length == 2
  • 1 <= ui, vi <= n
  • ui != vi
  • The given edges represent a valid star graph.

Approach and Intuition

The nature of a star graph provides a straightforward clue: the center node appears in all the edges since it is connected to every other node. Therefore, the central node will have the highest occurrence across all provided edge pairs. Here's how you can infuse this intuition into steps to solve the problem:

  1. Observe that in a star graph of size n, the task simplifies down to counting node occurrences in the edge definitions and determining which node appears the most, ideally n-1 times.
  2. Start by initializing a dictionary to count appearances of each node in the edge list. Iterate through each edge pair and increment the count for both nodes.
  3. Since the problem constraints guarantee the graph's star structure, the node with the maximum count, appearing in exactly n-1 edges, is unequivocally the central node.
  4. As an alternate method without needing extra space, consider the first two pairs of the edges array. Given the structure, the central node must appear in both edge definitions. Thus, the node common to the first two edge definitions can be deduced to be the center.

Through these approaches, one leverages the fixed properties and constraints of a star graph to efficiently pinpoint the central node.

Solutions

  • C++
  • Java
  • Python
cpp 
class Solution {
public:
    int findCenter(vector<vector<int>>& edges) {
        vector<int> edge1 = edges[0];
        vector<int> edge2 = edges[1];

        return (edge1[0] == edge2[0] || edge1[0] == edge2[1])
                   ? edge1[0]
                   : edge1[1];
    }
};

This solution is designed to identify the center of a star graph by examining its edges. The star graph is a type of graph where one central node (the center) connects to all other nodes. The approach assumes you receive a list of edge pairs representing connections between nodes, with each edge represented as a pair of integers.

To determine the center of the star graph:

  1. Retrieve the first two edge pairs from the list of edges.
  2. Compare the nodes in these two edges.
  3. Check if the first node of the first edge matches either node in the second edge. If it does, this node is the center. If not, the other node in the first edge is the center.

This method efficiently finds the center by checking no more than the first two edges. Since, in a star graph, the center node must be part of any two edges, this ensures an optimal solution with constant time complexity, O(1).

java 
class Solution {

    public int findHub(int[][] connections) {
        int[] edgeOne = connections[0];
        int[] edgeTwo = connections[1];

        return (edgeOne[0] == edgeTwo[0] || edgeOne[0] == edgeTwo[1]) 
            ? edgeOne[0] 
            : edgeOne[1];
    }
}

This solution tackles the problem of finding the center node in a star graph by analyzing the initial pairs of connected nodes provided in a 2D array, referred to as connections. Each pair represents an edge between two nodes.

  • Extract the first two edges from the connections array. These would be sufficient because in a star graph, all edges share a common node, which is what we are looking to find.
  • Determine which node from the first edge (edgeOne) is common to either node in the second edge (edgeTwo). This is done through a simple comparison:
    • If the first node of edgeOne matches either node of edgeTwo, then the first node of edgeOne is the center node.
    • Otherwise, the second node of edgeOne is the center node.

The function findHub returns the identified center node of the star graph, which is efficiently identified with just a comparison of the nodes from the first two edges, fully leveraging the properties of a star graph structure.

python 
class Solution:
    def centerNode(self, edge_list: List[List[int]]) -> int:
        edge1, edge2 = edge_list[0], edge_list[1]

        return edge1[0] if edge1[0] in edge2 else edge1[1]

The solution provided in Python helps identify the center node of a star graph. Given a set of edges (edge_list), the task focuses on determining which node serves as the central point connected to all other nodes in this specific graph structure.

The approach involves:

  1. Extracting the first two edges from the list to leverage their commonality, storing them in edge1 and edge2.
  2. Checking if the first node (edge1[0]) of the first edge is present in the second edge.
  3. If it exists in edge2, it confirms that edge1[0] is the center. Otherwise, the second node (edge1[1]) of the first edge is the center.

This method ensures efficient identification of the central node with minimal computation, leveraging the property that in a star graph, the center node is the common element in any two edges.

Comments

No comments yet.