그래프 Graph는 사물이나 현상을 정점 vertex이나 간선 edge으로 표현한 것이다. 정점은 대상, 간선은 대상 간의 관계를 나타낸다. 선형 자료구조나 트리 구조로는 표현할 수 없는 다 대 다 관계를 표현할 수 있다.
그래프의 종류
- 무방향 그래프 undirected graph
간선에 방향이 없는 그래프다. 정점 a와 정점 b를 동일하게 가르킨다. 즉, (a,b), (b,a)이다.
- 방향 그래프 directed graph
digraph라고도 한다. 간선에 방향이 있는 그래프다. 무방향 그래프와 다르게 한쪽 방향만 가르킨다.
- 완전 그래프 complete graph
각 정점에서 다른 모든 정점으로 가는 간선이 존재하는 그래프를 뜻한다. 즉, 주어진 정점 수에 대해 간선수가 최대이다.
정점이 n개인 완전 그래프인 경우 간선 수를 알 수 있는데,
무방향 그래프인 경우 n(n-1)/2 개
방향 그래프인 경우 n(n-1) 개
- 가중 그래프 weighted graph
간선에 '가중치'가 주어진 그래프다. 이 가중치는 두 정점 사이의 비용이나 거리, 시간 등을 의미한다.
그래프 용어
- 인접 adjacent, 부속 incident
정점 a와 정점 b 사이에 간선이 존재하면 a와 b는 인접(adjacent)하다, (a,b)는 a와 b에 부속(incident)되어 있다, 라고 한다.
- 차수 degree
정점에 부속된 간선의 수를 의미한다. 아래를 예시를 들면, 정점 A의 차수는 2, 정점 B의 차수는 3이다.
방향 그래프의 경우는 진입하거나 진출하는 차수를 합한다.
진출하는 차수를 out-degree, 진입하는 차수를 in-degree라고 한다. 위의 예시에서 무방향 그래프이기 때문에 정점 D의 out-degree는 3, in-degree는 3이다.
- 경로 path
그래프에서 한 정점에서 정점으로 간선을 따라 도달할 수 있는 길을 의미한다.
- 단순 경로 simple path
모두 다른 정점으로 구성된 경로다. 단 시작 정점과 마지막 정점은 동일해도 된다.
- DAG directed acyclic graph
사이클이 없는 방향그래프다.
- 연결 그래프 connected graph
모든 정점들 사이에 경로가 있는 그래프를 칭한다.
하단 오른쪽의 예가 왜 연결 그래프가 아닌가 하면, 정점 A로 가는 경로가 없기 때문이다.
- 부분그래프 subgraph
원래 그래프에서 정점이나 간선의 일부를 떼어 만든 그래프다.
그래프의 구현
인접행렬 adjacency matrix - 2차원 배열로 구현
n개의 정점을 가진 그래프는 n*n 정방행렬로 표현한다. 행렬의 행과 열 번호는 그래프의 정점을 의미한다.
인접 행렬이 M일 때, 정점 i에서 정점 j로의 간선이 존재하면 M[i][j]는 1, 아니라면 0이다.
행의 합이 진출차수, 열의 합이 진입차수라 생각하면 된다. 아래 이미지의 정점 1의 진입차수는 1, 진출차수는 1이다.
인접행렬의 java 구현을 확인해보자.
public class MatrixGraph {
private int[][] matrix;
private int ver; //정점의 갯수
public MatrixGraph(int n) { //matrixgraph를 만들면 다음과 같이 생성.
matrix = new int[n][n];
ver = n;
}
//간선을 삽입하는 함수
public void insertEdge(int v1, int v2) {
//v1와 v2이 0보다 작거나 정점과 같거나 크면 안된다.
if (v1<0 || v1>=ver || v2<0 || v2>=ver) {
System.out.println("그래프에 없는 정점입니다.");
}
else {
matrix[v1][v2]=1;
}
}
public void printAdjMatrix() {
for(int i=0; i<ver; i++) {
for(int j=0; j<ver; j++) {
System.out.print(matrix[i][j] + " ");
}
System.out.println();
}
}
//지정한 정점 사이에 간선 여부를 확인하는 함수다.
public boolean hasEdge(int v1, int v2) {
if(matrix[v1][v2]==1) {
return true;
}
else {
return false;
}
}
//해당 정점의 진출차수를 구하는 함수
public int outDegree(int num) {
int out = 0;
for (int i=1; i<ver; i++) {
if(matrix[num][i]==1) {
out +=1;
}
}
return out;
}인접행렬은 정점 수가 n개라면 간선 수와는 상관없이 n*n 크기의 배열을 생성하므로 희소행렬을 생성한다면 메모리를 낭비한다. 따라서 인접행렬은 간선의 밀도가 높은 경우에 적합한 방법이다. 희소행렬처럼 무의미한 정보를 다수 포함하지 않기 때문이다.
인접리시트 adjacency list - 연결리스트로 표현
각 정점마다 연결리스트를 두어 표현하는 방법이다. 정점 갯수에 따른 Node type의 배열을 생성하고 정점 사이의 간선은 연결리스트로 표현하면 된다.
다음은 인접리스트를 java로 구현하였다. 깊이 우선 탐색(DFS)는 아래에서 배울 수 있다.
package hw10_1;
public class ListGraph{
private class Node {
int vertex;
Node link;
}
private Node[] list;
private int vern;
public ListGraph(int n) {
list = new Node[n];
vern=n;
}
//삽입
public void insertEdge(int v1, int v2) {
if(v1<0 || v1>=vern || v2<0 || v2>=vern) {
System.out.println("그래프에 없는 정점입니다!");
}
else {
Node newNode = new Node();
newNode.vertex = v2;
newNode.link = list[v1];
list[v1] = newNode;
}
}
//프린트
public void printAdjList() {
for(int i=0; i<vern; i++) {
System.out.print("정점 " + i + "의 인접리스트");
for(Node temp = list[i]; temp != null; temp = temp.link) {
System.out.print(" -> "+ temp.vertex);
}
System.out.println();
}
}
// 리스트 간선 존재 여부 출력
public boolean hasEdge(int v1, int v2) {
Node temp = list[v1];
while(temp!=null) {
if(temp.vertex==v2) {
return true;
}
temp=temp.link;
}
return false;
}
// 매개변수로 받은 정점의 진출 차수 리턴
public int outDegree(int v) {
Node temp = list[v];
int result=0;
while(temp!=null) {
result+=1;
temp=temp.link;
}
return result;
}
// depth first search함수
boolean visited[] = new boolean[5];
public boolean isFull() {
int res = 0;
for (int i=0; i<5; i++) {
if(visited[i]==false) {
}
else {
res+=1;
}
}
return res == 5;
}
//깊이 우선 탐색 구현
public void DFS(int v) {
visited[v]=true;
System.out.print(v+" ");
//t에 v번째 위치값을 주고, visited 배열이 모두 true가 될 때까지
//t.vertex번째 visited가 true인지 살펴본다. 맞다면 다음 링크로 이동하고, 아니라면
//t.vertex번째 visited를 true로 만들기 위해 DFS를 다시 실행한다.
Node t = list[v];
while(!isFull()) {
if(visited[t.vertex]==true) {
t=t.link;
}
else {
DFS(t.vertex);
}
}
}
}
그래프 순회
하나의 정점에서 시작해 모든 정점을 한 번씩 방문 하는 것을 말한다. 이른 바 '탐색'이라 할 수 있다. 가장 기본적이면서 가장 중요한 것은 깊이 우선 탐색과 너비 우선 탐색이다.
깊이 우선 탐색 Depth First Search DFS
DFS를 우물 파기에 비유하자면 이렇다. 한 지점을 골라 팔 수 있을 때까지 깊게 파다가 아무리 파도 물이 나오지 않으면 나와서 다른 지점을 골라서 판다. DFS는 이렇듯 가장 깊고 먼 경로까지 순회를 마쳤다면 돌아와서 다른 정점의 경로를 순회한다. DFS는 스택이나 재귀 알고리즘을 이용하여 구현할 수 있다. 위의 코드는 재귀알고리즘을 java로 구현한 것이다.
너비 우선 탐색 Breadth First Search BFS
가까운 정점을 먼저 방문하고 멀리 있는 정점들은 나중에 방문하는 순회 방법이다. 우물파기로 비유하면, 여러 지점을 파보고 물이 나오지 않으면 파놓은 다른 지점에서 다시 조금 더 파는 깊게 파는 것이다. BFS는 선입선출 구조의 큐를 사용하여 구현할 수 있다.
그래프의 신장 트리
신장 트리 Spanning tree
무방향 연결 그래프 중에서 정점 n개를 전부 포함하고, 간선은 n-1개만 포함하여 모든 정점이 연결되는 부분그래프 subgraph다. 즉, 최소 갯수의 간선으로 모든 정점이 연결되도록 한다. 없는 간선은 포함해서는 안된다.
최소 비용 신장 트리 Minimum cost spanning tree
무방향 가중 연결 그래프의 신장 트리 중에서 간선의 가중치 합이 최소인 신장 트리를 뜻한다.
최소 비용 신장 트리를 구하는 알고리즘은 다음과 같이 나뉜다.
- Kruskal 알고리즘 (1과 2가 있지만 여기서는 2만 다루도록 하자. 안배웠다.)
정점만 그대로 둔, 간선이 없는 상태에서 가중치가 낮은 순서로 간선을 삽입한다.
1. 모든 간선의 가중치에 따라 오름차순으로 정렬한다.
2. 사이클을 형성하지 않는 한도 내에서 가중치가 가장 작은 간선을 고른다. 사이클을 형성하면 다음 간선을 고른다.
3. 모든 정점을 포함할 때까지 2번을 반복한다.
- Prim 알고리즘
하나의 정점에서 시작하여 모든 정점을 포함할 때까지 최소값의 가중치의 간선을 정하는 것은 kuskal 알고리즘과 동일하나, prim은 가중치의 간선을 오름차순으로 정렬해놓지 않는다.
