Chương trình tìm tâm của đồ thị hình sao bằng Python

Giả sử chúng ta có một đồ thị sao vô hướng với n nút có nhãn từ 1 đến n. Như chúng ta đã biết, đồ thị hình sao là một đồ thị trong đó có một nút chính giữa và chính xác n - 1 cạnh nối nút trung tâm với mọi nút khác. Chúng ta phải tìm tâm của biểu đồ hình sao đã cho.

Vì vậy, nếu đầu vào giống như

thì đầu ra sẽ là 3 vì 3 ở trung tâm.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• đã thấy:=một tập hợp mới

• đối với mỗi cạnh (u, v) trong biểu đồ, thực hiện

  • nếu bạn được nhìn thấy, thì

    • trả lại bạn

  • nếu v được nhìn thấy, thì

    • trở lại v

  • chèn u vào thấy

  • chèn v vào đã thấy

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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))

Đầu vào

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

Đầu ra

3