그래프 기초

1. 그래프(Graph)

1) 그래프의 구성 요소

• 정점(Node / Vertex) 특별한 하나의 객체
• 간선(Edge) 정점을 연결하는 선. 두 노드 간의 관계를 나타냄. 방향이나 비중을 나타낼수있음.
• 그래프(Graph) 정점과 간선의 집합으로 이루어진 구조.

2) 그래프 관련 용어

• 인접(adjacent) : 두 정점이 간선으로 연결되어 있는 경우
• 차수(degree) : 정점에 연결된 간선의 수
• 진입 차수(in-degree) : 해당 정점으로 향하는 간선의 수
• 진출 차수(out-degree) : 해당 정점에서 나가는 간선의 수
• 경로(path) : 한 정점에서 다른 정점으로 이어지는 정점들의 리스트
• 경로 길이(path length) : 경로를 구성하는 간선의 수
• 단순 경로(simple path) : 모두 다른 정점으로 구성된 경로
• 사이클(cycle) : 한 정점에서 시작해 같은 정점으로 돌아올 수 있는 경로

3) 그래프를 구현하는 방법

예시 1) x번 노드에서 y번 노드로 가는 간선이 있다면 graph[x][y] 가 True, 아니면 False.

n = 4 # 전체 노드의 갯수
graph = [[False] * n for _ in range(n)] # 그래프 초기 설정
graph[0][2] = True # 0번 노드에서 2번 노드로 가는 간선이 존재한다.

간선에 비중이 있는 경우는 graph[x][y] 에 간선의 비중을 넣어준다.

간혹 문제에서 “시작과 끝이 같은” 간선이 여러 개 주어지는 경우 아래의 방법을 사용하면 중복 간선 정보가 덮어써지기 때문에 주의해야한다.

n = 4 # 전체 노드의 갯수
graph = [[0] * n for _ in range(n)] # 그래프 초기 설정
graph[0][2] = 3 # 0번 노드에서 2번 노드로 가는, 비중이 3인 간선이 존재한다.

예시 2)x번 노드에서 y번 노드로 가는 간선이 있다면 graph[x] 안에 y 를 추가

graph = [
    [1],
    [0, 2],
    [1, 3],
    [2],
]

# 1번 노드에서 3번 노드로 가는 간선을 추가하려면?
graph[1].append(3)

비중이 있는 간선은 tuple 을 이용할수있음.

graph = [
    [(1, 3)],
    [(0, 3), (2, 1)],
    [(1, 1), (3, 4)],
    [(2, 4)],
]

# 1번 노드에서 3번 노드로 가는 비용이 7인 간선을 추가하려면?
graph[1].append((3, 7))