Do you think IIT Guwahati certified course can help you in your career?
No
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.
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
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.
You can also refer to our Guided Path on Coding Ninjas Studio to upskill yourself in domains like Data Structures and Algorithms, Competitive Programming, Aptitude, 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
Become a YouTube Analyst: Use Python to analyze viewers data
by Coding Ninjas
04 Feb, 2025
02:30 PM
Get hired as an Amazon SDE : Resume building tips
by Coding Ninjas
03 Feb, 2025
02:30 PM
Expert tips: Ace Leadership roles in Fortune 500 companies
by Coding Ninjas
03 Feb, 2025
12:30 PM
Become a YouTube Analyst: Use Python to analyze viewers data