그래프(Graph)에 대하여
지난 포스팅까지 다양한 트리 구조에 대해 알아보았다면, 이번에는 또 다른 자료 구조인 그래프(Graph)에 대해 자세히 알아보겠다. 그래프는 객체 간의 관계를 표현하는 도구이며, 소셜 네트워크, 교통망, 인터넷 구조 등 다양한 시나리오를 모델링하는 데 사용될 수 있다.
그래프란?
본질적으로 그래프는 객체들의 집합과 그들 사이의 연결 관계를 나타낸다. 객체는 vertex 또는 node라고 불리며, 연결 관계는 edge로 나타낸다. vertex를 도시, edge는 이 도시를 잇는 도로라고 생각할 수 있다.
그래프의 핵심 개념
그래프를 다룰 때 마주칠 몇 가지 필수 용어를 살펴보겠다.
- Vertex: 그래프의 기본 단위 또는 객체
- Edge: 두 정점 사이의 연결 또는 링크
- Directed Edge: 특정 방향을 가진 edge로, vertex 간의 일방적인 관계를 나타냄(예: 일방 통행 도로)
* 특정 vertex 기준 들어오면 incoming edge, 나가면 outgoing edge - Undirected Edge: 방향이 없는 edge으로, vertex 간의 양방향 관계를 나타냄 (예: 일반 도로)
- Adjacent Vertices: edge로 연결된 두 vertices (예: 도로로 연결된 두 도시)
- Parallel Edges: 동일한 두 vertex를 연결하는 여러 개의 edges (예: 두 도시를 연결하는 여러 개의 도로)
- Incident: 특정 vertex의 edges (예: 도시로 가는 여러 개의 도로)
- Path: edge로 연결된 vertex의 순서 (예: 여러 도시를 거치는 경로)
* vertex 중복이 없다면 simple path라 한다. - Cycle: 시작 vertex와 끝 vertex가 동일한 경로 (예: 출발 도시로 다시 돌아오는 경로)
* vertex 중복이 없다면 simple cycle이라 한다.
그래프 구현 방법
컴퓨터 프로그램에서 그래프를 표현하는 방법은 여러 가지가 있다. 몇 가지 일반적인 방법을 살펴보자.
Edge List : edge 쌍의 단순한 리스트다. 이 표현 방식은 간단하지만, 대규모 그래프에는 비효율적일 수 있다.
edge list Adjacency List : 각 vertex은 incident edge들의 리스트를 갖는다. 이는 비교적 적은 edge를 가진 sparse graph에 많이 사용된다.
adjacency list Adjacency Matrix : 2차원 행렬로, 행과 열은 vertex를 나타내고, 각 항목은 두 vertex 사이에 edge의 존재 여부를 나타낸다. 이는 많은 edge을 가진 dense graph)에 자주 사용된다.
adjacency matrix Adjacency Map : key가 vertex이고 value를 edge로 하는 맵(또는 딕셔너리)다. 이는 유연성을 제공하며 다양한 그래프 연산에 효율적일 수 있다.
adjacency map
 |
| |E| : edge 수, |V| : vertex 수 |
|E| <= n(n-1)라는 부등식을 만족한다.(undirected edge라면 중복 제외 *1/2)
마무리하며
이번 포스팅에서는 그래프의 기본 개념, 용어, 그리고 다양한 표현 방법에 대해 알아보았다. 그래프의 시작에 불과하다. 다음 포스팅에서는 그래프 탐색 알고리즘인 깊이 우선 탐색(Depth-First Search, DFS)과 너비 우선 탐색(Breadth-First Search, BFS)에 대해 자세히 알아보겠다.
추천글:
(https://hyeonb.blogspot.com/2024/03/blog-post.html)
