이코테-chapter5: 그래프란

정리 내용

그래프란

• 노드(node)와 간선(edge)으로 표현되며 이때 노드를 정점(vertex)라고도 말한다.
• 그래프 탐색: 하나의 노드를 시작으로 다수의 노드를 방문하는 것
• 두 노드가 간선으로 연결되어 있다면 두 노드는 인접하다(adjacent)라고 표현한다.
• 프로그래밍에서 그래프는 크게 아래 2가지 방식으로 표현할 수 있다.
  1) 인접 행렬(adjacency matricx): 2차원 배열로 그래프의 연결 관계를 표현하는 방식.
  2) 인접 리스트(adjacency list): 리스트로 그래프의 연결 관계를 표현하는 방식.

인접 행렬(adjacency matrix)

• 2차원 배열에 각 노드가 연결된 각 노드가 연결된 형태.
• 파이썬에서는 2차원 리스트로 구현할 수 있다.
• 연결이 되어 있지 않은 노드끼리는 무한의 비용이라고 작성한다.
• 실제 코드에서 논리적으로 정답이 될 수 없는 큰 값 중에서 9999999999 등의 값으로 초기화하는 경우가 많다.

인접 행렬 예제

inf = 9999999999  # 무한의 비용 선언

# 2차원 리스트를 이용해 인접 행렬 표현.
graph = [
    [0, 7, 5],
    [7, 0, inf],
    [5, inf, 0]
]

print(graph)

인접 리스트

• 파이썬으로 인접 리스트를 이용해 그래프를 표현하고자 할 때에도 단순히 2차원 리스트를 이용하면 된다.

인접 리스트 예제

# 행(row)이 3개인 2차원 리스트로 인접 리스트 표현
graph = [[] for _ in range(3)]

# 노드 0에 연결된 노드 정보 저장(노드, 거리)
graph[0].append((1, 7))
graph[0].append((2, 5))

# 노드 1에 연결된 노드 정보 저장(노드, 거리)
graph[1].append((0, 7))

# 노드2에 연결된 노드 정보 저장(노드, 거리)
graph[2].append((0,5))

print(graph) # [[(1, 7), (2, 5)], [(0, 7)], [(0, 5)]]

출처 && 깃허브

이것이 취업을 위한 코딩 테스트다 with python

github