पायथन में स्टार ग्राफ का केंद्र ज्ञात करने का प्रोग्राम

मान लीजिए हमारे पास n नोड्स वाला एक अनिर्देशित स्टार ग्राफ है जो 1 से n तक लेबल किए गए हैं। जैसा कि हम जानते हैं, एक स्टार ग्राफ एक ऐसा ग्राफ है जहां एक केंद्र नोड होता है और ठीक n-1 किनारे होते हैं जो केंद्र नोड को हर दूसरे नोड से जोड़ते हैं। हमें दिए गए स्टार ग्राफ का केंद्र ढूंढना है।

इसलिए, यदि इनपुट इस तरह है

तो आउटपुट 3 होगा क्योंकि 3 केंद्र में है।

इसे हल करने के लिए, हम निम्न चरणों का पालन करेंगे:

• seen := एक नया सेट

• ग्राफ में प्रत्येक किनारे (u,v) के लिए, करें

  • यदि u seen में है, तो

    • u वापस करें

  • यदि v seen में है, तो

    • v वापस करें

  • u को seen में डालें

  • v को seen में डालें

उदाहरण

बेहतर समझ के लिए निम्न कार्यान्वयन देखें:

def solve(graph):
    seen = set()
    for u, v in graph:
        if u in seen:
            return u
        if v in seen:
            return v
        seen.add(u)
        seen.add(v)

graph = [(1,3),(2,3),(4,3),(5,3),(6,3)]
print(solve(graph))

इनपुट

[(1,3),(2,3),(4,3),(5,3),(6,3)]

आउटपुट

3