Given a graph G, the task is to check if it represents a Star Topology.
A Star Topology is the one shown in the image below:
Examples:
Input : Graph =
Output : YES Input : Graph =
Output : NO
A graph of V vertices represents a star topology if it satisfies the following three conditions:
- One node (also called the central node) has degree V – 1.
- All nodes except the central node have degree 1.
- No of edges = No of Vertices – 1.
The idea is to traverse the graph and check if it satisfies the above three conditions. If yes, then it represents a Star Topology.
Below is the implementation of the above approach:
C++
// CPP program to check if the given graph// represents a Star Topology#include <bits/stdc++.h>using namespace std;// A utility function to add an edge in an// undirected graph.void addEdge(vector<int> adj[], int u, int v){ adj[u].push_back(v); adj[v].push_back(u);}// A utility function to print the adjacency list// representation of graphvoid printGraph(vector<int> adj[], int V){ for (int v = 0; v < V; ++v) { cout << "\n Adjacency list of vertex " << v << "\n head "; for (auto x : adj[v]) cout << "-> " << x; printf("\n"); }}/* Function to return true if the graph represented by the adjacency list represents a Star topology else return false */bool checkStarTopologyUtil(vector<int> adj[], int V, int E){ // Number of edges should be equal // to (Number of vertices - 1) if (E != (V - 1)) return false; // a single node is termed as a star topology // having only a central node if (V == 1) return true; int* vertexDegree = new int[V + 1]; memset(vertexDegree, 0, sizeof vertexDegree); // calculate the degree of each vertex for (int i = 1; i <= V; i++) { for (auto v : adj[i]) { vertexDegree[v]++; } } // countCentralNodes stores the count of nodes // with degree V - 1, which should be equal to 1 // in case of star topology int countCentralNodes = 0, centralNode = 0; for (int i = 1; i <= V; i++) { if (vertexDegree[i] == (V - 1)) { countCentralNodes++; // Store the index of the central node centralNode = i; } } // there should be only one central node // in the star topology if (countCentralNodes != 1) return false; for (int i = 1; i <= V; i++) { // except for the central node // check if all other nodes have // degree 1, if not return false if (i == centralNode) continue; if (vertexDegree[i] != 1) { return false; } } // if all three necessary // conditions as discussed, // satisfy return true return true;}// Function to check if the graph // represents a Star topologyvoid checkStarTopology(vector<int> adj[], int V, int E){ bool isStar = checkStarTopologyUtil(adj, V, E); if (isStar) { cout << "YES" << endl; } else { cout << "NO" << endl; }}// Driver codeint main(){ // Graph 1 int V = 5, E = 4; vector<int> adj1[V + 1]; addEdge(adj1, 1, 2); addEdge(adj1, 1, 3); addEdge(adj1, 1, 4); addEdge(adj1, 1, 5); checkStarTopology(adj1, V, E); // Graph 2 V = 5, E = 4; vector<int> adj2[V + 1]; addEdge(adj2, 1, 2); addEdge(adj2, 1, 3); addEdge(adj2, 3, 4); addEdge(adj2, 4, 5); checkStarTopology(adj2, V, E); return 0;} |
Java
// Java program to check if the given graph // represents a star topology import java.io.*;import java.util.*;class GFG { // A utility function to add an edge in an // undirected graph. static void addEdge(ArrayList<ArrayList<Integer>> adj, int u, int v) { adj.get(u).add(v); adj.get(v).add(u); } // A utility function to print the adjacency list // representation of graph static void printGraph(ArrayList<ArrayList<Integer>> adj, int V) { for (int v = 0; v < V; ++v) { System.out.print("\n Adjacency list of vertex " + v + "\n head "); for (int x : adj.get(v)) { System.out.print( "-> " + x); } System.out.println(); } } /* Function to return true if the graph represented by the adjacency list represents a Star topology else return false */ static boolean checkStarTopologyUtil(ArrayList<ArrayList<Integer>> adj, int V, int E) { // Number of edges should be equal // to (Number of vertices - 1) if (E != (V - 1)) { return false; } // a single node is termed as a star topology // having only a central node if (V == 1) { return true; } int[] vertexDegree = new int[V + 1]; // calculate the degree of each vertex for (int i = 1; i <= V; i++) { for (int v : adj.get(i)) { vertexDegree[v]++; } } // countCentralNodes stores the count of nodes // with degree V - 1, which should be equal to 1 // in case of star topology int countCentralNodes = 0, centralNode = 0; for (int i = 1; i <= V; i++) { if (vertexDegree[i] == (V - 1)) { countCentralNodes++; // Store the index of the central node centralNode = i; } } // there should be only one central node // in the star topology if (countCentralNodes != 1) return false; for (int i = 1; i <= V; i++) { // except for the central node // check if all other nodes have // degree 1, if not return false if (i == centralNode) continue; if (vertexDegree[i] != 1) { return false; } } // if all three necessary // conditions as discussed, // satisfy return true return true; } // Function to check if the graph // represents a Star topology static void checkStarTopology(ArrayList<ArrayList<Integer>> adj, int V, int E) { boolean isStar = checkStarTopologyUtil(adj, V, E); if (isStar) { System.out.println("YES"); } else { System.out.println("NO"); } } // Driver code public static void main (String[] args) { // Graph 1 int V = 5, E = 4; ArrayList<ArrayList<Integer>> adj1 = new ArrayList<ArrayList<Integer>>(); for(int i = 0; i < V + 1; i++) { adj1.add(new ArrayList<Integer>()); } addEdge(adj1, 1, 2); addEdge(adj1, 1, 3); addEdge(adj1, 1, 4); addEdge(adj1, 1, 5); checkStarTopology(adj1, V, E); // Graph 2 V = 5; E = 4; ArrayList<ArrayList<Integer>> adj2 = new ArrayList<ArrayList<Integer>>(); for(int i = 0; i < (V + 1); i++) { adj2.add(new ArrayList<Integer>()); } addEdge(adj2, 1, 2); addEdge(adj2, 1, 3); addEdge(adj2, 3, 4); addEdge(adj2, 4, 5); checkStarTopology(adj2, V, E); }}// This code is contributed by rag2127 |
Python3
# Python3 program to check if the given graph# represents a star topology# A utility function to add an edge in an# undirected graph.def addEdge(adj, u, v): adj[u].append(v) adj[v].append(u)# A utility function to print the adjacency list# representation of graphdef printGraph(adj, V): for v in range(V): print("Adjacency list of vertex ",v,"\n head ") for x in adj[v]: print("-> ",x,end=" ") printf()# /* Function to return true if the graph represented# by the adjacency list represents a star topology# else return false */def checkStarTopologyUtil(adj, V, E): # Number of edges should be equal # to (Number of vertices - 1) if (E != (V - 1)): return False # a single node is termed as a bus topology if (V == 1): return True vertexDegree = [0]*(V + 1) # calculate the degree of each vertex for i in range(V+1): for v in adj[i]: vertexDegree[v] += 1 # countCentralNodes stores the count of nodes # with degree V - 1, which should be equal to 1 # in case of star topology countCentralNodes = 0 centralNode = 0 for i in range(1, V + 1): if (vertexDegree[i] == (V - 1)): countCentralNodes += 1 # Store the index of the central node centralNode = i # there should be only one central node # in the star topology if (countCentralNodes != 1): return False for i in range(1, V + 1): # except for the central node # check if all other nodes have # degree 1, if not return false if (i == centralNode): continue if (vertexDegree[i] != 1): return False # if all three necessary # conditions as discussed, # satisfy return true return True# Function to check if the graph represents a bus topologydef checkStarTopology(adj, V, E): isStar = checkStarTopologyUtil(adj, V, E) if (isStar): print("YES") else: print("NO" )# Driver code# Graph 1V, E = 5, 4adj1=[[] for i in range(V + 1)]addEdge(adj1, 1, 2)addEdge(adj1, 1, 3)addEdge(adj1, 1, 4)addEdge(adj1, 1, 5)checkStarTopology(adj1, V, E)# Graph 2V, E = 4, 4adj2=[[] for i in range(V + 1)]addEdge(adj2, 1, 2)addEdge(adj2, 1, 3)addEdge(adj2, 3, 4)addEdge(adj2, 4, 2)checkStarTopology(adj2, V, E)# This code is contributed by mohit kumar 29 |
C#
// C# program to check if the given graph // represents a star topology using System;using System.Collections.Generic;class GFG{ // A utility function to add an edge in an // undirected graph. static void addEdge(List<List<int>> adj, int u, int v) { adj[u].Add(v); adj[v].Add(u); } // A utility function to print the adjacency list // representation of graph static void printGraph(List<List<int>> adj, int V) { for (int v = 0; v < V; ++v) { Console.WriteLine("\n Adjacency list of vertex " + v + "\n head "); foreach (int x in adj[v]) { Console.Write( "-> " + x); } Console.WriteLine(); } } /* Function to return true if the graph represented by the adjacency list represents a Star topology else return false */ static bool checkStarTopologyUtil(List<List<int>> adj, int V, int E) { // Number of edges should be equal // to (Number of vertices - 1) if (E != (V - 1)) { return false; } // a single node is termed as a bus topology if (V == 1) { return true; } int[] vertexDegree = new int[V + 1]; // calculate the degree of each vertex for (int i = 1; i <= V; i++) { foreach (int v in adj[i]) { vertexDegree[v]++; } } // countCentralNodes stores the count of nodes // with degree V - 1, which should be equal to 1 // in case of star topology int countCentralNodes = 0, centralNode = 0; for (int i = 1; i <= V; i++) { if (vertexDegree[i] == (V - 1)) { countCentralNodes++; // Store the index of the central node centralNode = i; } } // there should be only one central node // in the star topology if (countCentralNodes != 1) return false; for (int i = 1; i <= V; i++) { // except for the central node // check if all other nodes have // degree 1, if not return false if (i == centralNode) continue; if (vertexDegree[i] != 1) { return false; } } // if all three necessary // conditions as discussed, // satisfy return true return true; } // Function to check if the graph // represents a Star topology static void checkStarTopology(List<List<int>> adj, int V, int E) { bool isStar = checkStarTopologyUtil(adj, V, E); if (isStar) { Console.WriteLine("YES"); } else { Console.WriteLine("NO"); } } // Driver code static public void Main () { // Graph 1 int V = 5, E = 4; List<List<int>> adj1 = new List<List<int>>(); for(int i = 0; i < V + 1; i++) { adj1.Add(new List<int>()); } addEdge(adj1, 1, 2); addEdge(adj1, 1, 3); addEdge(adj1, 1, 4); addEdge(adj1, 1, 5); checkStarTopology(adj1, V, E); // Graph 2 V = 5; E = 4; List<List<int>> adj2 = new List<List<int>>(); for(int i = 0; i < V + 1; i++) { adj2.Add(new List<int>()); } addEdge(adj2, 1, 2); addEdge(adj2, 1, 3); addEdge(adj2, 3, 4); addEdge(adj2, 4, 4); checkStarTopology(adj2, V, E); }}// This code is contributed by avanitrachhadiya2155 |
Javascript
<script>// JavaScript program to check if the given graph// represents a star topology // A utility function to add an edge in an // undirected graph.function addEdge(adj,u,v){ adj[u].push(v); adj[v].push(u);} // A utility function to print the adjacency list // representation of graphfunction printGraph(adj,V){ for (let v = 0; v < V; ++v) { document.write("\n Adjacency list of vertex " + v + "\n head "); for (let x=0;x<adj[v].length;x++) { document.write( "-> " + adj[v][x]); } document.write("<br>"); }}/* Function to return true if the graph represented by the adjacency list represents a star topology else return false */function checkStarTopologyUtil(adj,V,E){ // Number of edges should be equal // to (Number of vertices - 1) if (E != (V - 1)) { return false; } // a single node is termed as a bus topology if (V == 1) { return true; } let vertexDegree = new Array(V + 1); for(let i=0;i<vertexDegree.length;i++) { vertexDegree[i]=0; } // calculate the degree of each vertex for (let i = 1; i <= V; i++) { for (let v=0;v<adj[i].length;v++) { vertexDegree[adj[i][v]]++; } } // countCentralNodes stores the count of nodes // with degree V - 1, which should be equal to 1 // in case of star topology let countCentralNodes = 0, centralNode = 0; for (let i = 1; i <= V; i++) { if (vertexDegree[i] == (V - 1)) { countCentralNodes++; // Store the index of the central node centralNode = i; } } // there should be only one central node // in the star topology if (countCentralNodes != 1) return false; for (let i = 1; i <= V; i++) { // except for the central node // check if all other nodes have // degree 1, if not return false if (i == centralNode) continue; if (vertexDegree[i] != 1) { return false; } } // if all three necessary // conditions as discussed, // satisfy return true return true;}// Function to check if the graph represents a star topologyfunction checkStarTopology(adj,V,E){ let isStar = checkStarTopologyUtil(adj, V, E); if (isStar) { document.write("YES<br>"); } else { document.write("NO<br>"); }}// Driver code// Graph 1 let V = 5, E = 4; let adj1=[]; for(let i = 0; i < V + 1; i++) { adj1.push([]); } addEdge(adj1, 1, 2); addEdge(adj1, 1, 3); addEdge(adj1, 1, 4); addEdge(adj1, 1, 5); checkStarTopology(adj1, V, E); // Graph 2 V = 5; E = 4; let adj2 = []; for(let i = 0; i < (V + 1); i++) { adj2.push([]); } addEdge(adj2, 1, 2); addEdge(adj2, 1, 3); addEdge(adj2, 3, 4); addEdge(adj2, 4, 2); checkStarTopology(adj2, V, E);// This code is contributed by patel2127</script> |
Output
YES NO
Time Complexity: O(V + E) where V and E are the numbers of vertices and edges in the graph respectively.
Approach 2: Using DFS:
The DFS algorithm implemented in the code visits all the vertices in the graph, starting from a specified source vertex.
- The DFS function takes in a graph represented as an adjacency list (adj), the total number of vertices in the graph (V), and the starting vertex (s).
- The function starts by creating a boolean array visited of size V initialized to false which keeps track of whether a vertex has been visited or not.
- Then it initializes a stack stack and pushes the starting vertex s onto the stack.
- The function enters a loop where it pops the top element from the stack and checks whether it has been visited or not.
- If the vertex has not been visited, it marks it as visited and prints it.
- It then iterates through the adjacency list of the popped vertex v and pushes any unvisited neighbors onto the stack.
- The loop continues until the stack is empty, which means all vertices reachable from the starting vertex have been visited.
C++
#include <iostream>#include <vector>using namespace std;// A utility function to add an edge in an undirected graph.void addEdge(vector<int> adj[], int u, int v) { adj[u].push_back(v); adj[v].push_back(u);}// A utility function to print the adjacency list representation of graphvoid printGraph(vector<int> adj[], int V) { for (int v = 0; v < V; ++v) { cout << "Adjacency list of vertex " << v << "\n head "; for (auto x : adj[v]) { cout << "-> " << x << " "; } cout << endl; }}// A DFS function to traverse the graph and check for star topologybool DFS(int node, vector<int> adj[], vector<bool>& visited, vector<int>& degree, int V) { visited[node] = true; degree[node] = adj[node].size(); for (int v : adj[node]) { if (!visited[v]) { DFS(v, adj, visited, degree, V); } } if (node != 0 && degree[node] != 1 && degree[node] != V-1) { // If a non-central node has a degree other than 1, it is not a star return false; } if (node == 0 && degree[node] != V-1) { // If the central node does not have degree V-1, it is not a star return false; } return true;}// Function to check if the graph represents a star topologyvoid checkStarTopology(vector<int> adj[], int V, int E) { vector<bool> visited(V, false); vector<int> degree(V, 0); // Start DFS from node 0 bool isStar = DFS(0, adj, visited, degree, V); if (isStar) { cout << "YES" << endl; } else { cout << "NO" << endl; }}int main() { // Graph 1 int V = 5, E = 4; vector<int> adj1[V]; addEdge(adj1, 0, 1); addEdge(adj1, 0, 2); addEdge(adj1, 0, 3); addEdge(adj1, 0, 4); checkStarTopology(adj1, V, E); // Graph 2 V = 4, E = 4; vector<int> adj2[V]; addEdge(adj2, 0, 1); addEdge(adj2, 0, 2); addEdge(adj2, 2, 3); addEdge(adj2, 3, 1); checkStarTopology(adj2, V, E); return 0;} |
Java
import java.util.ArrayList;import java.util.Arrays;import java.util.List;public class StarTopologyChecker { // A utility function to add an edge in an undirected graph.static void addEdge(List<Integer>[] adj, int u, int v) { adj[u].add(v); adj[v].add(u);}// A utility function to print the adjacency list representation of graphstatic void printGraph(List<Integer>[] adj, int V) { for (int v = 0; v < V; ++v) { System.out.print("Adjacency list of vertex " + v + "\n head "); for (int x : adj[v]) { System.out.print("-> " + x + " "); } System.out.println(); }}// A DFS function to traverse the graph and check for star topologystatic boolean DFS(int node, List<Integer>[] adj, boolean[] visited, int[] degree, int V) { visited[node] = true; degree[node] = adj[node].size(); for (int v : adj[node]) { if (!visited[v]) { DFS(v, adj, visited, degree, V); } } if (node != 0 && degree[node] != 1 && degree[node] != V-1) { // If a non-central node has a degree other than 1, it is not a star return false; } if (node == 0 && degree[node] != V-1) { // If the central node does not have degree V-1, it is not a star return false; } return true;}// Function to check if the graph represents a star topologystatic void checkStarTopology(List<Integer>[] adj, int V, int E) { boolean[] visited = new boolean[V]; int[] degree = new int[V]; // Start DFS from node 0 boolean isStar = DFS(0, adj, visited, degree, V); if (isStar) { System.out.println("YES"); } else { System.out.println("NO"); }}public static void main(String[] args) { // Graph 1 int V = 5, E = 4; List<Integer>[] adj1 = new ArrayList[V]; for (int i = 0; i < V; i++) { adj1[i] = new ArrayList<>(); } addEdge(adj1, 0, 1); addEdge(adj1, 0, 2); addEdge(adj1, 0, 3); addEdge(adj1, 0, 4); checkStarTopology(adj1, V, E); // Graph 2 V = 4; E = 4; List<Integer>[] adj2 = new ArrayList[V]; for (int i = 0; i < V; i++) { adj2[i] = new ArrayList<>(); } addEdge(adj2, 0, 1); addEdge(adj2, 0, 2); addEdge(adj2, 2, 3); addEdge(adj2, 3, 1); checkStarTopology(adj2, V, E);}} |
Python3
# Python3 program to check if the given graph# represents a star topology using DFS# A utility function to add an edge in an# undirected graph.def addEdge(adj, u, v): adj[u].append(v) adj[v].append(u)# A utility function to print the adjacency list# representation of graphdef printGraph(adj, V): for v in range(V): print("Adjacency list of vertex ",v,"\n head ") for x in adj[v]: print("-> ",x,end=" ") printf()# A DFS function to traverse the graph and check for star topologydef DFS(node, adj, visited, degree, V): visited[node] = True degree[node] = len(adj[node]) for v in adj[node]: if not visited[v]: DFS(v, adj, visited, degree, V) if node != 0 and degree[node] != 1 and degree[node] != V-1: # If a non-central node has a degree other than 1, it is not a star return False if node == 0 and degree[node] != V-1: # If the central node does not have degree V-1, it is not a star return False return True# Function to check if the graph represents a star topologydef checkStarTopology(adj, V, E): visited = [False] * V degree = [0] * V # Start DFS from node 0 isStar = DFS(0, adj, visited, degree, V) if isStar: print("YES") else: print("NO")# Driver code# Graph 1V, E = 5, 4adj1=[[] for i in range(V)]addEdge(adj1, 0, 1)addEdge(adj1, 0, 2)addEdge(adj1, 0, 3)addEdge(adj1, 0, 4)checkStarTopology(adj1, V, E)# Graph 2V, E = 4, 4adj2=[[] for i in range(V)]addEdge(adj2, 0, 1)addEdge(adj2, 0, 2)addEdge(adj2, 2, 3)addEdge(adj2, 3, 1)checkStarTopology(adj2, V, E) |
C#
using System;using System.Collections.Generic;class Program{// A utility function to add an edge in an undirected graphstatic void addEdge(List<int>[] adj, int u, int v){adj[u].Add(v);adj[v].Add(u);} // A utility function to print the adjacency list representation of graphstatic void printGraph(List<int>[] adj, int V){ for (int v = 0; v < V; v++) { Console.Write("Adjacency list of vertex " + v + "\n head "); foreach (int x in adj[v]) Console.Write("-> " + x); Console.WriteLine(); }}// A DFS function to traverse the graph and check for star topologystatic bool DFS(int node, List<int>[] adj, bool[] visited, int[] degree, int V){ visited[node] = true; degree[node] = adj[node].Count; foreach (int v in adj[node]) { if (!visited[v]) { if (!DFS(v, adj, visited, degree, V)) return false; } } if (node != 0 && degree[node] != 1 && degree[node] != V - 1) { // If a non-central node has a degree other than 1, it is not a star return false; } if (node == 0 && degree[node] != V - 1) { // If the central node does not have degree V-1, it is not a star return false; } return true;}// Function to check if the graph represents a star topologystatic void checkStarTopology(List<int>[] adj, int V, int E){ bool[] visited = new bool[V]; int[] degree = new int[V]; // Start DFS from node 0 bool isStar = DFS(0, adj, visited, degree, V); if (isStar) Console.WriteLine("YES"); else Console.WriteLine("NO");}// Driver code// Graph 1static void Main(string[] args){ int V = 5, E = 4; List<int>[] adj1 = new List<int>[V]; for (int i = 0; i < V; i++) adj1[i] = new List<int>(); addEdge(adj1, 0, 1); addEdge(adj1, 0, 2); addEdge(adj1, 0, 3); addEdge(adj1, 0, 4); checkStarTopology(adj1, V, E); // Graph 2 V = 4; E = 4; List<int>[] adj2 = new List<int>[V]; for (int i = 0; i < V; i++) adj2[i] = new List<int>(); addEdge(adj2, 0, 1); addEdge(adj2, 0, 2); addEdge(adj2, 2, 3); addEdge(adj2, 3, 1); checkStarTopology(adj2, V, E);}} |
Javascript
// Define a function to add an edge in an undirected graph.function addEdge(adj, u, v) { adj[u].push(v); adj[v].push(u);}// Define a function to print the adjacency list representation of graph.function printGraph(adj, V) { for (let v = 0; v < V; ++v) { console.log("Adjacency list of vertex " + v); let str = "head"; for (let i = 0; i < adj[v].length; ++i) { str += " -> " + adj[v][i]; } console.log(str); }}// Define a DFS function to traverse the graph and check for star topology.function DFS(node, adj, visited, degree, V) { visited[node] = true; degree[node] = adj[node].length; for (let v of adj[node]) { if (!visited[v]) { DFS(v, adj, visited, degree, V); } } if (node != 0 && degree[node] != 1 && degree[node] != V - 1) { // If a non-central node has a degree other than 1, it is not a star return false; } if (node == 0 && degree[node] != V - 1) { // If the central node does not have degree V-1, it is not a star return false; } return true;}// Define a function to check if the graph represents a star topology.function checkStarTopology(adj, V, E) { let visited = new Array(V).fill(false); let degree = new Array(V).fill(0); // Start DFS from node 0 let isStar = DFS(0, adj, visited, degree, V); if (isStar) { console.log("YES"); } else { console.log("NO"); }}// Main functionfunction main() { // Graph 1 let V = 5, E = 4; let adj1 = new Array(V); for (let i = 0; i < V; ++i) { adj1[i] = []; } addEdge(adj1, 0, 1); addEdge(adj1, 0, 2); addEdge(adj1, 0, 3); addEdge(adj1, 0, 4); checkStarTopology(adj1, V, E); // Graph 2 V = 4, E = 4; let adj2 = new Array(V); for (let i = 0; i < V; ++i) { adj2[i] = []; } addEdge(adj2, 0, 1); addEdge(adj2, 0, 2); addEdge(adj2, 2, 3); addEdge(adj2, 3, 1); checkStarTopology(adj2, V, E);}// Call the main function to execute the program.main(); |
Output
YES NO
Time Complexity: O(V + E) where V and E are the numbers of vertices and edges in the graph respectively.
Auxiliary Space: O(V + E)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!