[자료구조] 그래프

🎞️ Graph

그래프: 노드와 그 노드를 연결하는 간선을 모아 놓은 자료구조

🎞️ 용어

• 정점(vertex): 위치. aka 노드
• 간선(edge/link/branch): 위치 간의 관계. 노드를 연결하는 선
• 인접 정점(adjacent vertex): 간선에 의해 직접 연결된 정점
• 정점의 차수(degree): 무방향 그래프에서 하나의 정점에 인접한 정점의 수
  • 무방향 그래프에 존재하는 정점의 모든 차수의 합 = 그래프의 간선의 2배
• 진입 차수(in-degree): 방향 그래프에서 외부에서 오는 간선의 수
  • aka 내차수
• 진출 차수(out-degree): 방향 그래프에서 외부로 향하는 간선의 수
  • aka 외차수
• 경로 길이(path length): 경로를 구성하는데 사용된 간선의 수
• 단순 경로(simple path): 경로 중에서 반복되는 정점이 없는 경우
• 사이클(cycle): 단순 경로의 시작 정점과 종료 정점이 동일한 경우

🎞️ 종류

무방향 vs. 방향 그래프

• 무방향 그래프(Undirected graph)
  • 무방향 그래프의 간선은 간선을 통해서 양방향으로 갈 수 있음
  • 정점 A와 정점 B를 연결하는 간선은 (A, B)와 같이 정점의 쌍으로 표현
    • (A, B) = (B, A)
    • 양방향
• 방향 그래프(Directed graph)
  • 간선에 방향성이 존재하는 그래프
  • A -> B로만 갈 수 있는 간선은 <A, B>로 표시
    • <A, B> != <B, A>
    • 일방향 통행

가중치 그래프(Weighted graph)

• 간선에 비용이나 가중치가 할당된 그래프
• 네트워크라고도 함

연결 vs. 비연결 그래프

• 연결 그래프(Connected graph)
  • 무방향 그래프에 있는 모든 정점쌍에 대해서 항상 경로가 존재함
  • (예) 트리(Tree): 사이클을 가지지 않는 연결 방향 그래프
• 비연결 그래프(Disconnected graph)
  • 무방향 그래프에서 특정 정점쌍 사이에 경로가 존재하지 않음

순환 vs. 비순환 그래프

• 사이클(Cycle)
  • 단순 경로의 시작 정점과 종료 정점이 동일함
  • 단순 경로(Simple path): 경로 중에서 반복되는 정점이 없음
• 비순환 그래프(Acyclic graph): 사이클이 없는 그래프

완전 그래프(Complete graph)

• 그래프에 속해 있는 모든 정점이 서로 연결되어 있는 그래프
• 무방향 완전 그래프
  • 정점 수가 n이면 간선의 수는 n*(n-1)/2

🎞️ 구현하기

인접리스트 또는 인접행렬로 구현하기

🎞️ 인접리스트로 구현

• 모든 노드를 인접 리스트에 저장 (각각의 정점에 인접한 정점들을 리스트로 표시)
  • 주로 배열/해시테이블과 배열의 각 인덱스마다 존재하는 또 다른 리스트(배열/ArrayList/LinkedList)로 표현
  • 노드의 번호만 알면 이 번호를 배열의 인덱스로 하여 각 노드의 리스트에 쉽게 접근 가능
• 무방향 그래프에서 (a, b) 간선은 두번 저장됨
  • a 정점에 인접한 간선으로 저장, b 정점에 인접한 간선으로 저장
  • 정점의 수는 N, 간선의 수는 E인 무방향 그래프인 경우, N개의 리스트, N개의 배열, 2*E개의 노드 필요

🎞️ 인접행렬로 구현

인접 행렬: N*N의 Boolean Matrix(또는 binary matrix)

• matrix[i][j]가 true면 i->j로의 간선이 존재한다는 뜻
• 노드의 개수가 N인 그래프를 인접행렬로 표현
  • 간선의 수와 무관하게 항상 n^2개의 메모리 공간이 필요함
• 무방향 그래프를 인접 행렬로 표현하면 이 행렬은 대칭 행렬(Symmetric matrix)이 됨
  • 방향 그래프는 대칭 행렬이 아닐 수 있음
• 인접 행렬은 인접 리스트에 비해 그래프 알고리즘에 대해 효율성이 조금 떨어짐
  • 인접 리스트는 노드에 인접한 노드를 바로 찾을 수 있지만 인접 행렬은 인접한 노드를 찾기 위해 모든 노드를 전부 순회해야 함

🎞️ 인접리스트 vs. 인접행렬

인접리스트

• 그래프 내 적은 숫자의 간선만 존재하는 희소 그래프(Sparse graph)에 적합
• 장점
  • 노드에 인접한 노드를 쉽게 찾음
  • 그래프에 존재하는 모든 간선의 수는 O(N+E) 안에 알 수 있음
• 단점: 간선의 존재 여부와 정점의 차수 찾기 어려움: 정점 차수만큼 시간 필요

인접 행렬

• 그래프에 간선이 많이 존재하는 밀집 그래프(Dense graph)에 적합
• 장점
  • 두 정점을 연결하는 간선의 존재 여부를 O(1)에 알 수 있음
  • 정점의 차수는 O(N)에 알 수 있음
    • 인접 배열의 i번째 행/열을 모두 더함
• 단점
  • 노드에 인접한 노드를 찾기 위해서는 모든 노드 전부 순회
  • 그래프에 존재하는 모든 간선의 수도 모든 노드 전부 순회

🎞️ 연산의 시간 복잡도, 공간 복잡도

총 V개의 노드, E개의 엣지가 존재함

두 정점이 연결되었는지 여부

• 인접리스트
  • 시간복잡도: 해당 정점의 차수만큼의 시간
    • 최악의 경우 O(V)
    • 노드의 리스트 안에 특정 노드가 저장되어있는지 선형 탐색
• 인접행렬
  • 시간복잡도: O(1)
    • 행렬의 인덱스 사용

한 정점에 연결된 모든 정점 찾기

• 인접리스트
  • 시간복잡도: 해당 정점의 차수만큼의 시간
    • 최악의 경우 O(V)
    • 주로 인접행렬보다 빠르게 실행됨
• 인접행렬
  • 시간복잡도: O(V)
    • 전체 행렬을 순회하여 그 노드가 있는 인덱스의 값이 1(true)인지 확인해야 함

공간복잡도

• 인접리스트
  • 각 노드는 하나의 인접 리스트를 가짐 > 총 V개의 배열 > 최소 O(V)
  • 엣지는 O(E)
    • 무방향인 경우 2E
    • 방향인 경우 E
  • 총 O(V+E)
  • 최악의 경우(모든 노드가 서로에게 연결)는 O(V^2)
• 인접행렬
  • 배열의 크기는 (총 노드 개수)*(총 노드 개수)
  • 총 O(V^2)

🎞️ 정점의 개수가 N개, 간선의 개수가 N^3 개라면, 어떤 방식으로 구현하는 것이 효율적일까?

• 인접 리스트
  • 두 정점이 연결됐는지: O(N)
  • 한 정점에 연결된 모든 정점 찾기: O(N)
  • 공간복잡도: O(N^3)
• 인접 행렬:
  • 두 정점이 연결됐는지: O(1)
  • 한 정점에 연결된 모든 정점 찾기: O(N)
  • 공간복잡도: O(N^2)

인접행렬을 구현하는 것이 효율적이다.

🎞️ 사이클이 없는 그래프의 구분

트리: 사이클이 없는 연결 그래프

포레스트: 사이클이 없는 비연결 그래프

---

참고:

• [자료구조] 그래프(Graph)란
• [그래프] 12. 인접 행렬 vs 인접 리스트
• Graph Theory - Trees