1. Terminology
Graph란 edges로 연결된 vertices 집합이다.
지하철 노선도, 우주 은하 등 세상에 존재하는 수많은 것들을 그래프로 추상화하여 표현할 수 있다.
Vertices의 이름은 symbol table로 Integer로 mapping하여 사용하면된다.
특히 Undirected graph는 edge의 방향이 존재하지 않는다.
- Path : sequence of vertices connected by edges
- Cycle : 첫번째와 마지막 vertex가 같은 Path
2. API & Representation
Graph의 API는 다음과 같다.
Graph(int V) // V개 vertice를 가진 그래프 생성
Graph(In in) // Input stream에 따라 그래프 생성
void addEdge(int v, int w) // edge로 연결
Iterable<Integer> adj(int v) // v와 인접한 vertice들 반환
int V() // vertices 갯수반환
int E() // edges 갯수반환
String toSting()
Graph의 표현은 sparse matrix의 표현과 같이 Adjacency-lists representation을 사용한다. 2차원 배열이 아닌 각 vertex의 번호를 배열의 Index로 하여 vertex개수의 크기를 가진 배열을 생성하고, 각각의 vertex에 인접한 vertex들을 가진 Bag을 linked list로 연결하여 표현한다. Bag로 표현하는 이유는 인접한 vertex들간에 순서가 존재하지 않기 때문이다. 실세계에서 모든 그래프의 vertex가 서로 연결되는 밀도높은 경우는 거의 존재하지 않기 때문에, 이 방법은 매우 유용하다.
따라서, 전체 사용공간은 (배열사용공간 + Bag사용공간) 이므로 (V + E) 로 효율적으로 사용하며, Edge의 추가는 배열의 Index탐색은 constant time이고, Bag삽입 또한 constant time이므로 constant time이 걸린다.
3. Depth-first search(DFS)
다음과 같은 응용에 쓰인다.
- 한 vertex와 연결된 모든 vertices 찾기
- 두 vertex사이 path 찾기
Depth-first search는 recursive하게 계속 탐색하다가 막히면 이전단계로 돌아가 탐색함을 반복하는 탐색이다.
(탐색의 우선순위가 함수호출의 최대깊이까지 들어가므로 Depth-first search이다.)
이 탐색은 미로에서 탐색을 위해서 고안되었는데, 그리스로마신화에서 보았던 미노타우르스의 실과 원리가 동일하다. 즉, 출발지를 기준으로 최대한 쭉 탐색(recursive call)을 하다가 길이 없어 막히면 막힌 지점에 체크(marked)를 하고 직전 지점을 표시한뒤(edgeTo) 되돌아온다(return). 되돌아온 지점에서 탐색하지 않은 경로가 있다면 해당 경로로 동일하게 쭉 탐색하고, 되돌아옴을 반복한다.
구현은 다음과 같다.
public class DepthFirstPaths{
private boolean[] marked;
private int[] edgeTo;
private int s;
public DepthFirstPaths(Graph G, int s){
... // 초기화
dfs(G, s); // source vertex로 부터 탐색 시작
}
private void dfs(Graph G, int v){
marked[v] = true; // 탐색완료 표시
for (int w : G.adj(v))
if(!marked[w]){
dfs(G, w); //recursive search
edgeTo[w] = v; // 직전 vertex표시
}
}
}
탐색 실행시간은 모든 vertex를 한번씩 반복하고 인접한 edge를 탐색함을 반복하므로 모든 vertex에 대한 degree 합에 비례한다.
탐색완료후,
source vertex와 특정 vertex가 연결되었는지 여부는 단순히 marked 되어있는지를 확인하면 되므로, 배열의 접근시간인 contant time이 걸린다.
source vertex -> 특정 destination vertex까지 경로(최단경로 보장x)는 edgeTo[]를 이용하여 destination vertex부터 시작해서 역으로 찾으면 되므로, 해당 경로의 길이에 비례한다.
4. Breadth-first search(BFS)
DFS가 호출하는 함수를 지속적으로 함수Stack에 넣게 되므로, 방문한 vertex들을 stack에 넣는 것과 같이 볼 수 있다. 이와 반대로, BFS는 방문한 vertex를 queue에 넣고 꺼냄을 반복한다.
먼저, source vertex부터 시작해 vertex를 queue에 넣고, 방문완료 표시(marked)를 한다.
queue에서 하나씩 꺼내고 꺼낼때마다 인접한 vertex를 queue에 넣고, 넣을 때마다 해당 인접한 vertex에 방문완료 표시(marked)를 하고 직전지점을 표시(edgeTo)한다.
이것을 queue가 완전히 비워질때까지 반복한다.
이렇게 되면, source vertex가 비워질 때, 그로부터 distance = 1인 vertex가 모두 queue에 들어가 있을것이고, distance = 1인 vertex가 queue에서 모두 빠져나올 때, distance = 2인 vertex가 모두 queue에 들어가있을 것이다. 즉, source vertex로부터 거리가 가까운 vertex가 우선적으로 탐색된다.
탐색실행시간은 탐색순서만 다르고 방식이 동일하므로, DFS와 동일하다.
source vertex와 특정 vertex가연결되었는지 여부는 DFS와 동일하다.
한가지 다른점은, 거리가 가까운 것부터 탐색되므로 찾아진 경로는 최단경로가 된다.
따라서, source vertex -> 특정 destination vertex까지 최단경로 를 경로 길이에 비례한 시간으로 찾을 수 있다.
5. Connectivity query
Connectivity query란, 두 객체가 서로 연결되어있는지를 묻는 문제이다.
이것은 앞서 배웠던 union-find문제와 동일한 문제이고, union-find를 사용하면 객체의 연결과 연결여부 확인을 logarithmic time에 할 수 있었다.
하지만, 연결관계가 주어지면서 동적으로 연결관계가 지속적으로 변화하는 상황이 아니고, 객체간의 연결관계가 이미 고정되어있는 상황이라면, DFS를 이용하여 탐색을 완료한 후에 constant time에 연결여부를 확인할 수 있다.
이것은 connected component라는 연결된 vertex들을 갖는 집합을 생성하고, 각각의 connected component에 대해 DFS를 수행하는 방식으로 구현할 수 있다.
6. Graph-processing challenges
그래프 이론은 아직도 활발하게 연구중인 분야고 열린문제도 많다.
그래프 문제는 난이도에 따라 다음과 같이 분류될 수 있다.
- Any programmer could do it
- Typical diligent algorithms student could do it //Cycle, Euler tour, etc...
- Hire an expert //Hard problem(very difficult and complex algorithm, etc...)
- Intractable //Hamilton tour(NP-complete problem), etc...
- No one knows //graph isomorphism(Open problem)
- Impossible
이렇게 문제를 정의하고 분류하면, 현재 상황에서 해결불가능한건지 가능한건지 분류하고 빠르게 의사결정을 할 수 있을 것이다...
'프로그래밍 > Algorithm - 2' 카테고리의 다른 글
| 6. Maximum Flow & Minimum Cut (0) | 2024.02.18 |
|---|---|
| 5. Shortest Paths (0) | 2024.02.13 |
| 4. Minimum spanning tree(MST) (1) | 2024.02.12 |
| 3. Directed Graph(Digraph) (1) | 2024.01.30 |
| 1. Introduction (1) | 2024.01.16 |
