[자료구조] Graph(그래프)

그래프(Graph)

데이터들 사이의 연결관계를 표현해주는 자료구조 [ex] 지하철 노선도

정점과 간선을 이용하여 만들어진다.

정점(Vertex): node를 나타냄 / 간선(Edge): 정점을 이어주는 선

그래프의 종류
간선의 방향 여부: 무방향 그래프 / 방향 그래프

간선에 가중치 존재여부: 비가중치 그래프 / 가중치 그래프

무방향 그래프 / 방향그래프

비가중치 그래프 / 가중치 그래프

그래프의 용어

인접 정점(Adjacent vertex): 하나의 정점에서 간선으로 연결되어 있는 정점
차수(degree); 연결된 간선의 개수, 방향그래프의 경우 정점으로 들어오는 간선의 수를 진입차수, 정점에서 나가는 간선의 수는 진출자수라고 한다.

경로(Path): 간선을 타고 갈 수 있는 길

경로의 길이: 경로를 구성하는데 사용된 간선의 수. 최단경로를 구하는 알고리즘에서는 경로의 길이를 최소화 해야 한다.

단순 경로(simple path): 경로 중 반복되는 정점이 없는 경로
사이클(cycle): 단순 경로 중 시작정점과 종료정점이 동일한 경로. 한붓그리기와 같다.

 

인접행렬을 사용한 그래프 구현

2차원 배열로 간선의 정보를 저장한다. 

i 정점에서 j 정점으로 가는 간선의 데이터를 2차원 배열(i,j)위치 값을 넣는 것이다.

만약 가중치 그래프라면 해당 위치에 가중치를 넣는 것이다. 방향 그래프도 방향에 맞춰 인접행렬을 만들면 된다.

장점: 정점 사이의 간선의 정보를 받아오기 위해서는 두 정점의 인덱스만 있으면 된다. 두 노드의 간선의 정보를 확인하거나, 새로운 간선을 추가/제거할 때 시간 복잡도는 O(1)이다.

단점: 간선의 개수와 관게없이 노드의 개수^2만큼의 저장공간이 필요하다. 

노드의 수가 적고, 간선의 수가 많은 밀집그래프일 경우 사용하기 적합하다.

인접 행렬을 사용한 그래프 구현

 

인접리스트를 사용한 그래프 구현

Linked List를 1차원 배열에 저장해 그래프를 구현하는 방법

배열의 각 원소는 하나의 Linked List를 저장하고, 이 Linked List에는 그 노드에 연결된 모든 간선의 정보가 저장한다.

따라서 배열의 길이가 그래프의 노드의 개수가 된다.

장점: 메모리의 사용 효율이 좋다. 시간복잡도는 O(N+E)이다.(N: 배열의길이, E: 간선의수)

단점: 두 노드를 잇는 간선의 정보를 확인하는 것이 복잡하다.

노드의 수가 많고 간선의 개수가 상대적으로 적은 희소그래프에 적합하다.

인접 리스트를 사용한 그래프 구현

예시

위와 같은 무방향 가중치 그래프가 주어진다면, 인접 행렬과 인접 그래프는 아래 코드와 같이 구현할 수 있다.

1) 인접 행렬로 구현하기

INF = 999999999  # 무한

graph = [
    [0, 7, 5],
    [7, 0, INF],
    [5, INF, 0]
]

print(graph)

2) 인접 리스트로 구현하기

graph = [[] for _ in range(3)]  # [[], [], []]

graph[0].append((1, 7))
graph[0].append((2, 5))
graph[1].append((0, 7))
graph[2].append((0, 5))

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