S532 Graph

개념 정리

1) 그래프

• 그래프란?
  • 노드와 엣지(간선)으로 이루어진 자료구조.

  • 

  • 트리와 다른 점: 계층이 존재하지 않는다. (=루트노드 x)
  • 장점: object간 관계를 표현할 때 유용하다. 예를 들어 SNS나 운송 시스템 같은 경우 적합하다.
• 그래프 코드 구현 시

  

  인접행렬(Adjacency Matrix) 인접리스트 (Adjacency List) 두가지로 구현 가능하다.
  • 인접행렬(Adjacency Matrix)
    • 연결된 여부는 1로 (만약 가중치가 1보다 크면 1보다 큰 값으로) 연결되지 않으면 0으로 표현한다.
    • 메모리 차지가 인접리스트보다 많다. 시간 복잡도 O(n^2) 차지.
    • 노드간 엣지가 존재하는지 찾기 위해서 시간 복잡도가 O(1)으로 인접 리스트보다 좋다.
  • 인접리스트 (Adjacency List)
    • 딕셔너리 형태로 각 노드 (key로 표현)와 연결된 노드의 값을 value로 넣는다.
    • 메모리 차지가 인접 리스트보다 좋다. 시간 복잡도 O(n+m) 차지. (m은 각 노드가 연결된 노드 수)
    • 엣지 존재 여부의 시간 복잡도는 O(n)으로 인접 행렬보다 안 좋다.

 

2) 그래프의 유형

1. 방향성
   • 한쪽 방향성(one-way)
   • 양방향성(bidirectional)
     

     

     한쪽 방향성(one-way)

     

     양방향성(bidirectional)

     방향성 그래프는 순서가 있으므로 마지막 노드(leaf node)가 존재한다.
2. 무방향성
   • 무방향성 (undirected)그래프는 상호 교환 관계이다.

     

     무방향성 (undirected)

     화살표가 따로 없는 것을 확인 가능하다.

해야할 것

1) 그래프가 실제 활용되는 예시 찾아보기
2) 그래프로 코드 작성해보기

1) 최단거리 알고리즘, 네트워크 플로우, SNS, 포털 사이트 검색 엔진

2)

 

'''
그래프 경로 찾기 코드 구현 예시

connection_info = {
            'A': ['B', 'C'],2
            'B': ['C', 'D'],
            'C': ['D'],
            'D': ['C'],
            'E': ['F'],
            'F': ['C']
        }
        
        search_route(connection_info, 'B', 'D')
    출력값:
        ['B', 'C', 'D']
'''

def search_route(connection_info, start_node, end_node, route=[]):
    route = route + [start_node]
    if start_node == end_node:
        return None
    if not connection_info.__contains__(start_node):
        return None
    for node in connection_info[start_node]:
        if end_node in connection_info[node]:
            route = route + [node] + [end_node]
            return route
        elif end_node not in node:
            return None
        else:
            route = route + [node]
            return route