स्टार ग्राफ के लिए जाँच करें

एक ग्राफ दिया गया है; हमें जांचना है कि दिया गया ग्राफ स्टार ग्राफ है या नहीं।

ग्राफ को पार करते हुए, हमें यह पता लगाना है कि शीर्षों की संख्या एक है, और शीर्षों की संख्या, जिनकी डिग्री n-1 है। (यहाँ n दिए गए ग्राफ़ में शीर्षों की संख्या है)। जब डिग्री 1 वाले शीर्षों की संख्या n-1 है और डिग्री (n-1) वाले कई शीर्षों की संख्या एक है, तो यह एक तारा ग्राफ़ है।

इनपुट और आउटपुट

Input:
The adjacency matrix:
0 1 1 1
1 0 0 0
1 0 0 0
1 0 0 0

Output:
It is a star graph.

एल्गोरिदम

checkStarGraph(graph)

इनपुट: दिया गया ग्राफ़.

आउटपुट: सही है जब ग्राफ़ एक स्टार ग्राफ़ है।

Begin
   degOneVert := 0 and degNminOneGraph := 0
   if graph has only one vertex, then
      return true, if there is no self-loop
   else if graph has two vertices, then
      return true if there is only one vertex between two vertices
   else
      for all vertices i in the graph, do
         degree := 0
         for all vertices j, adjacent with i, do
            degree := degree + 1
         done
         if degree = 1, then
            degOneVert := degOneVert + 1
         else if degree = n-1, then
            degNminOneGraph := degNminOneGraph + 1
      done

   if degOneVert = n-1, and degNminOneGraph = 1, then
      return true
   otherwise return false
End

उदाहरण

#include<iostream>
#define NODE 4
using namespace std;

int graph[NODE][NODE] = {
   {0, 1, 1, 1},
   {1, 0, 0, 0},
   {1, 0, 0, 0},
   {1, 0, 0, 0}
};

bool checkStarGraph() {
   int degOneVert = 0, degVert = 0;    //initially vertex with degree 1 and with degree n - 1 are 0
   if (NODE == 1)    //when there is only one node
      return (graph[0][0] == 0);

   if (NODE == 2)  
      return (graph[0][0] == 0 && graph[0][1] == 1 && graph[1][0] == 1 && graph[1][1] == 0 );

   for (int i = 0; i < NODE; i++) {    //for graph more than 2
      int degree = 0;
      for (int j = 0; j < NODE; j++)    //count degree for vertex i
         if (graph[i][j])
            degree++;
      if (degree == 1)
         degOneVert++;
      else if (degree == NODE-1)
         degVert++;
   }
   //when only vertex of degree n-1, and all other vertex of degree 1, it is a star graph
   return (degOneVert == (NODE-1) && degVert == 1);
}

int main() {
   if(checkStarGraph())
      cout << "It is a star graph.";
   else
     cout << "It is not a star graph.";
}

आउटपुट

It is a star graph.