Check if the given graph represents a Star Topology

0 0 17 minutes read

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 graph
void 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 topology
void checkStarTopology(vector<int> adj[], int V, int E)
{
    bool isStar = checkStarTopologyUtil(adj, V, E);
    if (isStar) {
        cout << "YES" << endl;
    }
    else {
        cout << "NO" << endl;
    }
}
 
// Driver code
int 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 graph
def 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 topology
def checkStarTopology(adj, V, E):
 
    isStar = checkStarTopologyUtil(adj, V, E)
    if (isStar):
        print("YES")
 
    else:
        print("NO" )
 
# Driver code
 
# Graph 1
V, E = 5, 4
adj1=[[] 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 2
V, E = 4, 4
adj2=[[] 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 graph
function 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 topology
function 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 graph
void 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 topology
bool 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 topology
void 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 graph
static 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 topology
static 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 topology
static 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 graph
def 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 topology
def 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 topology
def 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 1
V, E = 5, 4
adj1=[[] 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 2
V, E = 4, 4
adj2=[[] 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 graph
static 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 graph
static 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 topology
static 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 topology
static 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 1
static 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 function
function 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 zambiatek!