그래프 (Graph)의 정의, 장단점, 구현법

그래프 관련 알고리즘 조사를 위해 기초가 되는 정보를 선조사한다.

 

그래프 관련 알고리즘 BFS, DFS 관련 조사는 이하 링크에 기재했다.

(미완) 그래프 알고리즘 종류

 

 

---

자료구조

선형자료구조 

 

하나의 자료 뒤에 하나의 자료가 존재하는 구조

자료들 간의 앞뒤 관계가 1:1의 선형관계
배열과 리스트가 대표적이고 더 나아가서 스택, 큐도 이에 해당된다.

 

비선형자료구조

 

비선형 자료구조란 하나의 자료 뒤에 여러개의 자료가 존재할 수 있는 것이다.
자료들 간의 앞뒤 관계가 1:n, 또는 n:n 의 관계
트리와 그래프가 대표적이며 계층적 구조를 나타내기에 적절하다. (자료를 계층적으로 구성)

데이터가 일렬로 연결되는 선형 자료구조와 달리 분기점이나 사이클 등이 존재하여 비선형적인 구조를 가지고 있다.

 

 

---

 

그래프란?

여러 개의 노드(node)와 이들을 연결하는 간선(Edge)으로 이루어진 자료구조.

컴퓨터 네트워크, 교통 시스템, 소셜 미디어와 같은 다양한 현실 세계의 문제를 모델링하는데 사용된다.

 

그래프의 구성 요소

정점은 그래프에서 가장 기본적인 구성 요소이며, 각 정점은 고유한 이름(identifier)을 가집니다.

간선은 정점과 정점을 연결하는 선으로, 두 개의 정점을 연결하는 데 사용.

 

도착점과 출발점에 따라 간선의 호칭도 달라진다.

 

 

 

그래프의 특징

그래프는 여러가지 특징을 가질 수 있다. 다만 하나의 그래프가 모든 특징을 가지는 것이 아니라 특징을 가짐에 따라 그래프의 종류도 나뉘어 진다.

• 무방향성 (Unidirectionality)
  그래프의 간선은 방향성이 없을 수 있으며, 양쪽 방향으로 모두 이동할 수 있습니다.
  이러한 그래프를 무방향 그래프(undirected graph)라고 부른다.
  양쪽의 방향으로 이동할 수 있지만, 무방향 그래프라고 부른다. 무방향의 의미가 방향의 강제하는 일방통행이 없다는 의미라고 생각할 수 있다.
• 방향성 (Directionality)
  그래프의 간선은 방향성이 있을 수 있으며, 한쪽 방향으로만 이동할 수 있다.
  이러한 그래프를 방향 그래프(directed graph) 또는 유향 그래프(digraph)라고 부른다.
• 가중치 (Weight)
  그래프의 간선에는 가중치(weight)를 부여할 수 있다.
  가중치를 부여한 그래프를 가중치 그래프(weighted graph)라고 부르며, 보통은 거리, 비용, 우선순위 등을 나타내는 데 사용된다.
• 연결성 (Connectivity)
  그래프에서 노드와 노드 사이에 경로가 존재하면, 두 노드는 연결되었다고 말한다. 그래프가 연결되어 있는 경우 연결 그래프(connected graph)라고 부르며, 그렇지 않은 경우 비연결 그래프(disconnected graph)이다.
• 사이클 (Cycle)
  그래프에서 한 노드에서 시작하여 경로를 따라가면서 마침내 자기 자신으로 돌아오는 경로를 사이클(cycle)이라고 부른다. 사이클이 없는 그래프를 비순환 그래프(acyclic graph)라고 부르며, 사이클이 있는 그래프를 순환 그래프(cyclic graph)라고 부른다.
• 차수 (Degree)
  그래프에서 한 노드에 인접한 간선의 수를 차수(degree)라고 부른다. 무방향 그래프에서는 노드의 차수가 연결된 노드의 수와 같으며, 방향 그래프에서는 인접한 노드의 수와 나가는 노드의 수로 구분된다.
•  

728x90

 

그래프의 장단점

장점

• 복잡한 관계를 직관적으로 표현할 수 있다.
• 네트워크 구조를 표현할 수 있어서 소셜 네트워크, 전력망, 노선도 등의 문제를 다룰 수 있다.
• 다양한 최적화 문제를 풀 수 있다.
  예를 들어, 최단 경로 문제나 최소 신장 트리 문제 등 다양한 그래프 알고리즘을 사용하여 최적화 문제를 풀 수 있다.

단점

• 데이터의 규모가 커질수록 계산 비용이 증가한다. 대형 그래프에서는 탐색 비용과 알고리즘의 수행 시간 등이 중요한 문제가 될 수 있다.
• 그래프의 구성이 복잡하면 이를 이해하기 어려울 수 있다.
• 방향성 그래프에서는 경로의 유무가 중요하므로, 경로가 존재하지 않는 경우에는 이를 고려하여 알고리즘을 설계해야 한다.

단점의 보완

• 분할 정복, 동적 계획법 등의 최적화 알고리즘을 사용하여, 계산 비용을 줄일 수 있다.
• 복잡해진 그래프를 시각화하는 방법을 고민하여, 데이터의 시각적 이해를 돕는 방법이 있다.
• 그래프를 단순화하여, 경로가 존재하지 않는 경우에도 유용한 결과를 도출할 수 있도록 만든다.
  예를 들면, 가중치를 조절하여 일정 이하의 가중치를 가진 간선들은 무시하는 방법을 생각할 수 있다.

 

 

 

그래프 구현 방법

인접 리스트(Adjacency List)와 인접 행렬(Adjacency Matrix)을 사용하는 방법이 있다.

인접 리스트는 각 정점에 대해 연결된 모든 정점의 리스트를 저장하는 방식으로, 특정 정점과 인접한 정점들을 바로 알 수 있다는 장점이 있다.

허접하지만 직접 그래프를 만들어보았다.

 

다음 그래프에 대한 인접 리스트는 다음과 같다.

1	2, 3
2	1, 4
3	1, 5, 6
4	2, 7, 8
5	3
6	3, 9, 10
7	4
8	4
9	6
10	6

 

다음은 인접 행렬이다.

	1	2	3	4	5	6	7	8	9	10
1	0	1	1	0	0	0	0	0	0	0
2	1	0	0	1	0	0	0	0	0	0
3	1	0	0	0	1	1	0	0	0	0
4	0	1	0	0	0	0	1	1	0	0
5	0	0	1	0	0	0	0	0	0	0
6	0	0	1	0	0	0	0	0	1	1
7	0	0	0	1	0	0	0	0	0	0
8	0	0	0	1	0	0	0	0	0	0
9	0	0	0	0	0	1	0	0	0	0
10	0	0	0	0	0	1	0	0	0	0

 

노드 간 연결 여부를 빠르게 확인할 수 있지만,

모든 정점에 관한 관계를 기록하기 때문에 메모리 소비가 더 크다고 한다. 행렬을 만드는 데에 너무 많은 시간이 걸렸다...

 

따라서 인접 행렬은 그래프 간선이 많은 그래프에 주로 사용하고, 인접 리스트는 상대적으로 간선이 적은 그래프에서 사용한다.

 

 

 

참고한 블로그

https://goodgid.github.io/DS-Linear-and-NonLinear/

https://velog.io/@kwontae1313/%ED%8A%B8%EB%A6%AC%EC%99%80-%EA%B7%B8%EB%9E%98%ED%94%84%EC%97%90-%EB%8C%80%ED%95%B4-%EC%95%8C%EC%95%84%EB%B3%B4%EC%9E%90

https://yozm.wishket.com/magazine/detail/2411/