कैसे पता करें कि कोई ग्राफ द्विदलीय है या नहीं?

एक ग्राफ को द्विदलीय ग्राफ कहा जाता है, जब उस ग्राफ के शीर्षों को दो स्वतंत्र सेटों में इस तरह विभाजित किया जा सकता है कि ग्राफ का प्रत्येक किनारा या तो पहले सेट से शुरू होता है और समाप्त होता है दूसरा सेट, या दूसरे सेट से शुरू होता है, पहले सेट से जुड़ा होता है, दूसरे शब्दों में, हम कह सकते हैं कि एक ही सेट में कोई बढ़त नहीं मिल सकती है।

वर्टेक्स कलरिंग का उपयोग करके द्विदलीय ग्राफ की जाँच संभव है। जब एक शीर्ष एक ही सेट में होता है, तो उसका रंग समान होता है, दूसरे सेट के लिए, रंग बदल जाएगा।

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

इनपुट:आसन्नता मैट्रिक्स.0 1 1 1 0 01 0 1 1 01 0 0 1 0 11 1 1 0 1 10 1 0 1 0 10 0 1 1 1 0आउटपुट:ग्राफ द्विदलीय है।

एल्गोरिदम

isBipartite(source)

इनपुट - स्रोत शीर्ष।
आउटपू टी :सच है जब ग्राफ़ द्विदलीय होता है।

एक खाली कतार qu को परिभाषित करना शुरू करें, और एक रंग सूची coloArray शुरू में किसी भी नोड को किसी भी रंग के रंग से रंगा नहीं जाता है, स्रोत के शीर्ष को रंग लाल के रूप में qu में स्रोत जोड़ें जब qu खाली न हो, तो qu से आइटम निकालें और लें यू में अगर कोई सेल्फ-लूप है, तो सभी वर्टिस वी के लिए झूठी वापसी करें, जो कि यू के साथ जुड़ा हुआ है, अगर वी में कोई रंग नहीं है, तो अगर कलरअरे [यू] =लाल, फिर कलरएरे [वी]:=नीला और अगर colorArray [u] =नीला, फिर colorArray [v]:=लाल जोड़ें v कतार में अगर colorArray [v] =colorArray [u], फिर गलत किया गया वापस लौटें trueEnd 

उदाहरण

ग्राफ़ द्विदलीय है।