[4.17] 문제 15. 친구의 친구 찾기 - 그래프

문제 15. 친구의 친구 찾기 -그래프

 

그래프

* 꼭짓점 - vertex, 선 - edge

파이썬으로 그래프 표현하기

딕셔너리, 리스트 이용함

graph = {
  'Summer' = ['Mike', 'John', 'Justin'],
  'Mike' = ['Summer', 'Justin'],
  'Justin' = ['Summer', 'Mike', 'John', 'May'],
  'John' = ['Summer', 'Justin'],
  'May' = ['Justin', 'Kim']
  'Kim' = ['May']
  'Tom' = ['Jerry']
  'Jerry' = ['Tom']

}

 

모든 친구 찾기 알고리즘

1차 시도

- 앞으로 처리할 사람을 qu에 추가한다.  - 이미 qu에 추가한 사람의 집합을 done이라고 한다.  - 출발점이 되는 사람을 qu랑 done에 추가한다.  - 꺼내서 출력을 한다.  - 꺼낸 사람의 친구 중에 qu, done에 없는 사람을 골라 qu와 집합 done에 추가한다.  - qu에 남아있으면 다시 반복한다.    (a, x)를 한다고 했을 때 1. qu = [], done = set()   2. qu.append(x) done.add(x)   while qu: value = qu.pop(0) for i in a[value]: if i not in qu and done: qu.append(i) done.add(i) print(i)

def find_frs(a, x):
  qu = []
  done = set()

  qu.append(x)
  done.add(x)

  while qu:
    value = qu.pop(0)
    for i in a[value]:
      if i not in qu and done:
        qu.append(i)
        done.add(i)
        print(i)


g = {
  'Summer' : ['Mike', 'John', 'Justin'],
  'Mike' : ['Summer', 'Justin'],
  'Justin' : ['Summer', 'Mike', 'John', 'May'],
  'John' : ['Summer', 'Justin'],
  'May' : ['Justin', 'Kim'],
  'Kim' : ['May'],
  'Tom' : ['Jerry'],
  'Jerry' : ['Tom']
}

print(find_frs(g, 'Summer'))

아하! for 문에 print i 적어서 무한출력되는 거였음. ㅇㅎㅇㅎ. 

예시 코드

#예시코드
def find_frs(a, x):
  qu = []
  done = set()

  qu.append(x)
  done.add(x)

  while qu:
    value = qu.pop(0)
    #다른 점 1. 
    print(value)
    for i in a[value]:
      if i not in done:
        qu.append(i)
        done.add(i)


g = {
  'Summer' : ['Mike', 'John', 'Justin'],
  'Mike' : ['Summer', 'Justin'],
  'Justin' : ['Summer', 'Mike', 'John', 'May'],
  'John' : ['Summer', 'Justin'],
  'May' : ['Justin', 'Kim'],
  'Kim' : ['May'],
  'Tom' : ['Jerry'],
  'Jerry' : ['Tom']
}

print(find_frs(g, 'Summer'))

친밀감 계산 알고리즘

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))
        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()

연습문제

- 그래프 탐색하는 프로그램 만들기

- 입력 : 그래프

- 출력 : 그래프 요소 나열

오 굿

 

gr = {
  1: [3, 2],
  2: [1, 4, 5], 
  3: [1],
  4: [2],
  5: [2]
}

def search(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)

print(search(gr,1))