Graph&Tree | 그래프와 트리
그래프
그래프의 용어 정리
- 노드(node,vertex) : A,B,C,D…와 같은 그래프를 구성하는 하나의 요소이다. 노드는 키값과 다음노드를 가르키는 포인터로 구성되어있다.
- 간선(edge,arc) : 노드와 노드사이의 연결선 그래프는 크게 세가지로 나누어 진다.
- 방향성을 가진 간선을 이용하는 방향 그래프
- 방향성이 없는 간선을 이용하는 무방향 그래프
- 가중치를 가진 간선을 이용하는 가중치 그래프
- 출발 간선(Out- degree) 현재 노드로부터 다른 노드로 향하는 간선을 말한다.
- 도착 간선(In- degree) 다른 노드로 부터 현재 노드로 도착하는 간선을 말한다.
코드에서 그래프의 표현방식
그래프는 두 가지 표현 방식이 있다.
-
인접 행렬 방식
인접 행렬 방식은 행렬 개념의 표를 이용해 표현하는 방식이다.
1번 노드에서 3번 노드로 가는 간선이 있다면 2차원 배열을 선언하고 1행 3열에 해당하는 칸에 1(true)값을 저장하는 방식이다.
아래에서 설명할 무방향 그래프의 경우 1번 노드에서 3번노드로 가는 간선이 있다면 당연히 3번 노드에서 1번노드로 가는 간선도 존재하는 것이기 때문에 대칭 행렬이 그려지게 된다.
하지만, 방향 그래프의 경우 대칭되지않는 경우도 존재 할 수 있다.
또 가중치가 존재하는 그래프에선 행렬에 1(true), 0(false) 값이 아닌 가중치가 저장된다.
-
인접 리스트 방식
간선의 연결정보만을 가지고 자료 구조의 기본이되는 연결리스트처럼 1번노드가 자신과 연결된 다음 노드의 주소값을 가지고 있는 형태로 구현하는 방식이다.
보기 편하게 분해해 놓은 그림이다. 그림과는 조금다르게
→ B ( B로 가는간선 이라는 의미)
B ⇒ {→ A, → C, → E} (B는 A로가는 간선, C로 가는 간선, E로 가는 간선을 가진다는 의미)
위 와 같은 형태로 표현된다.
방향그래프
방향성을 띄는 간선을 가진 그래프이다. 그래프 탐색을 진행할 때 방향성의 반대로는 탐색 하지 못한다.
방향 그래프의 인접행렬방식 코드
알파벳을 각각 A-1, B-2 이런식으로 가정한다.
또 0번 노드는 취급 하지 않아서 배열의 크기가 (전체 노드 개수 + 1)^2 이다.
//전체 노드 개수
int nodeCnt = 6;
// 그래프의 간선정보(대개 하위로 내려가는 방향으로만 주어짐
// {5,4}는 역방향만 존재 하므로 예외)
int[][] edgeInfo = new int[][]{{1,2},{2,3},{2,5},{3,4},{3,5},{5,4},{5,6}};
// 인접 행열 방식의 그래프
int[][] graph = new int[nodeCnt+1][nodeCnt+1];
for(int i = 0; i < edgeInfo.length; i++) {
graph[edgeInfo[i][0]][edgeInfo[i][1]] = 1;
}
//출력
/*
\ 0 1 2 3 4 5 6
0 0, 0, 0, 0, 0, 0, 0
1 0, 0, 1, 0, 0, 0, 0
2 0, 0, 0, 1, 0, 1, 0
3 0, 0, 0, 0, 1, 1, 0
4 0, 0, 0, 0, 0, 0, 0
5 0, 0, 0, 0, 1, 0, 1
6 0, 0, 0, 0, 0, 0, 0
*/무방향그래프
방향 상관없이 탐색할 수 있다 구현할때는 두 가지 방향 다 탐색이 가능하게 구현해야한다는 의미 이다.
무방향 그래프의 인접행렬방식 코드
//전체 노드 개수
int nodeCnt = 6;
// 그래프의 간선정보(대개 하위로 내려가는 방향으로만 주어짐)
int[][] edgeInfo = new int[][]{{1,2},{2,3},{2,5},{3,4},{3,5},{4,5},{5,6}};
// 인접 행열 방식의 그래프
int[][] graph = new int[nodeCnt+1][nodeCnt+1];
for(int i = 0; i < edgeInfo.length; i++) {
graph[edgeInfo[i][0]][edgeInfo[i][1]] = 1;
graph[edgeInfo[i][1]][edgeInfo[i][0]] = 1;
}
//출력
/*
\ 0 1 2 3 4 5 6
0 0, 0, 0, 0, 0, 0, 0
1 0, 0, 1, 0, 0, 0, 0
2 0, 1, 0, 1, 0, 1, 0
3 0, 0, 1, 0, 1, 1, 0
4 0, 0, 0, 1, 0, 1, 0
5 0, 0, 1, 1, 1, 0, 1
6 0, 0, 0, 0, 0, 1, 0
*/가중치 그래프
간선에 가중치가 존재하고 그래프의 탐색을 결정하는 요소에 가중치의 최소값을 선택해서 탐색하는 조건이 추가될 수 있다.
가중치 그래프를 쉽게 이해하는 방법은 가중치를 노드간 이동에 소요되는 시간이라고 생각하면 쉽게 이해할 수 있다.
A → B : A노드에서 B노드로 이동하는 데에는 3분이라는 시간이 소요된다.
이 와 같은 개념을 가진 상태로 가중치 방향, 무방향 그래프도 이해해보자
- 가중치 방향 그래프 A → E : 탐색 노드의 최소 개수와 최소 소요시간(최소 가중치)를 만족하기 위해서는 A → B → E 이 경로가 가장 합리적이다. 하지만 B → E의 경우 역 방향 간선이므로 해당 방향으로 탐색을 진행 할 수 없다. ∴ A → B → C → E 순서로 탐색하는게 가장 합리적인 탐색이다.
- 가중치 무방향 그래프 A → E : 무방향 그래프이기 떄문에 탐색 노드의 최소 개수만 만족하는 탐색 순서는 A → B → E 순서의 탐색이 가장 합리적이다. 하지만 B → E의 경우 가중치가 20이나 되기때문에 탐색 노드 수가 늘어나더라도 더 합리적인 탐색 루트가 존재한다. ∴ A → B → C → E 순서로 탐색하는게 가장 합리적인 탐색이다.
이번 파트는 가중치에 대해 설명하는 파트로 가중치라는 개념에 중점을 둬서 위와 같은 결론이 나오는 것이고 최소 노드 수를 우선으로 하는 탐색 조건이라면 위의 설명과 결론이 다를 수 있다. 하지만 대부분 가중치를 가진 그래프가 주어지는 상황에선 가중치가 가장 우선적인 탐색 조건으로 적용된다.
- 갑자기 떠오른 너무 찰떡 실생활 비유 여러번 환승하더라도 더 빠른 루트로 약속 장소에 갈 것 인지 오래 걸리더라도 한 번 만 환승하는 루트로 약속 장소에 갈 것 인지 정도의 차이점이다.
관련 알고리즘으로는 최소 비용 신장 트리 알고리즘(minimum spanning tree, MST)이 있다.
가중치가 적용된 인접행렬방식 코드(무방향)
//전체 노드 개수
int nodeCnt = 6;
// 그래프의 간선정보(대개 하위로 내려가는 방향으로만 주어짐)
// {startNode, endNode, weight}
int[][] edgeInfo = new int[][]{{1,2,3},{2,3,4},{2,5,20},{3,4,9},{3,5,2},{4,5,1},{5,6,10}};
// 인접 행열 방식의 그래프
int[][] graph = new int[nodeCnt+1][nodeCnt+1];
for(int i = 0; i < edgeInfo.length; i++)
graph[edgeInfo[i][0]][edgeInfo[i][1]] = edgeInfo[i][2];
graph[edgeInfo[i][1]][edgeInfo[i][0]] = edgeInfo[i][2];
}
//출력
/*
\ 0 1 2 3 4 5 6
0 0, 0, 0, 0, 0, 0, 0
1 0, 0, 3, 0, 0, 0, 0
2 0, 3, 0, 4, 0, 20, 0
3 0, 0, 4, 0, 9, 2, 0
4 0, 0, 0, 9, 0, 1, 0
5 0, 0, 20, 2, 1, 0, 10
6 0, 0, 0, 0, 0, 10, 0
*/트리
트리는 그래프에서 포함된 개념이다.
실질적으로는 방향이 존재하는 방향 그래프에 속 하지만 루트노드에서 리프노드를 향하는 단방향 방향성을 가지므로 방향성 표현이 생략 되었다. 하나의 Indegree와 여려개의 Out-degreefh 이루어져 있다.
트리의 용어 정리
노드, 간선, In,Out-degree는 그래프와 똑같다.
- 루트(root) : 부모노드가 없는 최상위 노드
- 부모(parent) : 자식 노드를 가진 노드
- 자식(child) : 부모노드의 하위노드
- 형제(brother) : 같은 레벨의있는 노드들
- 리프(leaf) : 자식 노드가 없는 노드
- 깊이(depth) : 루트 노드에서 어떤 노드까지의 간선 수
- 높이(height) : 임의의 두 노드 사이의 최대 길이의 간선 수
- 단 수(level) : 트리의 단 수
- 경로(path) : 어떤 노드에서 어떤 노드까지의 경로에 있는 노드들
- 경로 길이(path length) : 어떤 노드에서 어떤 노드까지의 경로에 있는 노드들의 수
- 폭(breadth) : 리프 노드의 개수
- 거리(distance) : 어떤 노드에서 어떤 노드까지의 경로에 있는 간선 수
- 서브트리(sub-tree) : 루트노드가아닌 다른 노드를 루트노드로 하는 전체 트리의 일부분
트리의 종류
- 편향 트리 모든 노드가 자식을 하나씩만 가지는 트리
- 이진트리 모든 노드의 Out-degree가 2이하인, 자식 노드가 2개 이하인 트리
- 이진 탐색 트리 이진 트리 구조에서 각 노드가 가지는 값이 부모보다 작으면 왼쪽 자식, 부모보다 크면 오른쪽 자식 이라는 규칙에 벗어나지 않게 구성된 트리
코드로 표현한 트리
A는 1번 노드 , B는 2번 노드와같은 방식으로 숫자로 치환해서 표현함
//전체 노드 개수
int nodeCnt = 10;
// 트리의 간선 정보
int[][] edgeInfo = new int[][]{{1,2},{1,3},{2,4},{2,5},{3,6},{3,7},{4,8},{4,9},{5,10}};
// 인접 행열 방식의 그래프
int[][] tree = new int[nodeCnt+1][nodeCnt+1];
for(int i = 0; i < edgeInfo.length; i++)
tree[edgeInfo[i][0]][edgeInfo[i][1]] = 1;
}
//출력
/*
\ 0 1 2 3 4 5 6 7 8 9 10
0 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
1 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0
2 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0
3 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0
4 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0
5 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1
6 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
7 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
8 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
9 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
10 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
*/인접 행렬은 낭비 되는 공간이 많아서 규모가 커지면 인접 리스트로 구현하는것이 효율적이다.
// 전체 노드 개
int nodeCnt = 10;
// 트리의 간선 정보
int[][] edgeInfo = new int[][]{{1,2},{1,3},{2,4},{2,5},{3,6},{3,7},{4,8},{4,9},{5,10}};
ArrayList<Integer>[] tree = new ArrayList[nodeCnt+1];
for(int i = 1; i <= nodeCnt; i++) {
tree[i] = (new ArrayList<Integer>());
}
for(int i = 0; i < edgeInfo.length; i++) {
tree[edgeInfo[i][0]].add(edgeInfo[i][1]);
}
/*
0
1 {2,3}, 2 {4,5}, 3 {6,7}, 4 {8,9}, 5 {10}
6 {}, 7 {}, 8 {}, 9 {}, 10 {}
*/
좋은 글 감사합니다.