📊Graph Algorithm(그래프 알고리즘)
Graph란❓
알고리즘 공부를 하면서 그래프(Graph) 를 많이 접하고 있습니다. 설명드리는 그래프는 학창시절 수학시간 함수들의 그래프랑은 조금 의미가 다른 자료구조의 그래프입니다. 자료구조의 그래프는 단순히 노드(N, node)와 그 노드를 연결하는 간선(E, edge)을 하나로 모아놓은 자료구조입니다. 그래프를 처음 접한다면 노드와 간선같이 용어가 생소해서 이해하기 힘들겁니다. 자료구조의 형태중 트리구조를 아신다면 아래 그림을 보면서 용어를 찾아가면 알아가는데 도움이 많이 됩니다.
위 그림과 같은 트리구조도 그래프의 일종으로 노드와 노드를 연결하는 선인 간선으로 이루어져 있습니다. 그래프의 용어는 하나의 용어도 여러말로 불리우며 자신이 주로 사용하는 용어 말고도 잘 숙지하고 있는 것이 좋을 것 같습니다. 다른 사람과 의사사통할때 못알아들을 수 있잖아요!
- 정점(vertex) : 노드(node)라고도 하며 정점에는 데이터가 저장됩니다. (A, B, C, D, E, F...)
- 간선(edge): 링크(link), 브런치(branch)라고도 하며 노드간의 관계를 나타냅니다.
- 인접 정점(adjacent vertex) : 간선에 의해 직접 연결된 정점으로 위에서 (정점A과 정점B은 인접 정점)
트리구조는 그래프의 일부일 뿐 트리구조로 설명할 수 없는 다른 그래프의 성질과 용어를 설명드리기 위해 다음 그래프를 보면서 살펴보도록 하겠습니다. 그래프는 참조링크3 에서 만들었습니다.
- 가중치 : 간선 위에 표시된 숫자입니다. 가중치가 있는 그래프가 있고 없는 그래프가 있는데, 가중치가 없다면 모두 동일한 가중치를 가진다고 보면 됩니다. 해당 간선을 타고 이동할 때 필요한 비용 등을 표현하는 것에 사용됩니다.
- Directed Graph(유향 그래프) : 말 그대로 방향성이 있는 그래프입니다. 위 두개의 그래프 중 왼쪽 그래프가 Directed Graph입니다. 간선의 방향에 따른 이동만이 가능한 경우에 사용합니다.
- undirected Graph(무향 그래프) : 오른쪽 그래프 처럼 간선이 방향성이 없는 일반 실선으로 표시된 그래프입니다. 방향성이 없다고 이동을 못하는 것이 아니라, 모든 간선들은 양방향 이동이 가능함을 의미합니다.
- 차수(degree): 각 정점에 연결되어 있는 Edge들의 수입니다. 이 중 out-degree는 해당 정점에서 나가는 간선을, in-degree는 해당 정점으로 들어오는 간선입니다. 따라서 특정 정점에서의 모든 진출차수(out-degree)와 진입차수(in-degree)를 더하면 그 정점의 차수(Degree)가 됩니다.
- 진출 차수(out-degree) : 방향그래프에서 사용되는 용어로 한 노드에서 외부로 향하는 간선의 수를 뜻합니다. (외차수라고도 함)
- 진입차수(in-degree) : 방향그래프에서 사용되는 용어로 외부 노드에서 들어오는 간선의 수를 뜻합니다. (내차수라고도 함)
- Self-loops : 정점에서 자기 자신으로 돌아오는 간선을 뜻합니다. 오른쪽 그래프에서 0번 정점에 연결된 가중치 2의 간선이 이에 해당합니다.
- 단순 경로(simple-path): 경로 중 반복되는 정점이 없는것, 같은 간선을 자나가지 않는 경로
- 사이클(cycle) : 그래프가 path를 따라 동일한 정점으로 돌아올 수 있는 경우를 의미합니다. 위 그래프의 왼쪽 컴포넌트는 <1,4,2> path가 cycle을 이루고 있습니다. 이 중, 돌아오는 경로 안에서 중복된 노드가 시작점(끝점) 이외에는 발생하지 않는 경우를 Simple Cycle이라고 표현합니다.
- An acyclic graph : 그래프에 싸이클이 없는 경우 그 그래프를 acyclic graph라고 부릅니다.
- Connected Graph : 기본적으로 connected graph는 방향성이 없는 그래프입니다. 모든 쌍의 정점들이 path로 연결이 가능한 그래프를 connected graph라고 합니다.
- Dag : Dag는 방향성이 있는 그래프 중 싸이클이 나오지 않는 그래프를 의미합니다.
이렇게 그래프와 관련된 용어를 살펴 보았는데 처음에 예시로 들었던 트리는 수학, 특히 그래프 이론상으로는 Connected(연결형), Acyclic(비순환), Undirected(무향) 한 그래프라고 합니다. 하지만 자료구조에서의 트리는 DAG의 한 종류로 부모가 없는(욕아닙니다.) 루트노드를 정의 하고 노드들이 부모-자식 관계로 간선이 이어져 있는 Directed Graph(유향 그래프)라고 합니다. 저도 이것저것 찾아보면서 이진트리구조를 공부할 때 분명 방향이 있었는데 그래프 용어를 정리하면서는 무향이라고 하니까 혼란이 와서 찾아봤네요. 컴퓨터 용어자체가 건축, 수학 같은 곳에서 영향을 많이 받아서 같은 이름에 다른 의미를 가진 것이 많기에 조심해야 할 것 같아요.
그래프를 다룬 건 트리구조에 대한 심화처럼 보이지만 현재 공부중인 DFS(깊이 우선탐색)에 대하여 설명하기 위함입니다. 다음 글에서는 Java를 이용한 DFS를 다뤄보고자 합니다. 수학을 잘한다고 프로그래밍을 잘하는 것은 아니지만 수학적 직관은 한계를 뛰어넘어 더 높은 수준에 도달할 수 있게 해주는 것 같습니다. 알고리즘에 대한 공부를 놓지 않고 더 효율적인 아키텍쳐를 구상할 수 있는 개발자가 될 것 입니다.
참조 링크
1. [자료구조]그래프(Graph)란
2. 그래프 알고리즘(Graph Algorithm)의 기초 용어 정리
3. 그래프 edit tool
4. [Algorithm] 자료구조 그래프(Graph)란 무엇인가?
5. 나무위키 : 트리(그래프)
