[알고리즘 설명][Python] 그래프 이론(graph theory)

이 게시글은 CS(컴퓨터공학) 프로그래밍 기초를 어느 정도 알고 있다고 가정하고 아주 간단하게 설명하는 게시글입니다.

혹시나 모르는 부분이 있으면 댓글로 질문해주세요.

 

한 줄 요약 : 그래프는 정점(node)과 간선(edge)로 이루어진 자료 구조입니다. 그리고 그래프는 인접 리스트와 인접 행렬로 구현할 수 있습니다.

 

참고 사이트 : https://csacademy.com/app/graph_editor/

CS Academy

이 사이트를 참고해서 그래프 사진들을 만들었습니다.

 

우선 그래프 자료 구조가 무엇일까요?

https://ko.wikipedia.org/wiki/%EA%B7%B8%EB%9E%98%ED%94%84_(%EC%A1%B0%ED%95%A9%EB%A1%A0)

여기 있는 사이트가 원래 정의(defination)이긴 한데 너무 어렵게 묘사되어 있습니다.

그래프를 처음 보는 사람들은 바로 접게 만들도록 만들어졌습니다.

 

그러나 그래프는 아주 기초만 보면 "그래프는 정점과 간선의 모음"입니다. 이게 끝입니다.

여기서 동그라미로 되어 있는 것을 정점(node)라고 부르고, node끼리 연결되어 있는 선을 간선(edge)라고 부릅니다.

2번 노드와 3번 노드에 연결된 간선에 숫자 1이 있던데 이것이 바로 값(value)입니다.

값(value)은 node와 edge에 적용할 수 있습니다.

놀랍게도 이것도 그래프가 됩니다! 간선이 없지만 정점 1개라도 있으면 그래프가 성립됩니다!

이건 훗날 연결 요소를 설명할 때 필요한 정보이니 참고해주세요.

우선 이 그래프를 어떻게 코드로 표현해야 할까요?

아래 Python 소스 코드를 통해 위 그래프를 구현하도록 합니다.

# 1번째 방법
graph[start] = [(end, value)]
# 2번째 방법
graph[start][end] = value

이게 끝입니다.

단방향 간선에서 시작 정점 start에서 출발하여 끝 정점 end에 도착하여 그 간선의 값이 value일 때 위 코드대로 구현하면 끝입니다. 정말 쉽죠?

 

이제 그래프를 선언해야겠죠?

위에 4개의 정점이 간선이 없는 상태로 있습니다.

이 때 이것을 아래와 같은 코드로 그래프를 선언하면 됩니다.

N = 4 # node 개수

# 1번째 방법
graph:list = [[] for _ in range(N + 1)]
# 2번째 방법
graph:list = [[0 for _ in range(N + 1)] for _ in range(N + 1)]

이렇게 하시면 됩니다.

여기서 1번째 방법을 인접 리스트(Adjacency List), 2번째 방법을 인접 행렬(Adjacency Matrix)라고 부릅니다.

메모리 최적화가 더 중요하면 1번째 방법, 메모리가 아주 풍부하여 시간 최적화가 필요하면 2번째 방법을 사용하면 됩니다.

보통 1번째 방법을 더 많이 사용합니다.

이렇게 되어 있는 그래프가 있습니다.

이 때 아래와 같이 구현하면 됩니다.

[인접 리스트 방식]

N = 4 # node 개수

# 인접 리스트 선언
graph:list = [[] for _ in range(N + 1)]

# graph[start].append((end, value))
graph[1].append((2, 3))
graph[1].append((3, 2))
graph[2].append((4, 5))
graph[3].append((1, 4))
graph[4].append((1, 2))
graph[4].append((3, 1))

[인접 행렬 방식]

N = 4 # node 개수

# 인접 행렬 선언
graph:list = [[0 for _ in range(N + 1)] for _ in range(N + 1)]

# graph[start][end] = value
graph[1][2] = 3
graph[1][3] = 2
graph[2][4] = 5
graph[3][1] = 4
graph[4][1] = 2
graph[4][3] = 1

 

이렇게 해서 그래프 정보를 기입할 수 있습니다.

 

그런데 잘 보시면 간선에서 화살표 있는 것이 있고 없는 것이 있어요.

자, 아래의 사진을 확인해주세요.

이렇게 화살표가 하나로 이루어져 있는 것을 단방향 그래프 혹은 유방향 그래프라고 부릅니다.

코드로 표현하면 다음과 같습니다.

graph[1][2] = 3

참고로 2번 정점 -> 1번 정점으로 가는 간선의 값을 3이 아닌 다른 값(예시 : 4)으로 넣을 수도 있습니다.

현실적인 예시를 들면 서울 -> 부산으로 가는 비용은 약 5만원이나 부산 -> 서울로 가는 비용은 약 51000원으로 가격을 매길 수 있습니다.

위 사진처럼 방향이 없는 그래프가 있습니다. 이 그래프를 양방향 그래프 혹은 무방향 그래프라고 부릅니다.

코드로 표현하면 다음과 같습니다.

graph[1][2] = 3
graph[2][1] = 3

잘 보시면 start -> end와 end -> start의 value가 서로 같은 것을 알 수 있습니다.

즉, 무방향 그래프는 단방향 그래프에서 2개의 간선이 값이 같은 경우와 동일한 것을 알 수 있습니다.

현실적인 예시를 들면 서울 -> 부산으로 가거나 부산 -> 서울로 가거나 모두 5만원으로 동일하게 받는다고 보시면 됩니다.

이건 생각보다 엄청 자주 나오므로 반드시 알아야 합니다.

 

이렇게 그래프 이론은 사실 별거 아닙니다.

그걸 응용하는 것이 어려운 것 뿐입니다ㅎㅎ...

그냥 정점들과 start -> end + value 정보가 담겨진 간선들의 모임이 바로 그래프입니다.