파이썬에서 별 그래프의 중심을 찾는 프로그램

<시간/>

1에서 n까지 레이블이 지정된 n개의 노드가 있는 하나의 무방향 스타 그래프가 있다고 가정합니다. 우리가 알다시피 스타 그래프는 중심 노드가 하나이고 중심 노드를 다른 모든 노드와 연결하는 모서리가 정확히 n - 1개인 그래프입니다. 주어진 별 그래프의 중심을 찾아야 합니다.

따라서 입력이 다음과 같으면

3이 중앙에 있으므로 출력은 3이 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

본 :=새로운 세트
그래프의 각 모서리(u,v)에 대해 수행
- u가 본 경우
  - 돌아오다
- v가 표시되면
  - 리턴 v
- 본에 u를 삽입하십시오
- 본에 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)]