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

मान लीजिए कि हमारे पास 1 से n तक लेबल किए गए n नोड्स के साथ एक अप्रत्यक्ष स्टार ग्राफ है। जैसा कि हम जानते हैं कि एक स्टार ग्राफ एक ग्राफ होता है जहां एक केंद्र नोड होता है और बिल्कुल n - 1 किनारे होते हैं जो केंद्र नोड को हर दूसरे नोड से जोड़ते हैं। हमें दिए गए स्टार ग्राफ का केंद्र ढूंढना है।

तो, अगर इनपुट पसंद है

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

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

• देखा :=एक नया सेट

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

  • अगर आप दिख रहे हैं, तो

    • आप पर लौटें

  • अगर v दिख रहा है, तो

    • वापसी वी

  • आपको सीन में डालें

  • देखा में v डालें

उदाहरण

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

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