graph에 대해 이해해 보기
그래프 자료구조에 대해
예제
예제2
현재 사이드 프로젝트를 구상하고 있다. 핵심 로직에 그래프 구조의 이해가 필요했기에, 다시 한 번 정리해보려 한다.
그래프란 무엇인가?
from medium 블로그 현실 세계를 생각해 봅시다. 당신에게는 여러 친구가 있고 그들과의 관계를 정의해 봅시다. 당신과 당신의 친구들을 원으로 그린 다음에 서로 친구인 사람들은 선으로 잇는 겁니다. 이것이 바로 그래프입니다!
이 원은 위처럼 사람이 될 수도, 도시, 웹사이트, 세포가 될 수도 있다. 이 경우 개체인 원은 node(vertices), 도시간을 잇는 도로, 즉 노드 사이의 관계는 edges라고 부른다.
위의 예시처럼 그래프는 소셜 네트워크, 교통망, 컴퓨터 네트워크처럼 현실의 예시에서 사용된다.
그래프의 종류는 어떤 것들이 있는가?
1. Directed Graph
Directed 그래프는 node와의 관계(edge)에 방향이 있어 1방향으로 소통하는 관게이다. source node와 target node로 구분한다.
전기 회로, 컴퓨터 네트워크, 워크플로우처럼처럼 일발향으로 흘러가는 관계를 표현하기에 유용하다. 소셜 네트워크에서도 한 유저가 다른 유저를 팔로우하는 것이 좋은 예시이다.
Undirected 그래프는 node 관의 edge에 방향이 없고 양방향으로 소통할 수 있다.
소셜 네트워크, 교통망, 생물학적 네트워크 등 양방향으로 소통하는 구조를 표현하기에 유용하다.
2. Weighted Graph
Weighted 그래프는 node 간의 관계에 weight 혹은 cost가 존재하는 경우이다. 해당 weight는 여러가지로 사용될 수 있는데, 예를 들어 교통망일 경우 v1에서 v2로 이동하는데 5의 시간이 걸리는 경우이다.
Unweighted 그래프는 모든 edge가 같은 weight를 공유하는 경우이다. 소셜 네트워크의 경우, 한 유저가 다른 유저와의 관계를 맺는 경우 모두 같은 중요도를 가지고 있다고 여기는 경우이다.
3. Cyclic Graph
Cyclic 그래프는 최소한 하나의 사이클이 존재하는 경우이다. 모든 관계성이 그 시작점으로 돌아올 수 있는 경우를 말한다. 계절의 흐름이나 달의 위상 변화가 해당한다.
Acyclic 그래프는 DAGs(directed acyclic graphs)라고도 불리며 여러 컴퓨터 공학이나 수학에서 사용되는 구조이다. 각종 태스크나 이벤트, 프로젝트 매니지먼트, 스케쥴링 과 같은 예시에서 사용된다.
그래프를 구현하는 방법은?
크게 두 가지 Adjacency Matrix, Adjacency List 두 가지의 방법으로 구현한다.
1. Adjacency Matrix
2차원 배열을 통해 edge 관계를 구현한다. 행과 열이 해당 관계의 위치를 구분하며 value가 edge가 존재하는지, weight가 얼마인지를 표시한다.
장점: 두 노드 간의 관계를 확인하는데 (O(1))이 든다. 수학적 Matrix Multiplication 계산에 도움이 된다. 단점: Edge가 별로 없는 경우에도 최소 O(v2)의 공간이 필요함. edge를 추가하거나 제거할 때 배열의 계산 전체가 일어나 느릴 수 있다.
2. Adjacency List
Edges를 리스트의 형태로 보관한다. 모든 노드가 이웃 노드 그 자체를 참조하는 리스트를 가지고 여기에 edges를 보관함.
장점: O(V+E) 공간 복잡도를 가지며 간선이 적을 수록 메모리 사용량이 적다. edge를 추가하거나 삭제하는 것이 빠르다.
단점: node 간의 edge를 탐색하는 속도가 느리다. 탐색을 위해서는 해당 리스트(배열을 돌면서 찾아야 하므로)
Graph Traversal
그래프를 순회하는대는 크게 두 가지 방법이 존재한다.
1. Breadth First Search(BFS)
너비 우선 탐색이란 현재의 depth에서 탐색할 수 있는 모든 branch node를 탐색한 뒤, 다음 depth로 넘어가는 방식이다. queue구조를 사용한다.
2. Depth First Search(DFS)
깊이 우선 탐색이란 시작 node부터 탐색할 수 있는 모든 depth의 node를 확인한 뒤 backtracking 하는 방식이다. stack 구조를 사용한다.