그래프
- 객체들과 객체들 사이의 연결관계 표현
- 정점(Vertex)들의 집합과 정점을 연결하는 간선(Edge)들의 집합으로 구성된 자료 구조
- 선형 자료구조나 트리 자료구조로 표현하기 어려운 N:N 관계를 가지는 원소들을 표현하기에 용이.
- 무향 그래프: 서로 대칭적인 관계를 연결해서 나타낸 그래프. 친구관계 등.
- 유향 그래프: 간선을 화살표로 표현하고 방향성의 개념 포함. 애정관계 등
- 가중치 그래프: 정점 - 도시, 간선 - 한 도시에서 다른 도시로 이동 가능. 두 도시들 사이 이동하는데 걸리는 시간 비용이 다를 경우 가중치로 표현.
- 인접(Adjacency): 두 개의 정점에 간선이 존재(연결됨)할 경우 서로 인접해 있다고 함.
컴퓨터에서의 그래프 표현
1) 인접행렬
- VxV 크기의 2차원 리스트 이용.
- 두 정점을 연결하는 간선의 유무를 행렬 형태로 표현
- 행 번호와 열 번호는 그래프의 정점에 대응
- 인접하면 1, 아니면 0
- 인접 리스트: 각 정점마다 인접 정점으로 나가는 간선의 정보 저장
그래프 탐색
친구관계 문제
- A로부터 시작해서 한 명의 친구에만 소식을 전달할 수 있따면 최대 몇 명이 전달 받을 수 있을까? 중복 불가.
- 혹은 최대한 전달할 수 있다고 할 때 가장 늦게 전달받는 사람은?
1) 깊이 우선 탐색
- 시작 정점에서 갈 수 있는 한 방향을 선택 해서 다음으로 이동
- 위 방법을 반복수행. 갈 수 있는 경로가 있는 곳까지 깊이 탐색하나, 재방문은 하지 않음.
- 갈곳이 없으면 가장 최근 갈림길의 정점으로 돌아와서 다른 방향으로 탐색하여 모두 방문.
- 스택이나 재귀호출로 구현
- 재귀: 작업 수행 -> 인접정점에 대해 방문했는지 검사 -> 안 했으면 반복
- 스택: ...
2) 너비 우선 탐색
- 탐색 시작점의 인접 정점들을 먼저 모두 방문
- 방문했던 정점들을 시작점으로 하여 앞의 과정 반복 수행.
- 방문한 정점은 재방문하지 않음
- 큐를 만들어, 해당 큐를 pop하면서 방문여부 확인
서로소 / 상호배타집합
- 서로 중복 포함된 원소가 없는 집합들로 교집합이 없음.
- 집합에 속한 하나의 특정 원소를 통해 각 집합들을 구분
- 특정원소: 대표자(Representative)
- 상호 배타 집합을 표현하는 방법
- 연결 리스트, 트리
- Make-set(x): 원소 x만 있는 집합
- Find-set(x): 임의의 원소 x가 속한 집합. 집합의 대표자를 알기 위한 연산.
- Union(x, y): x원소가 속한 집합과 y원소가 속한 집합을 하나의 집합으로 합침.
- 하나의 집합을 하나의 트리로 표현
- 자식 노드가 부모 노드를 가리키며 루트 노드가 대표자가 됨.
문제점.
- 집합을 합치는 과정에 편향된 트리 구조가 생성될 수 있음.
- 간선의 수만큼 재귀호출 필요
- 간선 하나를 따라가면 바로 루트에 도달 -> 모든 원소들이 루트를 바로 가리키도록 하면 됨.
연산 효율 높이기
- Rank를 이용한 union
-> 각 노드는 자신을 루트로 하는 subtree 높이를 랭크로 저장
-> 두 집합을 합칠 때 랭크가 낮은 집합을 랭크가 높은 집합에 붙임
- path compression: Find-set을 행하는 과정에서 만나는 모든 노드들이 직접 root를 가리키도록 부모 정보를 변경
상호배타 집합의 연산들
- 구현이 간단하고 동작 속도가 빠르기 때문에 그래프 영역에서 많이 사용되고 다른 알고리즘의 일부로 활용
-> 그래프의 연결성 확인
-> KRUSKAL MST 알고리즘
- 각 집합에 속한 원소의 수 관리
-> 가장 큰 집합 추적
-> 집합의 노드 개수가 몇 개 이상이 되는 시점 찾기
