프로그래밍

그래프(Graph)

바이오닉크로니클 2024. 12. 17. 17:39

그래프는 정점(Vertex 또는 Node)과 간선(Edge)으로 이뤄진 자료 구조이다. 그래프 이론은 컴퓨터 과학, 수학, 네트워크, 소셜 네트워크 등에서 널리 사용된다.

그래프는 이와 같이 정의된다.

G = (V, E)

  • V: 정점(Vertex)의 집합
  • E: 간선(Edge)의 집합그래프의 구성 요소
  1. 노드(정점, Vertex)
  • 그래프에서 각 숫자는 노드(정점)를 나타낸다.
  • 여기선 0번부터 8번까지 총 9개의 노드가 있다.
  1. 간선(Edge)
  • 두 노드를 연결하는 경로를 나타낸다.
  • 배열의 값이 0이 아닌 경우, 해당 노드 간 간선이 있음을 의미한다.
  • 값은 간선의 가중치(Weight)를 나타낸다.정점(Vertex 또는 Node)데이터나 개체를 나타낸다.
    도시를 표현할 때 각 도시는 하나의 정점이다.간선(Edge)두 정점을 연결하는 선으로 정점 간 관계를 나타낸다.
    두 도시 간 도로는 간선으로 표현된다.

그래프의 종류

1) 방향성에 따른 분류
무방향 그래프(Undirected Graph)
- 간선이 양방향이다. 정점 A와 B가 연결되면 A → B, B → A 모두 가능
- 도로 네트워크(양방향 도로)

(A)---(B)
  \     /
   (C)

유방향 그래프(Directed Graph)

  • 간선에 방향에 있다. 정점 A에서 B로 가는 간선은 A → B만 의미한다.
  • 단방향 도로, 웹페이지 링크

2) 가중치에 따른 분류
가중치 그래프(Weighted Graph)
- 간선에 가중치(Weight)가 부여된 그래프이다. 가중치는 거리, 비용, 시간 등을 의미할 수 있다.
- 도시간 거리, 네트워크 대역폭

(A)---4---(B)
  \       /
   8     7
    \   /
     (C)

비가중치 그래프(Unweighted Graph)

  • 간선에 가중치가 없는 그래프이다. 단순히 정점 간 연결만을 나타낸다.

3) 특수한 그래프
완전 그래프(Complete Graph)
- 모든 정점이 서로 연결된 그래프이다.
- N개의 정점이 있을 때 간선의 개수는 N(N - 1)/2이다.
트리(Tree)
- 사이클이 없는 연결 그래프이다.
- 사이클이 없다는 건 트리에서 정점들을 연결하는 간선을 따라 이동할 때 출발한 노드로 다시 돌아오는 경로가 존재하지 않는단 뜻이다. 즉, 순환 구조가 없는 것이다.
- 사이클이 하나라도 있으면 트리가 아니고, 사이클이 하나도 없으면 트리이다.
- 정점(V)이 N개이고, 간선(E)이 N - 1개여야 한다.
- 간선이 하나라도 추가되면 사이클이 생성되어 트리가 아니게 된다.
- 파일 시스템, 조직도

사이클이 없는 트리 예시

      A
     / \
    B   C
   / \
  D   E

A → B → D 경로로만 이동할 수 있고, 다시 D에서 출발점 A로 돌아갈 수 있는 경로는 없다.

그래프는 사이클이 있다.

(A)---(B)
 |     |
(C)---(D)

A → B → D → C → A

희소 그래프(Space Graph)

  • 간선의 수가 상대적으로 적은 그래프이다.
    밀집 그래프(Dense Graph)
  • 간선의 수가 상대적으로 많은 그래프이다.

그래프의 표현 방법

1) 인접 행렬(Adjacency Matrix)

  • 2차원 배열을 사용하여 정점 간 연결 여부와 가중치 표현
  • O(1) 시간에 간선 확인
  • 메모리 사용량 O(N^2)

graph 2차원 배열의 인덱스 (i, j)는 노드 i와 노드 j 사이 연결 상태를 나타낸다.

  • graph[i][j] = 0
    • 노드 i와 j 사이에 연결된 간선이 없음
  • graph[i][j] > 0
    • 노드 i와 j 사이에 가중치 graph[i][j]인 간선이 있음
int[][] graph = {
    {0, 4, 0},
    {4, 0, 8},
    {0, 8, 0}
};
(0)---4---(1)
              \
               8
                \
                 (2)

정점(0, 1, 2)

  • 숫자 0, 1, 2는 각각 정점을 나타낸다.
  • 정점 0은 특정 개체(도시, 서버 등)를 나타낼 수 있다.간선과 가중치
  • 정점 0과 정점 1 사이에 가중치 4의 간선이 있음
  • 정점 1과 정점 2 사이에 가중치 8의 간선이 있음정점
  • 정점은 그래프에서 데이터를 나타내는 노드(Node)이다.
  • 숫자 0, 1, 2는 각각 고유한 정점을 나타낸다.간선
  • 간선은 두 정점을 연결하며 배열의 값으로 표현된다.
    • 4: 정점 간 가중치(거리, 비용 등)
    • 0: 간선이 없음2) 인접 리스트(Adjacency List)
  • 각 정점에 연결된 다른 정점들을 리스트로 표현
  • 메모리 사용량 O(V + E)
  • 간선 확인은 느리지만 희소 그래프에 효율적
(0)---(1)
 |    /
(2)--(3)
(정점: 연결된 정점들의 리스트)
0: 1, 2
1: 0, 3
2: 0, 3
3: 1, 2

리스트는 LinkedList, Array, HashMap 등 여러 자료 구조를 사용해 구현할 수 있다.

두 정점의 연결 여부를 확인하는 것은 리스트를 순회해야 하기에 O(E) 시간이 걸린다.
밀집 그래프의 경우 인접 행렬이 더 효율적이다.