그래프(Graph)란 인터넷, 도로, 운송, 전력, 상하수도망, 신경망, 화학성분 결합 등 광범위한 분야에서 활동되는 자료구조입니다. 연결된 정점 간 관계를 표현할 수 있습니다.
모든 정점이 서로 연결된 완전 그래프는 정점이 N개일 경우 간선의 수는 n(n-1)/2개입니다. 가중치(Weighted) 그래프는 간선에 값이 있어 이동 비용이 발생합니다. 가중치는 실제 두 정점 사이의 거리가 될 수도 있고, 두 정점을 연결하는 간선을 지나는 데에 소요되는 시간일 수도 있습니다. 응용에 따라 가중치가 음수인 경우도 존재합니다. 최소 신장 트리(Minimum Spannig Tree)를 찾기 위한 알고리즘과 다양한 최단 경로를 찾는 알고리즘에 활용할 수 있습니다.
그래프는 정점(Vertex)과 간선(Edge)의 집합으로 하나의 간선은 두 개의 정점을 연결합니다. 그래프에서 정점들이 서로 연결되어 있는 부분을 연결 성분(Connected Component)라고 합니다. 간선에 방향이 있는 그래프를 방향 그래프(Directed Graph), 방향이 없는 그래프를 무방향 그래프(Undirected Graph)라고 합니다. 무방향 그래프는 양방향으로 이동이 가능합니다.
정점에 인접한 정점의 수를 차수(Degree)라고 정의합니다. 방향 그래프에서는 방향에 따라 진입 차수(In-Degree)와 진출 차수(Out-Degree)로 구분합니다. 경로(Path)는 시작점에서 도착점까지의 정점들을 나열하여 표현합니다.
경로상의 정점들이 모두 다른 경로를 특별히 단순 경로(Simple Path)라고 합니다. 시작점과 도착점이 동일한 단순 경로는 사이클(Cycle)이라고 합니다.
그래프를 구현하는 방법에는 두 가지가 있습니다. 인접 행렬(Adjacency Matrix)과 인접 리스트(Adjacecy List)입니다. 특징은 다음 표와 같습니다.
| 인접 행렬 | 인접 리스트 | |
| 구현 | 2차원 배열 | 연결 리스트 |
| 장점 | 간선 정보의 확인과 업데이트가 빠름 | 메모리 사용량이 상대적으로 적음 노드의 추가와 삭제가 빠름 |
| 단점 | 인접 행렬을 위한 메모리 공간을 차지함 |
간선 정보 확인이 상대적으로 오래 걸림 |
| 특정 간선 검색 |
O(1) | O(degree(V)) |
| 정점의 차수 계산 |
O(N) | O(degree(V)) |
| 전체 노드 탐색 |
O(N^2) | O(E) |
| 메모리 | N * N | N + E |
| 상황 | 노드의 개수가 적고 간선의 수가 많을 때 유리 |
노드의 개수가 많고 간선의 수가 적을 때 유리 |
| 예 | 밀집 그래프(Dense Graph) | 희소 그래프(Sparse Graph) |
N은 전체 정점의 개수, E는 전체 간선의 개수를 의미합니다.
인접 행렬 그래프 구현 코드
class GraphMatrix {
char[] vertices;
int[][] adjMat;
int elemCnt;
public GraphMatrix() {}
public GraphMatrix(int size) {
this.vertices = new char[size];
this.adjMat = new int[size][size];
this.elemCnt = 0;
}
public boolean isFull() {
return this.elemCnt == this.vertices.length;
}
public void addVertex(char data) {
if (isFull()) {
System.out.println("Graph is Full");
return;
}
this.vertices[this.elemCnt++] = data;
}
// 무방향 그래프
public void addEdge(int x, int y) {
this.adjMat[x][y] = 1;
this.adjMat[y][x] = 1;
}
// 방향 그래프
public void addDirectedEdge(int x, int y) {
this.adjMat[x][y] = 1;
}
public void deleteEdge(int x, int y) {
this.adjMat[x][y] = 0;
this.adjMat[y][x] = 0;
}
public void deleteDirectedEdge(int x, int y) {
this.adjMat[x][y] = 0;
}
}
인접 리스트 그래프 구현 코드
class Node {
int id;
Node next;
public Node(int id, Node next) {
this.id = id;
this.next = next;
}
}
class GraphList {
char[] vertices;
Node[] adjList;
int elemCnt;
public GraphList() {}
public GraphList(int size) {
this.vertices = new char[size];
this.adjList = new Node[size];
this.elemCnt = 0;
}
public boolean isFull() {
return this.elemCnt == this.vertices.length;
}
public void addVertex(char data) {
if (isFull()) {
System.out.println("Graph is Full");
return;
}
this.vertices[elemCnt++] = data;
}
// 무방향 그래프
public void addEdge(int x, int y) {
this.adjList[x] = new Node(y, this.adjList[x]);
this.adjList[y] = new Node(x, this.adjList[y]);
}
//방향 그래프
public void addDirectedEdge(int x, int y) {
this.adjList[x] = new Node(y, this.adjList[x]);
}
}
각 노드에 방문했는지 여부를 체크하는 그래프 탐색 연산에는 배열과 스택을 이용하여 구현하는 깊이 우선 탐색(Depth First Search; DFS)과 배열과 큐를 이용하여 구현하는 너비 우선 탐색(Breath First Search; BFS)가 있습니다.
그래프에서의 DFS는 임의의 정점에서 시작하여 이웃하는 하나의 정점을 방문하고, 방금 방문한 정점의 이웃 정점을 방문하며, 이웃하는 정점들을 모두 방문한 경우에는 이전 정점으로 되돌아가서 탐색을 수행하는 방식으로 진행됩니다.
그래프에서의 BFS는 임의의 정점 s에서 시작하여 s의 모든 이웃하는 정점을 방문하고, 방문한 정점의 이웃 정점들을 모두 방문하는 방식으로 그래프의 모든 정접을 방문합니다. BFS는 이진 트리에서의 레벨 순회와 유사합니다.
인접 행렬 그래프 DFS, BFS 구현 코드
class GraphMatrix2 extends GraphMatrix {
public GraphMatrix2(int size) {
super(size);
}
public void dfs(int id) {
boolean[] visited = new boolean[this.elemCnt];
Stack<Integer> stack = new Stack<>();
stack.push(id);
visited[id] = true;
while (!stack.isEmpty()) {
int curId = stack.pop();
for (int i = this.elemCnt - 1; i >= 0; i--) {
if (this.adjMat[curId][i] == 1 && visited[i] == false) {
stack.push(i);
visited[i] = true;
}
}
}
}
public void bfs(int id) {
boolean[] visited = new boolean[this.elemCnt];
Queue<Integer> queue = new LinkedList<>();
queue.offer(id);
visited[id] = true;
while (!queue.isEmpty()) {
int curId = queue.poll();
for (int i = this.elemCnt - 1; i >= 0; i--) {
if (this.adjMat[curId][i] == 1 && visited[i] == false) {
queue.offer(i);
visited[i] = true;
}
}
}
}
}
인접 리스트 그래프 DFS, BFS 구현 코드
class GraphList2 extends GraphList {
public GraphList2(int size) {
super(size);
}
public void dfs(int id) {
boolean[] visited = new boolean[this.elemCnt];
Stack<Integer> stack = new Stack<>();
stack.push(id);
while (!stack.isEmpty()) {
int curId = stack.pop();
Node cur = this.adjList[curId];
while (cur != null) {
if (visited[cur.id] == false) {
stack.push(cur.id);
visited[cur.id] = true;
}
cur = cur.next;
}
}
}
public void bfs(int id) {
boolean[] visited = new boolean[this.elemCnt];
Queue<Integer> queue = new LinkedList<>();
queue.offer(id);
visited[id] = true;
while (!queue.isEmpty()) {
int curId = queue.poll();
Node cur = this.adjList[curId];
while (cur != null) {
if (visited[cur.id] == false) {
queue.offer(cur.id);
visited[cur.id] = true;
}
cur = cur.next;
}
}
}
}그래프에서의 DFS는 그래프의 기본적인 분석을 위한 연산에 사용됩니다. 이는 위상 정렬, 이중 연결 성분 및 강 연결 성분을 찾는 데에 이용합니다.
위상 정렬(Topological Sort)이란 사이클이 없는 방향 그래프에서 정점들을 선형 순서(즉, 정점들을 일렬)로 나열하는 것입니다. 그래프의 각 정점에 대해 순서를 부여합니다. 일반적으로 작업(Task)들 사이에 의존관계가 존재할 때 수행 가능한 작업 순서를 도식화하는 데에 위상 정렬을 사용합니다.
이중 연결 성분(Biconnected Component)이란 무방향 그래프의 연결 성분에서 임의의 두 정점 사이에 적어도 두 개의 단순 경로가 존재하는 연결 성분을 의미합니다. 따라서 하나의 단순 경로 상의 어느 정점 하나가 삭제되더라도 또 다른 경로가 존재하므로 연결 성분 내에서 정점들 사이의 연결이 유지됩니다. 이중 연결 성분은 통신 네트워크 보안, 전력 공급 네트워크 등에서 네트워크의 견고성(Robustness)을 분석하는 주된 방법입니다.
강 연결 성분(Strongly Connected Component)이란 방향 그래프에서 연결 성분 내의 임의의 두 정점 u와 v에 대해 정점 u에서 v로 가는 경로가 있고 동시에 v에서 u로 돌아오는 경로가 있는 연결 성분을 의미합니다. 소셜 네트워크에서 커뮤니티를 분석하는 데 활용되며, 인터넷의 웹 페이지 분석에도 사용됩니다.
| 응용 | DFS | BFS |
| 신장 트리, 연결 성분, 경로, 사이클 | ○ | ○ |
| 최소 간선을 사용하는 경로 | ○ | |
| 위상 정렬, 이중 연결 성분, 강 연결 성분 | ○ |
※ "자바와 함께하는 자료구조의 이해"라는 책을 참고하여 쓴 게시글입니다. 책에는 없는 내용을 추가하여 작성된 부분이 있습니다. 문제가 되거나 부정확한 부분이 있다면 알려주시면 감사하겠습니다.
※ 책은 게시글보다 정확한 내용을 담고 있으며 코드, 그림, 예제를 이용하여 개념을 자세히 설명합니다.
'Java > 자료구조' 카테고리의 다른 글
| [자료구조] 우선순위 큐(Priority Queue) (0) | 2023.07.06 |
|---|---|
| [자료구조] 이진 힙(Binary Heap) (0) | 2023.07.04 |
| [자료구조] 해시 테이블(Hash Table) (0) | 2023.07.02 |
| [자료구조 트리] 레드 블랙 트리(Red-Black Tree) (0) | 2023.06.30 |
| [자료구조 트리] AVL 트리 (0) | 2023.06.28 |