Teaching Kids Programming – Algorithms to Find Center of Star Graph

Teaching Kids Programming: Videos on Data Structures and Algorithms

There is an undirected star graph consisting of n nodes labeled from 1 to n. A star graph is a graph where there is one center node and exactly n – 1 edges that connect the center node with every other node.

You are given a 2D integer array edges where each edges[i] = [ui, vi] indicates that there is an edge between the nodes ui and vi. Return the center of the given star graph.

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

The center is the only node that has more than one edge.
The center is also connected to all other nodes.
Any two edges must have a common node, which is the center.

Algorithms to Find the Center of a Star Graph

Using a dictionary, we can compute the indegree of each vertices. Then, the center is the one with the maximum indegree value. We can use different ways to obtain the item/key (which is the vertex) that has the largest value of indegree.

The following Python code to find the centre of the Star Graph takes O(N) time and O(N) space where N is the number of the nodes in the graph.

1
2
3
4
5
6
7
8

class Solution:
    def findCenter(self, edges: List[List[int]]) -> int:
        G = defaultdict(int)
        for u, v in edges:
            G[u] += 1
            G[v] += 1
        # or return max(G, key=G.get)
        return max(G.items(), key=lambda i:i[1])[0]

class Solution:
    def findCenter(self, edges: List[List[int]]) -> int:
        G = defaultdict(int)
        for u, v in edges:
            G[u] += 1
            G[v] += 1
        # or return max(G, key=G.get)
        return max(G.items(), key=lambda i:i[1])[0]

We can return the center vertex as long as the indegree is larger than 1. This will improve the complexity to O(1) in both time and space. Because at most two iterations, we will find the center.

1
2
3
4
5
6
7
8
9
10

class Solution:
    def findCenter(self, edges: List[List[int]]) -> int:
        G = defaultdict(int)
        for u, v in edges:
            G[u] += 1
            G[v] += 1
            if G[u] > 1:
                return u
            if G[v] > 1:
                return v

class Solution:
    def findCenter(self, edges: List[List[int]]) -> int:
        G = defaultdict(int)
        for u, v in edges:
            G[u] += 1
            G[v] += 1
            if G[u] > 1:
                return u
            if G[v] > 1:
                return v

Alternative, We can do this O(1) by checking if two vertices of the any edge (preferrably first one) to see which one appears more than once by comparing another different edge. This works because the center vertex appears more than one in all edges. And for the first two edges, we surely can find a common node that appears in both.

1
2
3
4
5

class Solution:
    def findCenter(self, edges: List[List[int]]) -> int:
        if edges[0][0] == edges[1][0] or edges[0][0] == edges[1][1]:
            return edges[0][0]
        return edges[0][1]

class Solution:
    def findCenter(self, edges: List[List[int]]) -> int:
        if edges[0][0] == edges[1][0] or edges[0][0] == edges[1][1]:
            return edges[0][0]
        return edges[0][1]

See also: Teaching Kids Programming – Introduction to Graph Data Structure

–EOF (The Ultimate Computing & Technology Blog) —