स्टार ग्राफ की जांच

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

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

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

इनपुट: आसन्नता मैट्रिक्स: 0 1 1 1 1 0 0 0 1 0 0 0 1 0 0 0 आउटपुट: यह एक स्टार ग्राफ है।

एल्गोरिदम

checkStarGraph(graph)

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

आउटपुट: ग्राफ स्टार ग्राफ होने पर सच।

शुरू     degOneVert := 0 और degNminOneGraph := 0     यदि ग्राफ में केवल एक शीर्ष है, तो       वापस करें सच, यदि कोई सेल्फ-लूप नहीं है     अन्यथा यदि ग्राफ में दो शीर्ष हैं, तो       वापस करें सच यदि दो शीर्षों के बीच केवल एक किनारा है     अन्यथा       ग्राफ में सभी शीर्ष i के लिए, करें         degree := 0         i के साथ आसन्न सभी शीर्ष j के लिए, करें           degree := degree + 1         किया         यदि degree = 1, तो           degOneVert := degOneVert + 1         अन्यथा यदि degree = n-1, तो           degNminOneGraph := degNminOneGraph + 1       किया     यदि degOneVert = n-1, और degNminOneGraph = 1, तो       वापस करें सच     अन्यथा गलत वापस करें अंत

उदाहरण

#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;       //प्रारंभ में डिग्री 1 वाले शीर्ष और डिग्री n - 1 वाले शीर्ष 0 हैं     if (NODE == 1)       //जब केवल एक नोड हो       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++) {       //2 से अधिक ग्राफ के लिए       int degree = 0;       for (int j = 0; j < NODE; j++)       //शीर्ष i के लिए डिग्री गिनें         if (graph[i][j])           degree++;       if (degree == 1)         degOneVert++;       else if (degree == NODE-1)         degVert++;     }     //जब केवल एक शीर्ष डिग्री n-1 का हो, और अन्य सभी शीर्ष डिग्री 1 के हों, तो यह स्टार ग्राफ है     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.