Table of contents
1.
Introduction
2.
What is a Star
3.
Input-Output
3.1.
Example 1
3.2.
Example 2
4.
Approach
4.1.
C++ Code
4.2.
Python Code
4.3.
Java Code
5.
Complexity Analysis
6.
Frequently Asked Questions
6.1.
How can we represent a Graph?
6.2.
What are the primary elements of a graph?
6.3.
What is the difference between a directed and undirected graph?
7.
Conclusion
Last Updated: Mar 27, 2024
Medium

Check if a Given Graph is Star

Author Rhythm Jain
0 upvote
Career growth poll
Do you think IIT Guwahati certified course can help you in your career?

Introduction

We can represent a Graph using an adjacency list or a matrix. We are given a graph in the form of a N x N matrix. Our task is to find whether the given representation of the Graph contains a star or not.

What is a Star

A star graph is a form of a graph with N vertices that has N-1 vertices with degree 1 and a single vertex with degree N - 1. These appear to be N - 1 vertex linked to a single core vertex. Sn denotes a star graph with total N - vertices. Here degree means the number of edges of a vertex.

Image showing Sn for different values of n

Input-Output

We have an N x N matrix.

Output “Yes” if the given graph is a Start Graph; else, output “No.”

Example 1

Input

[ [0, 1, 0]

[1, 0, 1]

[0, 1, 0] ]

Output

Yes

Example 2

Input

[ [0, 1, 0]

[1, 1, 1]

[0, 1, 0] ]

Output

No

Approach

Simply traverse the whole matrix and count the number of vertices with degrees 1 and N-1. If the number of vertices with degree 1 is N-1 and the number of vertices with degree N-1 is 1, the given graph should be a star graph.

Some Corner Cases to tackle:

  • For S1, there must be a single node with no edges.
  • For S2, there must be two nodes with a single edge connecting both.

C++ Code

#include<bits/stdc++.h>
using namespace std;


bool checkStar(vector<vector<int>>& graph)
{
    //number of vertex with degree 1 and n-1
    int deg1 = 0, degn = 0;
    int n=graph.size();
    // check for S1
    if (n == 1)
        return (graph[0][0] == 0);
     
    // check for S2
    if (n == 2)   
       return (graph[0][0] == 0 && graph[0][1] == 1 &&
               graph[1][0] == 1 && graph[1][1] == 0 );
 
    // check for Sn (n>2)
    for (int i = 0; i < n; i++)
    {
        int deg_i = 0;
        for (int j = 0; j < n; j++)
            if (graph[i][j])
                deg_i++;
 
        if (deg_i == 1)
            deg1++;
        else if (deg_i == n-1)
            degn++;
    }
     
    return (deg1 == (n-1) &&
            degn == 1);
}
 
// driver code
int main()
{
    vector<vector<int>> graph = { {0, 1, 0},
                                {1, 0, 1},
                                {0, 1, 0}
                                };
 
    checkStar(graph) ? cout << "Yes\n" :
                     cout << "No\n";
    return 0;
}
You can also try this code with Online C++ Compiler
Run Code

 

Output

Yes
You can also try this code with Online Python Compiler
Run Code

Python Code

def checkStar(graph) :
	n=len(graph)
	# number of vertex with degree 1 and n-1
	deg1 = 0
	degn = 0


	# check for S1
	if (n == 1) :
		return (graph[0][0] == 0)

	# check for S2
	if (n == 2) :
		return (graph[0][0] == 0 and
		graph[0][1] == 1 and
		graph[1][0] == 1 and
		graph[1][1] == 0)


	# check for Sn (n>2)
	for i in range(0, n) :


		deg_i = 0
		for j in range(0, n) :
			if (graph[i][j]) :
				deg_i = deg_i + 1


			if (deg_i == 1) :
				deg1 = deg1 + 1


			elif (deg_i == n - 1):
				degn = degn + 1

	return (deg1 == (n - 1) and degn == 1)


# Driver code
graph = [[0, 1, 0],
    [1, 0, 1],
    [0, 1, 0]]


if(checkStar(graph)) :
	print ("Yes\n")
else :
	print ("No\n")
You can also try this code with Online Python Compiler
Run Code

Output

Yes
You can also try this code with Online Java Compiler
Run Code

Java Code

import java.io.*;


class Main
{

	static boolean checkStar(int graph[][])
	{
    	int n=graph.length;
		// number of vertex with degree 1 and n-1
		int deg_1 = 0,
		deg_n = 0;

		// check for S1
		if (size == 1)
			return (graph[0][0] == 0);

		// check for S2
		if (size == 2)
			return (graph[0][0] == 0 &&
			graph[0][1] == 1 &&
			graph[1][0] == 1 &&
			graph[1][1] == 0);

		// check for Sn (n>2)
		for (int i = 0; i < size; i++)
		{
			int deg_i = 0;
			for (int j = 0; j < size; j++)
			if (graph[i][j] == 1)
				deg_i++;

			if (deg_i == 1)
				deg_1++;
			else if (deg_i == size - 1)
				deg_n++;
		}

		return (deg_1 == (size - 1) && deg_n == 1);
	}

	// Driver code
	public static void main(String args[])
	{
		int graph[][] = {{0, 1, 1, 1},
						{1, 0, 0, 0},
						{1, 0, 0, 0},
						{1, 0, 0, 0}};

		if (checkStar(graph))
			System.out.print("Yes\n");
		else
			System.out.print("No\n");
	}
}
You can also try this code with Online Java Compiler
Run Code

Output

Yes
You can also try this code with Online Java Compiler
Run Code

Complexity Analysis

Time Complexity - O(N x N)

We had to iterate over the whole matrix of size N x N.

Space Complexity - O(1)

Variables take up a constant amount of space.
Check out this problem - No of Spanning Trees in a Graph

Also check out: Application of graph data structure

Frequently Asked Questions

How can we represent a Graph?

There are two ways to represent a Graph:

1. Adjacency Matrix

2. Adjacency List

What are the primary elements of a graph?

The primary elements of a graph are the vertices and the edges. The vertices represent the particular things being linked, while the edges reflect the interactions between those objects.

What is the difference between a directed and undirected graph?

A directed graph is one in which the edges are assigned a specified direction. As a result, the edges can only be traveled in one way. On the other hand, an undirected graph has no direction associated with its edges, allowing them to be traversed in any way.

Conclusion

We hope this blog has helped you enhance your Knowledge about Graphs. We discussed a problem with checking if a given Graph is a Start or not. We discussed what a Star is and what the corner cases involved. Then we write code in three different languages- C++, Python, and Java for better understanding.

See Basics of C++ with Data StructureDBMSOperating System by Coding Ninjas, and keep practicing on our platform Coding Ninjas Studio.

If you think you are ready for the tech giants company, check out the mock test series on code studio.

 

Related articles:

 

You can also refer to our Guided Path on Coding Ninjas Studio to upskill yourself in domains like Data Structures and AlgorithmsCompetitive ProgrammingAptitude, and many more! You can also prepare for tech giants companies like Amazon, Microsoft, Uber, etc., by looking for the questions asked by them in recent interviews. If you want to prepare for placements, refer to the interview bundle. If you are nervous about your interviews, you can see interview experiences to get ideas about these companies' questions.

Nevertheless, you may consider our premium courses to give your career an edge over others!

Do upvote our blogs if you find them helpful and engaging!

Happy Learning!

Live masterclass