1. 학습 목표
알고리즘을 학습하기 위해 필요한 자료구조들을 먼저 복습하자.
2. 학습 내용
우리가 사용할 DFS, BFS, 다익스트라 등의 알고리즘은 그래프를 많이 활용한다. 따라서 오늘을 그래프에 대해서 내용을 복습하고 구현해 보았다. 추가적으로 그래프의 일종인 트리구조에 대해서도 학습하였다.
그래프를 구성하는 요소는 정점(vertex), 간선(edge), 가중치(weight)가 있다.
정점은 다른 말로 노드라고 한다. 쉽게 말하면 값을 가지고 있는 공간이라고 생각할 수 있다. 그리고 그 공간들을 연결해주는 다리 역할을 하는 것이 간선이라고 할 수 있다.
그래프의 종류엔 무방향 그래프(undirected graph), 방향 그래프(directed graph)를 둘 수 있다. 이름에서도 알 수 있듯이
무방향 그래프는 간선에 방향이 없다는 것이다. 예를 들면 A -> B == B -> A 임을 사진에서 확인할 수 있다.
반면에 방향 그래프는 간선에 방향이 존재한다. 예를 들면 A -> B == B -> A 일 수 도 있지만 가중치가 뭐냐에 따라서
A -> B != B -> A 일 수 있다.
cf) 여기서 말한 가중치란 간선에 부여하는 비용이다.
*그래프의 연결성(connectivity)*
1. 연결 그래프(connectivity graph)
무방향 그래프 G에 있는 모든 정점 쌍에 대하여 경로가 존재할 경우, 무방향 그래프 G는 연결 그래프이다. 여기서 주의할 점은, 모든 정점 쌍에 대하여 경로가 존재한다는 것은 임의의 두 정점 간에 간선이 존재한다는 걸 의미하는 게 아니다. 두 정점이 간선으로 연결되어 있지 않더라도 다른 정점을 통한 간선으로 이동할 수 있음을 주의해야한다.
2. 트리(tree)
그래프의 특수한 형태로서,무순환 연결 그래프이다 (connected acyclic graph). acyclic 이란 사이클이 존재하지 않는다라는 것이다. 즉 시작 정점에서 다시 시작 정점으로 돌아올 때 이미 방문한 엣지를 무조건 다시 방문하지 않고서는 불가능한 구조이므로 하나의 edge만 삭제해도 연결그래프가 아니게 된다.
3. 완전 그래프 (complete graph)
모든 정점이 서로 연결되어 있는 그래프이다.
n개의 정점을 가지는 완전 그래프의 에지 개수
→ (무방향 그래프): n(n-1)/2, (방향 그래프): n(n-1)
* 그래프의 표현 방법*
1. 인접 행렬
정점의 개수를 v라고 했을 때, v x v 행렬을 정의한다. 이때 row는 해당 정점의 연결 상태를 의미한다.
2. 인접 리스트
각 정점에 인접한 정점들을 연결 리스트로 표현한다. 정점이 v개인 그래프라면 v개의 연결리스트로 구성한다. 각 연결리스트마다 포인터 변수가 리스트의 처음 노드를 가리키며 연결리스트가 없는 경우, 즉 차수가 0인 경우 포인터 변수의 값은 null이 된다.
이 때 시간복잡도를 보았을 때 인접리스트를 사용하였을 때 더 좋은 효율을 보여준다는 것을 알 수 있다. 시간 복잡도를 비교해보면 O(V^2) / O(V+E) (V는 vertex 수, E는 edge의 수)로 인접 리스트를 쓰는 것이 보통의 경우에 더 낫다.
* 그래프 구현*
1. 인접 행렬
def print_graph(graph):
for i in range(1, len(graph)):
for j in range(1, len(graph)):
print(graph[i][j], end=" ")
print()
def put_edge(graph, x, y):
graph[x][y] = 1
graph[y][x] = 1
if __name__ == "__main__":
n = 5
graph = [[0] * (n + 1) for _ in range(n + 1)]
put_edge(graph, 1, 2)
put_edge(graph, 1, 3)
put_edge(graph, 1, 4)
put_edge(graph, 2, 3)
put_edge(graph, 2, 5)
put_edge(graph, 3, 4)
put_edge(graph, 4, 5)
print_graph(graph
2. 인접 리스트
import sys
n, m = map(int, sys.stdin.readline().split())
visited = [False] * (n+1)
adjacent = [[] for _ in range(n+1)] # 인접 행렬 // e.g n = 5, 0은 1,2와 인접, 2는 3과 인접 하다 가정 >> [ [1,2] [] [3] [] [] ]
# 그래프 생성
for _ in range(m):
u, v = map(int, sys.stdin.readline().split())
adjacent[u].append(v)
adjacent[v].append(u)
# 그래프 출력
for i in range(n+1):
print(f"{i}와 인접한 노드들: {adjacent[i]}")
* 그래프와 트리의 비교*
트리는 그래프의 일종으로 노드와 노드 간을 연결하는 간선으로 구성되어있다. 트리는 두 개의 노드 사이에 반드시 1개의 경로만을 가지고 방향성이 존재하며 사이클은 존재하지 않는다. 추가로 부모-자식 관계가 존재하며 레벨이 존재한다. 이 때 최상위 노드를 root 노드라고 한다. 노드가 V개면 간선은 V-1개 존재한다.
*느낀 점*
스스로가 이론적으론 알고 있다고 하였지만 복습을 확실히 하지 않으면 힘들다는 것을 느낀 것 같다. 그리고 파이썬이라는 언어는 내부 라이브러리에 많은 자료구조들이 구성되어있어서 자바를 이용하였다. 언어는 확실히 그냥 툴일 뿐이고 알고리즘과 자료구조에 대해 더 깊이 있는 이해를 하는 것이 중요하다는 것을 깨달은 시간이 되었다.
