그래프(Graph)

그래프란?

노드와 간선으로 이루어진 자료구조

그래프의 종류

- 무방향 그래프(Undirected Graph): 방향성이 없고 노드(정점)이 연결된 그래프

- 방향 그래프(Directed Graph): 무방향 그래프에서 방향성이 추가된 그래프

- 완전 그래프(Complete Graph): 각 정점에서 다른 모든 정점을 연결하여 최대 간선 수를 가진 그래프

  -> 정점이 n개인 무방향 그래프에서는 최대 간선 수 = n(n-1)/2

  -> 정점이 n개인 방향 그래프에서 최대 간선 수 = n(n-1)

- 가중(치) 그래프(Weight Graph): 간선에 가중치를 담아서 표현(방향 여부 상관X)

- 부분 그래프(Sub Graph): 일부 정점과 간선으로 구성된 그래프(가중치 그래프에서 조금 떼어낸 그래프)

 

그래프의 집합 표현

- 정점의 집합을 V(G), 간선의 집합을 E(G)로 표현한다.

- 방향성이 없는 경우 괄호로 묶고, 방향성이 있는 경우 부등호로 묶고, 간선의 시작 부분을 먼저 표현한다.

  -> V(그래프이름) = {1, 2, 3, 4}

  -> E(그래프이름) = {(1, 2), (1, 3), (2, 3), (3, 4)}

 

그래프의 구현 방법

- 인접 행렬 기반

  -> 그래프의 연결 관계를 2차원 배열로 나타내는 방식

  -> 노드 i와 노드 j의 연결 여부에 따라 arr[i][j]의 값이 정해짐. (가중 그래프: 연결 - 가중값, 연결X - INF(무한의 비용), 자신 - 0 일반 그래프: 연결 - 1, 연결X - INF, 자신 - 0)

  -> 장점: 구현이 쉽다. 둘의 연결 여부를 확인 할 때 시간 복잡도 O(1). arr[i][j]값 확인만 하면 되기 때문. 

  -> 단점: 노드 i에 연결된 노드가 어떤 노드가 있는지를 확인하려면 arr[i][0]~arr[i][N]을 전부 방문해봐야 함. O(N)의 시간이 소요됨.

INF = 999999999  # 무한의 비용
graph = [
    [0, 2, 3, INF, INF],
    [2, 0, 15, 2, INF],
    [3, 15, 0, INF, 13],
    [INF, 2, INF, 0, 9],
    [INF, INF, 13, 9, 0],
]

print(graph)

- 인접 리스트 기반

  -> 그래프의 연결 관계를 연결 리스트로 나타내는 방식

  -> 장점: 연결된 정보만 저장하므로 메모리를 효율적으로 사용한다. 노드 i에 어떤 노드가 연결되어 있는지 확인이 빠르다.

  -> 단점: 특정 두 노드가 연결되어 있는지 확인이 느리다.

graph_list = [[] for _ in range(6)]

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

# 노드 1에 연결된 노드 정보 저장(노드, 거리)
graph_list[1].append((3, 2))

# 노드 2에 연결된 노드 정보 저장(노드, 거리)
graph_list[2].append((3, 1))

# 노드 3에 연결된 노드 정보 저장(노드, 거리)
graph_list[3].append((4, 4))
graph_list[3].append((5, 8))

# 노드 4에 연결된 노드 정보 저장(노드, 거리)
graph_list[4].append((5, 6))

# 노드 5에서 뻗어나가는건 없음.
print(graph_list)