[Data Structure] 그래프 (Graph)

✔ 그래프

그래프(Graph)란?

• 정점(노드)과 간선(엣지)의 집합
• 트리는 사이클이 허용되지 않는 그래프

그래프 용어

1. 무방향 그래프 : 정점과 간선의 연결관계에 있어서 방향성이 없는 그래프
2. 방향 그래프 : 정점과 간선의 연결관계에 있어서 방향성이 포함되어 있는 그래프
3. 가중치 그래프 : 간선에 가중치 정보를 두어서 구성한 그래프
4. 비가중치 그래프 : 모든 간선의 가중치가 동일한 그래프
5. 부분 그래프 : 본래의 그래프의 일부 정점 및 간선으로 이루어진 그래프
6. 차수 : 각 정점에 연결된 엣지의 개수
   • 방향 그래프에서는 간선에 방향성이 존재하기 때문에 차수가 두 개로 나뉘게 됨
   • 각 정점에서 나가는 간선의 개수는 진출차수
   • 각 정점으로 들어오는 간선의 개수는 진입차수 

그래프를 구현하는 방법

1. 인접 행렬 : 정방 행렬로 그래프를 표현
   
   • 가중치가 없는 그래프라면,
     출발 노드에서 도착 노드로 향하는 엣지를 인접 행렬의 출발 행 도착 열에 1을 저장하여 노드를 표현
   • 가중치가 있는 그래프라면,
     출발 노드에서 도착 노드로 향하는 엣지를 인접 행렬의 출발 행 도착 열에 가중치를 저장하여 노드를 표현
   • 인접 행렬은 구현하기 쉽지만, 노드와 관련되어 있는 엣지를 탐색하려면 N번 접근해야 하며
     노드 개수에 비해 엣지가 적을 때는 공간 효율성이 떨어짐
2. 인접 리스트 : 연결 리스트로 그래프를 표현
   
   • 가중치가 없는 그래프라면,
     N번 노드와 연결되어 있는 노드를 배열의 위치 N에 연결된 노드 개수만큼 배열을 연결하여 표현
   • 가중치가 있는 그래프라면,
     N번 노드와 연결되어 있는 노드를 배열의 위치 N에 연결된 노드 개수만큼 배열을 선언하고
     (도착 노드, 가중치)를 갖는 Node 클래스를 사용하여 표현
   • 그래프 구현은 복잡하지만, 노드와 연결되어 있는 엣지를 탐색하는 시간은 매우 뛰어나며
     노드 개수가 커도 공간 효율이 좋아 메모리 초과 에러도 발생하지 않음
   • 실제 코딩 테스트에서는 인접 리스트를 이용한 그래프 구현을 선호

그래프와 트리의 차이점

1. 그래프
   • 방향 그래프, 무방향 그래프 모두 존재
   • 사이클 가능, 자체 간선도 가능, 순환 그래프, 비순환 그래프 모두 존재
   • 루트 노드의 개념이 없음
   • 부모-자식의 개념이 없음
   • 네트워크 모델
   • DFS, BFS로 순회
   • 그래프에 따라 간선의 수가 다르며 간선이 없을 수도 있음
2. 트리
   • 방향 그래프만 존재
   • 사이클 불가능, 자체 간선도 불가능, 비순환 그래프
   • 한 개의 루트 노드만이 존재
   • 부모-자식 관계를 가지며 모든 자식 노드는 한 개의 부모 노드만을 가짐
   • 계층 모델
   • DFS, BFS 안의 전위, 중위, 후위 순회만 가능
   • 노드가 N인 트리는 항상 N - 1의 간선을 가짐
   • 임의의 두 노드 간의 경로는 유일함

너비 우선 탐색 (BFS)

1. 그래프 상에 존재하는 임의의 한 정점으로부터 연결되어 있는 모든 정점으로 나아감
   즉, 시작 노드에서 출발하여 시작 노드를 기준으로 가까운 노드를 먼저 방문하면서 탐색
2. 트리에서의 레벨 순회 형식으로 진행
3. 탐색을 시작하는 정점을 큐에 넣은 후, 탐색하면서 그 정점과 연결되어 있는 정점들을 넣도록 함
4. 큐를 이용하며 시간 복잡도는 O(V + E)

깊이 우선 탐색 (DFS)

1. 그래프 상에 존재하는 임의의 한 정점으로부터 연결되어 있는 한 정점으로만 나아감
   즉, 시작 노드에서 출발하여 탐색할 한 쪽 분기를 정하여 최대 깊이까지 탐색을 마친 후 다른 쪽 분기로 이동하여 다시 탐색
2. 일단 연결된 정점으로 탐색한 후 연결할 수 있는 정점이 있을 때까지 계속 연결하다가
   더 이상 연결될 수 있는 정점이 없으면 바로 그 전 단계의 정점으로 돌아가서 연결할 수 있는 정점이 있는지 탐색
3. 스택 또는 재귀 함수를 이용하며 시간 복잡도는 O(V + E)

최소 신장 트리

1. 신장 트리란 그래프의 모든 정점이 사이클 없이 연결된 형태
2. 최소 신장 트리는 그래프의 신장 트리 중에서 엣지 가중치의 합이 최소인 트리
   즉, 모든 노드를 연결할 때 사용된 엣지들의 가중치의 합을 최소로 하는 트리
3. 최소 신장 트리를 구현하기 위한 알고리즘으로는 크루스칼 알고리즘, 프림 알고리즘이 존재
   • 크루스칼 알고리즘은 엣지 없이 노드들로만 그래프를 구성한 후
     가중치가 제일 작은 엣지부터 사이클이 생기지 않는지 검토한 후 엣지를 추가하는 방식
   • 프림 알고리즘은 한 개의 노드로 이루어진 그래프를 구성한 후
     노드와 연결될 수 있는 외부에 있는 정점에 대해 가중치가 제일 작은 엣지를 가지는 정점을 그래프에 추가하는 방식 

위상 정렬

1. 사이클이 없는 방향 그래프일 때, 그래프의 각 노드의 순서를 찾는 알고리즘
2. 순서(정렬) 값이 유일하지 않다는 특징
3. 시간 복잡도는 O(V + E)

최단 경로

1. 다익스트라는 시작점에서 다른 모든 노드로 가는 최단 거리를 구하는 알고리즘
   • 음수 간선이 존재하지 않아야 함
   • 시간 복잡도가 O(ElogV)
2. 벨만-포드는 시작점에서 다른 모든 노드로 가는 최단 거리를 구하는 알고리즘
   • 음수 간선이 존재해도 됨
   • 시간 복잡도가 O(VE)
3. 플로이드 워셜은 임의의 모든 노드에서 다른 모든 노드로 가는 최단 거리를 구하는 알고리즘
   • 시간 복잡도가 좋지 않음
   • 시간 복잡도가 O(V³)