그래프 (Graph)
그래프는 정점(Vertex)과 간선(Edge)로 이루어진 자료구조로, 정점간의 연결관계를 나타냅니다.
- 정점(Vertex) : 데이터를 표현하는데 사용한다.
- 간선(Edge) : 두 정점을 연결하며, 관계를 나타낸다.
특징 및 종류
- 네트워크 모델
- 2개 이상의 경로가 가능하다.
- 부모-자식 관계 / 루트 노드 개념이 없다
- 순환 / 비순환 그래프
- 순환(Cycle) : 동일한 정점에서 시작하여 다시 그 정점으로 돌아오는 경로. 순환이 있는 그래프
- 비순환(Acyclic) : 그래프 내에 순환이 없는 그래프
- 방향 / 무방향 그래프
- 방향 그래프 (Directed Graph) : 간선이 방향성을 가지고 있는 그래프
- 무방향 그래프 (Undirected Graph) : 간선간의 방향이 없는 그래프로 서로 모두 이용 가능한 상태
- 가중치 그래프
- 가중치 (Weighted Graph) : 간선에 비용이나 가중치가 할당된 그래프
- 연결 / 비연결 그래프
- 연결 (Connected Graph) : 무방향 그래프에 있는 모든 정점에 대해서 경로가 존재하는 그래프
- 비연결 (DisConnected Graph) : 무방향 그래프에서 특정 정점 사이에 경로가 존재하지 않는 경우
- 완전 그래프
- 완전(Complete Graph) : 그래프에 속해있는 모든 정점이 서로 연결되어 있는 그래프
인접 리스트
- 각 정점마다 연결된 정점들을 리스트로 저장하는 방식
- 메모리 사용량 O(V + E)이며, 인접 행렬보다 메모리 사용이 효율적이다.
- 그래프 내의 적은 숫자의 간선을 가지는 그래프(희소 그래프)인 경우에 사용하기 적합하다.
- 인접 노드를 빠르게 알 수 있지만, 연결 여부확인은 모든 노드를 탐색해야한다.
enum Vertex { A, B, C, D, E, F };
class Graph
{
private:
int vertices;
std::vector<std::vector<Vertex>> adjList;
public:
void addEdge(Vertex u, Vertex v)
{
adjList[u].push_back(v);
adjList[v].push_back(u);
}
};
int main() {
graph.addEdge(A, B);
graph.addEdge(B, C);
graph.addEdge(B, D);
graph.addEdge(C, E);
graph.addEdge(D, F);
}
인접 행렬
- 정점간의 연결 여부를 2D 행렬(2차원 배열)로 표현하는 방식
- 메모리 사용량은 O(V^2)이며, 인접 리스트보다 상대적으로 메모리를 더 많이 사용한다.
- 노드간의 연결 정보를 바로 알 수 있으며, 구현이 쉽다 (탐색 속도 O(1))
- 간선의 연결 여부는 빠르게 알 수 있지만, 어떤 노드에 인접한 노드를 찾기 위해서는 모든 노드를 순회해야한다.
- 간선이 많이 존재하는 그래프(밀집 그래프) 형태에 사용하기 적합하다.
class arrGraph
{
private:
int vertices;
std::vector<std::vector<int>> adjMatrix;
public:
void addEdge(int u, int v)
{
adjMatrix[u][v] = 1;
adjMatrix[v][u] = 1;
}
};
int main() {
graph.addEdge(0, 1);
graph.addEdge(1, 2);
graph.addEdge(1, 3);
graph.addEdge(2, 4);
graph.addEdge(3, 4);
graph.addEdge(3, 5);
return 0;
}
'알고리즘 , 자료구조' 카테고리의 다른 글
| [알고리즘] 힙 / 병합 정렬 (Heap / Merge Sort) (0) | 2025.01.14 |
|---|---|
| [알고리즘] 레드블랙 트리 , RBT (Red-Black Tree) (0) | 2025.01.10 |
| [알고리즘] 이진탐색트리 BST(Binary Search Tree) (0) | 2025.01.09 |
| [자료구조] 트리 (Tree) (0) | 2025.01.08 |
| 시간복잡도와 공간복잡도, Big O 표기법 (1) | 2024.12.26 |
