Chapter 5. Graph
1. 그래프란?
정점객체와 간선객체로 이루어진 자료구조이다. 일상 속에서 자주 사용되는 자료구조 중 하나이다.
용어
node [vertex] : 위치라는 개념이다. 정점이라고도 부른다.
edge : 노드를 연결하는 선을 말하며 간선에 가중치를 둘 수 있다. 간선이라고도 부른다.
adjacent vertex : 간선에 의해 직접 연결된 정점을 말한다.
degree : 무방향 그래프에서 하나의 정점에 인접한 정점의 수이다.
무방향 그래프에 존재하는 정점의 모든 차수의 합 = 그래프의 간선 수의 2배이다.
Subgraph : 그래프의 부분 그래프를 말한다.
Path : v->w의 모든 간선의 나열이다.
Cycle : 해당 노드에서 시작하여 다시 해당 노드로 돌아오는 경우를 말한다.
Complete Graph : 모든 정점 사이의 간선이 존재하며 undirected Grahpe일 경우 간선의 갯수 = n(n-1) / 2이다.
Conncted Graph : 무방향 그래프에서 모든 정점 쌍에 대해 경로가 존재함을 말한다.
Strongly Conncted : 방향 그래프에서, 모든 정점들 v->w 사이의 Path가 존재함을 말한다.
Strongly Connected Graph : 방향 그래프의 서브 그래프로 Strongly Conntected를 만족하는 정점 갯수가 최대일때를 말한다.
특징
그래프는 네트워크 모델을 나타낼 때 사용하며 정점과 정점 사이의 여러 Path가 존재 할 수 있다. 또한 루트 노드라는 개념이 없고 부모-자식 형태의 개념이 없다.
예를 들어, 네트워크 망, 지도, 지하철 노선도, 네비게이션 등 모델링을 할 때 사용하며
포장도로를 설치하는데 가장 최소 비용, 출발지 -> 목적지 까지의 길 찾기 등 많은곳에서 사용된다.
ADT 기능 명세
정점과 간선 객체로 데이터를 저장한다.
e.endVerticies() : 간선에 연결된 두 정점을 리턴한다.
e.opposite(v) : v의 반대 정점을 리턴한다.
v.isAdjacentTo(u) : v와 u가 인접한지를 알아낸다.
incidentEdges(v) : v에 연결된 모든 간선을 리턴한다.
verticies() : 모든 정점을 리턴한다.
edges() : 모든 간선을 리턴한다.
insertVertex() : 정점 삽입
intsertEdges() : 간선 삽입
removeVertex() : 정점 삭제
removeEDges() : 간선 삭제
2. 그래프 표현 방식
1. Adjacent Matrix
인접 행렬로 구현시 n*n 행렬을 사용한다. 왼쪽 사진을 보면 행렬에는 간선 정보를 나타내며 index가 의미하는것은 정점을 말한다. 그림에는 없지만 정점 객체를 따로 만들어 표현하고 만약 정점 객체의 id가 0~n-1이 아니면 hash, map 등 다양한 방식으로 표현한 후 이를 index로 transfer한다. 여기서는 O(1)에 정점을 접근한다고 생각한다.
만약 해당 정점에서 다른 정점으로 못 갈 경우 무한으로, 자기 자신은 0으로 처리하며, 간선이 존재할 경우 가중치를 값으로 저장한다.
만약 간선에 여러 정보(간선의 이름, cost, 기타 등)가 들어갈 경우, 행렬의 Type은 모두 급격히 증가하게 된다. 따라서 공간의 낭비를 줄이고자 오른쪽 사진처럼 인접행렬을 표시한다.
정점객체와 간선객체가 이루어져있다. 행렬에는 포인터로 간선에 정보가 있다면 간선 객체를 가리킨다.
만약 Class 크기가 T라면 T x (N^2) -> 4*(N^2) + m * T로 크기가 줄어든다.
정점과 정점이 연결되었는지 가중치는 얼마인지에 대한 isAdjacentTo연산이 O(1)인 장점과 구현이 쉽다는 장점이 있다.
하지만 정점 삽입, 삭제가 O(N^2)에 수행되며 해당 정점과 연결된 간선들을 보는것이 O(n)에 수행되는 단점이 있다.
2. Adjacent List
정점객체와 간선 객체로 이루어져 있으며 간선을 리스트 형식으로 매단다.
왼쪽 사진은 배열을 정점으로 표시하며 해당 정점에 연결된 간선을 리스트 형식으로 표현하였다. 하지만 정점 추가/삭제의 cost가 n만큼 들기 때문에 오른쪽 사진처럼 벡터형식으로 바꿨다. 또한 무향 그래프에서 간선의 중복을 막고자 즉, 공간낭비를 줄이고자 정점과 간선의 중간단계를 만들어 진행하였다.
해당 정점과 연결된 간선들을 빠르게 찾을 수 있으며 정점 삽입, 삭제가 빠른시간에 수행될 수 있지만 정점과 정점사이의 weight이나 연결유무를 빠른시간 내에 못찾는 단점이 있다.
Adjacent Matrix vs Adjacent List
- 해당 정점과 연결된 간선들을 찾을 때 인접 리스트는 연결된 degree만큼 순회를 하면 되지만, 인접 행렬은 한 행을 모두 돌아야 하기 때문에 O(n)이 소요된다.
- 두 정점이 이웃한지를 확인 하기 위해 인접 리스트는 해당 정점들의 연결된 간선들을 모두 확인 하므로 두 정점 중 degree가 작은 만큼의 coast가 들지만, 인접 행렬은 배열로 구현되어 O(1)만에 확인할 수 있다.
- 정점 삽입 시 인접 리스트는 끝에 노드를 추가하면 되므로 O(1)만에 수행되지만, 인접 행렬은 Matrix를 재 할당 해야하므로 O(n^2)의 cost가 든다.
- 간선 삽입 시 인접 행렬, 인접 리스트 모두 O(1)만에 수행 가능하다.
- 정점 삭제 시 인접 리스트는 해당 정점에 연결된 간선들을 모두 지워야 하므로 degree만큼의 cost가 들고, 인정 행렬은 Matrix를 재할당 해야하므로 O(n^2)의 cost가 든다.
- 간선 삭제는 인접 행렬, 인접 리스트 모두 O(1)만에 수행 가능하다.
3. Traversal
Tree에서 순회는 PreOrder, PostOrder, InOrder가 있지만 그래프에서의 순회는 DFS, BFS가 존재한다. 이때 각 node, edge는 정확히 한번씩 visit한다.
DFS(Depth First Search)
갈 수 있을 때까지 가고 못가면 해당 정점을 Pop한다. Stack을 이용하여 구현하며 정점, 간선의 방문 여부를 체크 해야 한다. 재귀함수는 Stack으로 구현 돼있어 보통 재귀함수를 이용하여 구현한다.
- v의 incidentEdges 중 안 간곳으로 간다. (간선 체크)
- 마주보는 정점이 방문 했다면 간선은 Back Edge로 체크한다.
- 마주보는 정점이 방문을 안 했다면 간선은 Tree Edge로 체크하고 Stack에 정점을 Push 한 후 재귀 호출을 한다.
위 작업을 Stack이 빌 때까지 수행한다.
인접 행렬로 구현 시 O(n^2)에 수행되며, 인접 리스트 구현시 O(n+m)의 수행시간을 가진다.
n of while X (incidentEdges + 그 외 연산)
BFS(Breadh First Search)
한번씩 하나의 반경(distance)을 넓혀가는 방식이다. Queue를 이용하여 구현하며 정점, 간선의 방문 여부를 체크한다.
- v의 incidentEdges 중 안 간곳으로 간다. (간선 체크)
- 마주보는 정점이 방문 했다면 간선은 Back Edge로 체크한다.
- 마주보는 정점이 방문을 안 했다면 간선은 Tree Edge로 체크하고 Queue에 정점을 넣고 계속 incidentEdges 중 안 간곳을 체크한다.
위 작업을 Queue가 빌 때까지 수행한다.
인접 행렬로 구현 시 O(n^2)에 수행되며, 인접 리스트 구현시 O(n+m)의 수행시간을 가진다.
n of while X (incidentEdges + 그 외 연산)
4. Strongly Connected Component
Strongly Connected는 Directed Graph에서 모든 정점들 v -> w의 경로가 존재함을 말한다. 이때 Strongly Connected Component라 함은, 그래프 G에서 Subgraph로 Strongly Connected가 되는 정점갯수가 최대일때의 그래프 집합을 말한다.
Step
- 그래프 G를 DFS를 수행하면서 Finish 돼는 node를 Stack에 Push한다. (finish가 돼는 노드는 더 이상 갈 수 있는 node가 없음을 말한다.)
- 그래프 transpose G(G의 방향을 바꾼 그래프)에 대해서 Stack에서 노드를 Pop을 하고 차례로 DFS를 수행한다.
- 이후 끝나는 시점으로 노드들을 그룹화 한다.
