그래프 이론과 간단한 응용 (Application of Graph Theory)

실제 데이터를 추상화하고 그것을 Modeling을 하는 데 있어서 그래프 형태로 표현하는 것이 유용하다.

 

여기서 말하는 그래프는 이런 그래프를 말하는 것이다. 행렬 배운 세대는 다 아는 그것..

 

출처 : https://ko.wikipedia.org/wiki/%EA%B7%B8%EB%9E%98%ED%94%84_%EC%9D%B4%EB%A1%A0

C언어라면 그래프를 구현하기 위해서 이중배열을 사용하는 등 복잡한 과정을 거쳐야하지만 파이썬의 경우 Dictionary를 이용해서 간단하게 구현할 수 있다.

 

아래는 『모두의 파이썬x알고리즘』의 예제이다. 실제 모델링 대상인 미로와 '서로아는 친구'문제의 그래프는 해당 도서를 참고하길 바란다.

 

maze = {
    'a' : ['e'],
    'b' : ['c','f'],
    'c' : ['b','d'],
    'd' : ['c'],
    'e' : ['a','i'],
    'f' : ['b','g','j'],
    'g' : ['f', 'h'],
    'h' : ['g','l'],
    'i' : ['e','m'],
    'j' : ['f', 'k', 'n'],
    'k' : ['j','o'],
    'l' : ['h','p'],
    'm' : ['i','n'],
    'n' : ['m','j'],
    'o' : ['k'],
    'p' : ['l']
}
#미로의 구현

def solve_maze(g, start, end):
    #g는 그래프, start는 시작점, end는 끝
    qu = []
    done = set()
    
    qu.append(start)
    done.add(start)
    
    while qu:
        p = qu.pop(0)
        v = p[-1]    #v = p의 마지막 부분이다.
        if v == end:
            return p
        for x in g[v]:    #마지막 부분에 연결된 부분 중
            if x not in done:
                qu.append(p+x)    #이동 경로에 새로운 꼭짓점을 추가한다.
                done.add(x)
        
        
print(solve_maze(maze, 'a', 'p'))

 

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 print_all_freinds(g, start):
    #g는 그래프, start는 모든 친구를 찾을 대상
    qu = []
    done = set()
    inti = 0
    qu.append((start, 0))
    done.add(start)
    
    while(qu):
        while(qu):
            (p,inti) = qu.pop(0)
            print((p, inti))
            for x in g[p]:
                if x not in done :
                    qu.append((x, inti + 1))
                    done.add(x)
                
print_all_freinds(fr_info, 'Summer')
print()
print_all_freinds(fr_info, 'Jerry')