[Python] 그래프 알고리즘 - 친구의 친구찾기

모든 친구 찾기 알고리즘

def print_all_friends(g, start):
    qu = [] #처리해야 할 사람들 저장
    done = set() #이미 큐에 추가한 사람들을 집합에 기록(중복방지)

    qu.append(start)
    done.add(start)

    while qu: #큐에 처리할 사람이 남아있는 동안에 
        p = qu.pop(0)
        print(p)
        for x in g[p]: #그의 친구들 중에
            if x not in done: #아직 큐에 추가된적 없는 사람을
                qu.append(x)
                done.add(x)

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']
}

print_all_friends(fr_info, 'Summer')
print()
print_all_friends(fr_info, 'Jerry')

 

모든 친구를 찾아서 친밀도를 계산하는 알고리즘

def print_all_friends(g, start):
    qu = []
    done = set()#중복방지

    qu.append((start, 0))#(사람이름, 친밀도) 튜플로 묶어 처리

    done.add(start)#집합에 추가

    while qu:
        (p, d) = qu.pop(0)#큐에서 (사람이름, 친밀도)를 각각 꺼냄
        print(p, d)
        for x in g[p]:#친구들 중에
            if x not in done:#아직 큐에 추가된 적이 없는 사람을
                qu.append((x, d + 1))#친밀도 1 증가시켜 큐에 추가
                done.add(x)#집합에도 추가

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']
}

print_all_friends(fr_info, 'Summer')
print()
print_all_friends(fr_info, 'Jerry')