💡 그래프 (Graph) - 비선형 구조 중 하나로 ‘정점(Vertices)과 그들 사이를 연결하는 간선(Edge)으로 표현된 자료구조’를 의미합니다. 각 정점은 데이터를 저장하며 간선은 정점들 간의 관계를 나타냅니다.
- 모든 그래프는 공식적으로 정점(V)와 간선(E)으로 그래프는 G = {V, E}로 표현이 됩니다. - 그래프는 다양한 형태와 용도를 가지며 네트워크, 경로 탐색, 스케줄링 등 다양한 시스템에서 활용됩니다. - 또한 다양한 알고리즘과 연산을 수행하는데 이용됩니다. 예를 들어 그래프 탐색 알고리즘을 사용하여 특정 노드를 찾거나 최단 경로 알고리즘을 사용하여 두 노드 사이의 최단 경로를 찾을 수 있습니다
- 그래프는 정점을 나타내는 노드와 간선으로 이루어져 있습니다. 정점은 데이터를 나타내고, 간선은 정점들 간의 관계를 나타냅니다.
2. 방향성(Directedness)
- 그래프는 방향성이 있는 경우와 없는 경우로 나뉩니다. - 방향성이 있는 그래프에서는 간선에 방향이 있어서 한 정점에서 다른 정점으로만 이동할 수 있습니다. - 방향성이 없는 그래프에서는 간선에 방향이 없어서 양방향으로 이동할 수 있습니다.
3. 가중치(Weight)
- 그래프의 간선은 가중치를 가질 수 있습니다. 간선의 가중치는 두 정점 사이의 거리, 비용, 우선순위 등을 나타냅니다.
4. 사이클(Cycle)
- 그래프에서 사이클은 한 정점에서 시작해서 다시 그 정점으로 돌아올 수 있는 경로를 말합니다. 사이클이 없는 그래프를 트리라고도 합니다.
5. 연결성(Connectivity)
- 그래프에서 모든 정점들이 연결되어 있는지를 나타내는 개념입니다. 그래프가 연결되어 있으면 연결 그래프라고 하고, 연결되어 있지 않으면 비연결 그래프라고 합니다.
6. 차수(Degree)
- 그래프에서 각 정점에 연결된 간선의 개수를 차수라고 합니다. 차수는 정점의 중요성이나 연결성을 나타내는 지표로 사용될 수 있습니다.
[ 더 알아보기 ] 💡 자료구조에서 트리(Tree)는 그래프(Graph)의 종류라고 하던데 그게 맞을까? - 트리가 그래프의 일종이라고 볼 수 있는 점이 있습니다.
1. 트리는 사이클이 없습니다. - 트리는 순환 경로가 없는 비선형 구조입니다.
2. 트리는 연결성을 가지고 있습니다. - 트리의 모든 노드들은 한 개 이상의 다른 노드와 연결되어 있습니다.
3. 트리는 단일 루트 노드를 가지고 있습니다. - 트리는 하나의 루트 노드에서 시작되며 다른 모든 노드들은 이 루트노드로부터 도달할 수 있습니다.
4. 트리는 계층 구조를 가지고 있습니다. - 트리는 부모-자식 관계를 통해 계층구조를 형성합니다.
이러한 특징들로 인해 트리는 그래프의 일종으로 간주됩니다.
2. 그래프의 기본구조
용어
설명
정점 (Vertices)
그래프에서 ‘데이터’를 나타내는 개별 요소를 말합니다. 노드(Node)라고도 불립니다.
간선(Edge)
그래프에서 ‘정점간의 관계’를 나타내는 선입니다. 연결선이라고도 불립니다.
가중치(Weight)
그래프의 ‘간선(Edge)에 할당된 값’으로, 간선(Edge)의 중요도 또는 비용을 나타냅니다.
차수(Degree)
정점에 연결된 ‘간선(Edge)의 개수’를 말합니다. 정점의 연결성을 나타내는 지표입니다.
경로(Path)
그래프에서 정점들을 연결하는 ‘간선(Edge)들의 순서대로 나열한 것’을 말합니다.
사이클(Cycle)
그래프에서 경로의 ‘시작점과 끝점이 동일한 경우’를 말합니다. 즉, 동일한 정점을 여러 번 방문하는 경로입니다.
연결성(Connectedness)
그래프에서 정점들이 얼마나 잘 연결되어 있는지를 나타내는 지표입니다.
플레너리티(Planarity)
그래프에서 사이클이 없는 경우를 말합니다. 즉, 모든 경로가 사이클을 형성하지 않는 그래프입니다.
이분 그래프(Bipartiteness)
그래프의 정점들을 두 개의 그룹으로 나눌 수 있는 그래프를 말합니다. 각 그룹 내의 정점들끼리는 서로 연결되어 있지 않아야 합니다.
3. 그래프의 표현 : 인접 행렬, 인접 목록
💡 그래프의 표현 : 인접 행렬, 인접 목록
- 그래프를 표현하는 방법에는 인접 행렬 형태로 표현하거나 인접 목록으로 표현하는 방법이 있습니다.
3.1. 인접 행렬(Adjacency Matrix)
💡 인접 행렬(Adjacency Matrix) - 그래프의 연결 상태를 2차원 배열로 나타내는 자료구조입니다.
- 노드의 개수를 N이라고 할 때, N x N 크기의 배열을 사용하여 그래프의 각 노드 간 연결 여부를 표현합니다. - 그래프의 연결 관계를 0 또는 1로 구현을 합니다. 만약 노드 간에 연결이 있다면 1을 나타내고 연결이 없으면 0으로 나타냅니다. - 인접 행렬은 노드 간의 연결 관계를 상수 시간에 확인할 수 있으며, 간선의 개수에 비례하는 메모리 공간을 요구합니다. 그러나 그래프가 희소한 경우 메모리 낭비가 발생할 수 있습니다.
💡 아래의 예시에서는 무방향 그래프(Undirected Graph)를 인접 행렬(Adjacency Matrix)로 표현을 합니다.
- [1,1] ‘0’의 값을 기준으로 ‘0’은 연결이 되어있지 않기에 0의 값을 가집니다. - [1,2] ‘0’의 값을 기준으로 ‘1’은 연결되어 있기에 1의 값을 가집니다. - [1,3] ‘0’의 값을 기준으로 ‘2’는 연결되어 있기에 1의 값을 가집니다.
- [2,1] ‘1’의 값을 기준으로 ‘0’은 연결되어 있기에 1의 값을 가집니다. - [2,2] ‘1’의 값을 기준으로 ‘1’은 연결이 되어 있지 않기에 0의 값을 가집니다. - [2,3] ‘0’의 값을 기준으로 ‘2’는 연결되어 있기에 1의 값을 가집니다.
- [3,1] ‘2’의 값을 기준으로 ‘0’은 연결되어 있기에 1의 값을 가집니다 - [3,2] ‘2’의 값을 기준으로 ‘1’은 연결되어 있기에 1의 값을 가집니다 - [3,3] ‘2’의 값을 기준으로 ‘2’은 연결이 되어 있지 않기에 0의 값을 가집니다.
💡 아래의 예시에서는 방향 그래프(Directed Graph)를 인접 행렬(Adjacency Matrix)로 표현을 합니다. - [1,1] ‘0’의 값을 기준으로 ‘0’은 연결이 되어있지 않기에 0의 값을 가집니다. - [1,2] ‘0’의 값을 기준으로 ‘1’은 방향성이 존재하지 않기에 0의 값을 가집니다. - [1,3] ‘0’의 값을 기준으로 ‘2’는 방향성이 존재하지 않기에 0의 값을 가집니다.
- [2,1] ‘1’의 값을 기준으로 ‘0’은 방향성이 존재하므로 1의 값을 가집니다 - [2,2] ‘1’의 값을 기준으로 ‘1’은 연결이 되어 있지 않기에 0의 값을 가집니다. - [2,3] ‘0’의 값을 기준으로 ‘2’는 방향성이 존재하므로 1의 값을 가집니다.
- [3,1] ‘2’의 값을 기준으로 ‘0’은 방향성이 존재하므로 1의 값을 가집니다. - [3,2] ‘2’의 값을 기준으로 ‘1’은 방향성이 존재하지 않기에 0의 값을 가집니다 - [3,3] ‘2’의 값을 기준으로 ‘2’은 연결이 되어 있지 않기에 0의 값을 가집니다.
그래프에 사이클이 존재하는 그래프로 한 노드에서 시작하여 다시 해당 노드로 돌아올 수 있는 경로가 있는 그래프입니다.
비순환 그래프
순환 여부
그래프에 사이클이 존재하지 않는 그래프로 한 노드에서 시작하여 해당 노드로 돌아오는 경로가 없는 그래프입니다.
1. 무방향 그래프 (Undirected Graph)
💡 무방향 그래프 (Undirected Graph) - 간선에 ‘방향이 없는 그래프’로 노드들이 서로 연결됩니다. 각각의 노드가 서로를 향하는 방향을 가리키지 않는 그래프입니다.
- 노드들이 서로 연결되어 있으며 간선은 양방향으로 표현됩니다. 즉 ‘한 노드에서 다른 노드로 갈 수 있는 경로’가 존재하면 그 노드들은 무방향 그래프에서 연결되어 있다고 볼 수 있습니다.
[더 알아보기 ]
💡 무방향 그래프의 사용 예시
1. 관계를 모델링 하는데 유용합니다. - 예를 들어, 친구 관계나 네트워크 연결 등을 해당 그래프를 이용하여 표현할 수 있습니다.
2. 응용 알고리즘 - 무방향 그래프를 이용하여 깊이 우선 탐색 (DFS), 너비 우선 탐색 (BFS), 최소 신장 트리 (MST) 알고리즘을 구현할 수 있습니다.
💡깊이 우선 탐색 (DFS) 알고리즘
- 그래프의 한 정점에서 다른 모든 정점을 탐색하는 알고리즘입니다. 💡 너비 우선 탐색 (BFS) 알고리즘
- 그래프의 한 정점에서 시작하여 인접한 정점을 먼저 탐색하는 알고리즘입니다 💡 최소 신장 트리 (MST)
- 그래프에서 모든 정점을 연결하는 가장 작은 가중치를 가진 부분 그래프를 찾는 알고리즘입니다.
2. 방향 그래프 (Directed Graph)
💡 방향 그래프 (Directed Graph) - 간선에 ‘방향이 있는 그래프’로 간선은 출발 노드와 도착 노드를 가리킵니다. 각각의 노드가 서로를 향해 방향을 가리키는 그래프입니다.
- 한 노드에서 다른 노드로 갈 수 있는 경로가 있을때만 그 노드들은 방향 그래프에서 연결되어 있다고 볼 수 있습니다.
[ 더 알아보기 ] 💡 방향 그래프의 사용 예시 1. 다양한 관계를 모델링 하는데 유용합니다. - 예를 들어, 인터넷의 웹 페이지 간의 링크, 도로 네트워크의 트래픽 흐름, 의사 결정 트리 등을 방향 그래프로 표현할 수 있습니다. 가중치를 활용하여 사용합니다. - 최단 경로 알고리즘, 흐름 네트워크 문제, 예산 할당 등의 문제를 해결하는 데에 활용됩니다.
2. 응용 알고리즘 - 방향 그래프를 이용하여 깊이 우선 탐색 (DFS), 너비 우선 탐색 (BFS), 위상 정렬 (Topological Sort) 알고리즘을 구현할 수 있습니다.
💡위상 정렬 (Topological Sort) 알고리즘
- 방향 그래프의 정점들을 일렬로 나열하는 알고리즘입니다. 사이클이 없는 방향 그래프에서만 적용 가능합니다.
3. 가중 그래프 (Weighted Graph)
💡 가중 그래프 (Weighted Graph)
- 간선에 ‘가중치가 할당된 그래프’로 가중치는 노드 간의 관계나 강도, 비용, 거리 등을 나타냅니다.
[ 더 알아보기 ] 💡 가중 그래프의 사용 예시
1. 다양한 관계를 모델링 하는데 유용합니다. - 최단 경로 알고리즘, 흐름 네트워크 문제, 예산 할당, 회로 설계 등 다양한 문제를 해결하는 데에 활용됩니다
2. 응용 알고리즘 - 가중 그래프를 이용하여 최단 경로 (Shortest Path), 최소 신장 트리 (MST), 최대 유량 (Maximum Flow) 알고리즘을 구현할 수 있습니다.
💡최단 경로 (Shortest Path) 알고리즘
- 그래프에서 두 정점 사이의 가장 짧은 경로를 찾는 알고리즘입니다. 💡최대 유량 (Maximum Flow) 알고리즘
- 그래프에서 한 정점에서 다른 정점으로의 최대 유량을 찾는 알고리즘입니다.
4. 연결 그래프 (Connected Graph)
💡 연결 그래프 (Connected Graph)
- 그래프에서 ‘모든 노드가 최소한 하나의 경로로 연결’된 그래프입니다. 즉, 어떤 두 노드 사이에 경로가 존재하면 그 노드들은 연결 그래프에서 연결되어 있다고 볼 수 있습니다.
[ 더 알아보기 ] 💡 연결 그래프의 사용 예시
1. 다양한 관계를 모델링 하는데 유용합니다. - 인터넷의 웹 페이지 간의 링크 관계, 도로 네트워크의 연결성, 사회적 관계 네트워크 등 다양한 문제를 해결하는데 활용됩니다.
2. 응용 알고리즘 - 연결 그래프를 이용하여 연결성 확인 (Connectivity Check), 최소 신장 트리 (MST), 오일러 경로 (Eulerian Path)을 구현할 수 있습니다. 💡 연결성 확인 (Connectivity Check) 알고리즘
- 그래프 내에서 두 정점 사이의 연결성을 확인하는 알고리즘입니다
💡오일러 경로 (Eulerian Path) 알고리즘
- 그래프의 모든 간선을 한 번씩만 지나는 경로를 찾는 알고리즘입니다.
5. 비연결 그래프 (Disconnected Graph)
💡 비연결 그래프 (Disconnected Graph)
- 그래프에서 ‘일부 노드가 다른 노드와 연결되지 않은 그래프’입니다. - 하나 이상의 연결 요소로 이루어져 있으며 각 연결 요소는 자체적으로는 연결되어 있지만 다른 연결 요소와는 연결되어 있지 않습니다.
[ 더 알아보기 ] 💡 비 연결 그래프의 사용 예시
1. 다양한 관계를 모델링 하는데 유용합니다. - 도로 네트워크에서 도로가 각각의 도시를 연결하고 있지만 도시들 간에는 연결이 되어 있지 않은 경우 비연결 그래프로 표현할 수 있습니다.
2. 응용 알고리즘 - 비 연결 그래프를 이용하여 연결성 확인 (Connectivity Check), 최소 신장 트리 (MST), 오일러 경로 (Eulerian Path) 알고리즘을 구현할 수 있습니다.
6. 순환 그래프 (Cyclic Graph)
💡 순환 그래프 (Cyclic Graph)
- 그래프에 ‘사이클이 존재하는 그래프’로 한 노드에서 시작하여 다시 해당 노드로 돌아올 수 있는 경로가 있는 그래프입니다. 적어도 한 개 노드에서 시작하여 다른 노드들을 거쳐 다시 ‘자기 자신으로 돌아오는 경로’를 가지는 그래프입니다.
- 즉, 한 노드에서 출발하여 계속해서 이동하면서 다른 노드들을 방문하다가 어느 시점에서 출발노드로 다시 돌아올 수 있는 그래프입니다.
[ 더 알아보기 ] 💡 순환 그래프의 사용 예시
1. 다양한 관계를 모델링 하는데 유용합니다. - 전기 회로에서의 신호의 흐름, 사이클링 알고리즘, 경로 최적화 등을 순환 그래프로 표현
2. 응용 알고리즘 - 순환 그래프를 이용하여 사이클 검사 (Cycle Detection), 위상 정렬 (Topological Sort) 알고리즘에 대해 구현이 가능합니다.
💡사이클 검사 (Cycle Detection) - 그래프 내에 순환 구조가 있는지 확인하는 알고리즘입니다.
💡 위상 정렬 (Topological Sort) - 순환 그래프에서는 적용할 수 없지만, 사이클이 없는 방향 그래프에서 정점들을 일렬로 나열하는 알고리즘입니다.
7. 비순환 그래프 (Acyclic Graph)
💡 비순환 그래프 (Acyclic Graph)
- 그래프에 ‘사이클이 존재하지 않는 그래프’로 한 노드에서 시작하여 해당 노드로 돌아오는 경로가 없는 그래프입니다. 어떠한 경로도 자기 자신으로 돌아오지 않는 순환이 없는 그래프입니다.
[ 더 알아보기 ] 💡 비 순환 그래프의 사용 예시
1. 다양한 관계를 모델링 하는데 유용합니다. - 전기 회로에서의 신호의 흐름, 사이클링 알고리즘, 경로 최적화 등을 순환 그래프로 표현
2. 응용 알고리즘 비 순환 알고리즘을 이용하여 위상 정렬 (Topological Sort), 최단 경로 (Shortest Path) 알고리즘에 대해 구현이 가능합니다.
💡[참고] 좀 더 다양한 자료구조에 대해 알고 싶으시면 아래의 글을 참고하시면 도움이 됩니다.
