[자료 구조] 친구의 친구 찾기 / 그래프

그래프 (Graph)

꼭짓점(vertex)과, 그 꼭짓점 사이를 연결한 선(edge)의 집합

파이썬에서는 그래프를 표현할 수 있는 다양한 방법이 있지만, 이 글에서는 딕셔너리와 리스트를 이용한다. 꼭짓점을 key로 정의하고, 직접 연결된 꼭짓점 list를 value로 정의한 딕셔너리를 선언하여 그래프를 표현할 수 있다.

 

fr_info = {
    "Summer": ["John", "Justin", "Mike"],
    "John": ["Summer", "Justin"],
    "Justin": ["John", "Summer", "Mike", "May"],
    "Mike": ["Summer", "Justin"],
    "May": ["Justin", "Kim"],
    "Kim": ["May"],
    "Tom": ["Jerry"],
    "Jerry": ["Tom"]
}

 

친구의 친구 찾기 알고리즘

큐에 앞으로 처리할 사람들을 저장하고, 집합에 이미 처리한 사람들을 저장해가며, 큐에 값이 없을 때까지 처리한다.

그래프에서 연걸된 모든 꼭짓점을 탐색하는 알고리즘으로, 그래프 탐색 알고리즘이라고 부른다.

def all_fr(info_dict, name):
    q = []
    done = set()
    q.append(name)
    done.add(name)

    while q:
        p = q.pop(0)
        for n in info_dict[p]:
            if n not in done:
                q.append(n)
                done.add(n)

 

너비 우선 탐색 (Breadth First Search)
꼭짓점을 큐에서 하나씩 꺼내 처리하고, 그 꼭짓점에 연결된 꼭짓점들을 다시 큐에 추가하면서 그래프를 탐색하는 방법

 

참고 문서

https://velog.io/@gimtommang11/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0%EA%B7%B8%EB%9E%98%ED%94%84