MST

트리는 방향 그래프인가? 무방향 그래프인가?

질문의 배경 최근 면접스터디를 진행 중인데요. 자료구조와 알고리즘 파트를 진행하면서 트리와 그래프의 차이, 이진 탐색 트리와 완전 이진 트리에 대한 질문이 나오면서 얘네한테 방향성이랄 것이 있는지에 대한 토론을 했답니다. 명확하게 결론이 날 줄 알았는데 구글링을 해 보니 그렇지 않았습니다. 한 다섯 개 정도의 블로그에서는 방향이 있다고 하고, 네 개 정도 블로그에서는 방향이 없다고 하더라고요. 진짜에요 이럴 수가… 아니 이런 Mr.애매모호가 싫어서 컴퓨터공학 왔다고 결론을 후다닥 말씀드리도록 하겠습니다. 트리는 방향 그래프로 볼 수도 있고, 무방향 그래프로 볼 수도 있다. 이딴 게 결론? 입니다. 정말 열받는 부분이죠? 이유에 대해 알아봅시다. 그래프 이론에서의 “트리” In graph theory, a..