이 md 파일은 Typora 에서 작성되었습니다. 읽으실 때, Typora 에서 읽으시는 것이 가장 보기에 좋습니다.
[TOC]
드디어 마지막 그래프입니다. 고생많으셨습니다.
그래프는 경로탐색 알고리즘에 주로 사용됩니다.
그래프의 용어는 정점(vertex)과, 간선(edge)을 맨 처음에 다루네요. 정점은 말 그대로 그래프의 기준이 되는 점, 연결의 대상이 되는 개체 또는 위치고, 간선은 정점 사이에 위치한 선이며 정점 사이의 연결이라고 볼 수도 있습니다.
그래프에는 방향성이라는 개념도 존재합니다. 방향성은 간선에 부여됩니다.
방향성이 없으면 무방향 그래프입니다.
간선에 방향정보가 있는 그래프를 방향 그래프(directed graph), 다이그래프(digraph)라고 합니다.
또 연결 형태에 따라 완전 그래프(complete graph)로 구분이 될 수 있습니다.
완전 그래프의 정의는 '각각의 정점에서 다른 모든 정점을 연결한 그래프'를 뜻하고, 무방향 그래프와 방향 그래프의 정점이 같을 때, 간선의 개수는 방향 그래프가 두 배 더 많습니다.
간선에 가중치라는 정보를 부여해서 그래프를 구성할 수 있습니다. 그리고 이런 가중치가 있는 그래프를 '가중치 그래프'라고 합니다.
가중치는 두 정점 사이의 정보를 표현할 때 사용합니다. 거리, 시간이 될 수도 있지만, 음수인 가중치를 갖는 경우도 있을 수 있습니다.
그리고 '부분 그래프'라고 하는 것이 있는데, 부분 그래프는 원 그래프의 일부 정점 및 간선으로 이뤄진 그래프를 뜻합니다.
그래프는 정점과 간선의 집합이라서 집합의 표기법으로 표현이 가능합니다.
정점 집합과 간선 집합으로 나눌 수 있고, V(G), E(G)와 같은 식으로 표기합니다.
정점은 그냥 집합 표기하듯이 {A, B, C, D} 의 형태로 표기하고
간선은 {(A, B), (A, C), (C, D)} 와 같은 형태로 표기합니다.
무방향 그래프는 간선 (A, B)와 (B, A)는 서로 같은 간선을 표시합니다.
간선은 무방향 그래프와 동일한 형태로 표기합니다.
방향 그래프는 방향성을 고려해서 순서대로 <A, B>와 같은 형태로 표시하고 <B, A>와는 다른 간선을 의미합니다.
오랜만에 ADT를 정의해주네요.
그런데 지금까지 나온 내용을 다 다루는 그래프는 아닌 것으로 보입니다. (다행...)
그래프를 초기화 하는 시점에 정점의 개수를 전달하고, 정점을 연결하는 간선을 추가하는 기능, 간선 정보를 출력하는 기능을 제공하네요.
정점은 Enum을 활용해서 만든다고 합니다.
Graph.java
/**
* 간단한 그래프 자료구조의 인터페이스
*
* @author dion
*/
public interface Graph {
/**
* 매개변수 fromV와 toV로 전달된 정점을 연결하는 간선을 그래프에 추가합니다.
*
* @param fromV 시작하는 정점
* @param toV 도달하는 정점
*/
void addEdge(Enum<?> fromV, Enum<?> toV);
/**
* 그래프의 간선정보를 반환합니다.
*/
String showGraphEdgeInfo();
}그래프는 2차원 배열 또는 연결 리스트로 구현할 수 있습니다.
둘 을 각각 인접 행렬(adjacent matrix) 기반 그래프, 인접 리스트(adjacent list) 기반 그래프 라고 표현합니다.
정방 행렬이라는 용어가 나오는데, 가로 세로의 길이가 같은 행렬을 의미하고, 2차원 배열로 표현합니다.
인접 행렬 기반 그래프는 무방향 그래프는 대각선을 기준으로 대칭성을 보입니다.
인접 리스트는 정점이 자신과 연결된 정점의 정보를 담기위해 연결 리스트를 가지는 형태입니다.
직관적인 이해가 가능한 부분은 2차원 배열이라고 생각됩니다.
그래프 구현 관점에서 무방향 그래프와 방향 그래프의 구현은 차이가 없습니다. 그리고 무방향의 구현이 더 어렵다고 합니다.
GraphTest.java
class GraphTest {
Graph graph;
@BeforeEach
void setUp() {
graph = new ListGraph(5, Point.class);
}
@Test
void 그래프_초기화_테스트() {
assertThat(graph).isNotNull();
}
@Test
void 무방향_그래프_정점_연결_테스트() {
graph.addEdge(Point.A, Point.B);
assertThat(graph.showGraphEdgeInfo()).isEqualTo("A: B\nB: A\n");
graph.addEdge(Point.A, Point.D);
assertThat(graph.showGraphEdgeInfo()).isEqualTo("A: B D\nB: A\nD: A\n");
graph.addEdge(Point.B, Point.C);
assertThat(graph.showGraphEdgeInfo()).isEqualTo("A: B D\nB: A C\nC: B\nD: A\n");
graph.addEdge(Point.C, Point.D);
assertThat(graph.showGraphEdgeInfo()).isEqualTo("A: B D\nB: A C\nC: B D\nD: A C\n");
graph.addEdge(Point.D, Point.E);
assertThat(graph.showGraphEdgeInfo()).isEqualTo("A: B D\nB: A C\nC: B D\nD: A C E\nE: D\n");
graph.addEdge(Point.E, Point.A);
assertThat(graph.showGraphEdgeInfo()).isEqualTo("A: B D E\nB: A C\nC: B D\nD: A C E\nE: D A\n");
}
private enum Point {
A, B, C, D, E, F, G, H, I, J
}
}테스트하기 편하게 하기 위해서 출력하기 보다는 String을 반환하도록 하였습니다.
enum도 그냥 외부에서 사용하는 방식으로 결정했습니다. 조금 어렵겠네요.
ListGrpah.java
public class ListGraph implements Graph {
private final List<Enum<?>>[] vertexes;
public ListGraph(int vertexCount, Class<? extends Enum<?>> clazz) {
Enum<?>[] enumConstants = clazz.getEnumConstants();
int min = Math.min(vertexCount, enumConstants.length);
this.vertexes = new List[min];
for (int i = 0; i < min; i++) {
this.vertexes[i] = new DummyDoublyLinkedList<>();
this.vertexes[i].insert(enumConstants[i]);
}
}
@Override
public void addEdge(Enum<?> fromV, Enum<?> toV) {
}
@Override
public String showGraphEdgeInfo() {
return null;
}
}초기화 코드가 좀 복잡해서 따로 설명합니다.
먼저 우리는 Enum을 인자로 받을겁니다. ? extends Enum<?> 의 의미는 Enum 클래스를 상속하는 클래스를 의미합니다.
그리고 Class<T> 로 Reflection을 사용함을 알 수 있고, 변수명은 관례적으로 clazz 를 사용하였습니다.
enumConstants는 Reflection API를 이용해서 Enum에 선언된 상수를 모두 가져옵니다.
기본적으로 vertexCount만큼 반복하며, 오류를 방지하기 위해 Math.min() 을 사용합니다.
size를 지정해서 새로운 리스트 배열을 생성합니다. 여기엔 null 만 들어있게됩니다.
그리고 반복하며 배열을 채우게 됩니다.
@Override
public void addEdge(Enum<?> fromV, Enum<?> toV) {
vertexes[fromV.ordinal()].insert(toV);
vertexes[toV.ordinal()].insert(fromV);
}
@Override
public String showGraphEdgeInfo() {
StringBuilder sb = new StringBuilder();
for (List<Enum<?>> vertex : vertexes) {
if (vertex.size() > 1) {
for (int i = 0; i < vertex.size(); i++) {
sb.append(vertex.get(i));
if (i == 0) {
sb.append(": ");
} else if (i < vertex.size() - 1) {
sb.append(" ");
}
}
sb.append("\n");
}
}
return sb.toString();
}
}추가하는 로직은 아주 간단하죠? 방향 그래프는 여기서 두번째 줄을 제거하면 됩니다.
ordinal 은 여기서 사용해도 무방합니다. 왜냐하면, 순서대로 배열에 저장되고, 그 순서를 이용하기 때문입니다.
하지만, 되도록이면 ordinal은 안티패턴이니 사용하지 않는게 좋습니다.
그래프 정보를 출력하는 로직은 좀 더럽습니다. 함수로 빼도 되긴하는데, 로직을 보기엔 이 편이 더 좋은 것 같네요.
그래프의 모든 정점을 탐색하는 방법에 대해 다룹니다.
그래프는 이제까지 배워왔던 자료구조들에 비해서 탐색이 어려운 편입니다.
그래프의 모든 정점을 탐색하는 두 가지 방법이 있습니다. 다들 아시는 DFS, BFS입니다.
먼저 DFS입니다. DFS는 일단 한 방향을 정해서 끝까지 도달하고 그 다음을 생각합니다.
너비 우선 탐색은 탐색 가능한 모든 범위로 퍼져나가면서 탐색합니다.
그리고 이미 한 대상이 들른 대상은 다시 탐색하지 않습니다. (순서는 고려하지 않습니다.)
DFS는 스택을 활용합니다. 즉 재귀로도 풀어낼 수 있습니다.
스택에 방문한 정점을 저장하면서 나아가다가 끝에 도달하면 다시 방문한 정점을 찾아다니면서 못찾은 곳이 있는지 찾습니다.
그림 보시면 쉽게 이해가갑니다.
스택에 대해서 깊이 이해할 수 있다고 합니다.
인터페이스에 메서드를 추가해 확장하는 구조로 개발하겠습니다.
Graph.java
/**
* startV를 기점으로 DFS를 수행한 결과를 반환합니다.
*
* @param startV DFS를 시작하는 정점
* @return startV를 기점으로 하는 DFS 결과
*/
String depthFirstSearch(Enum<?> startV);먼저 탐색된 위치를 파악해야합니다. 이것은 간단하게 boolean 배열로 처리할 수 있습니다.
조금 더 객체지향적으로 생각한다면, Node를 만들어서 isVisited라는 상태값을 가지는 것도 고려해볼 수 있을 것 같네요.
@Test
void dfsTest() {
graph.addEdge(Point.A, Point.B);
graph.addEdge(Point.A, Point.C);
graph.addEdge(Point.A, Point.E);
graph.addEdge(Point.B, Point.D);
graph.addEdge(Point.B, Point.E);
graph.addEdge(Point.C, Point.D);
graph.addEdge(Point.D, Point.E);
assertThat(graph.depthFirstSearch(Point.A)).isEqualTo("A E D C B");
assertThat(graph.depthFirstSearch(Point.B)).isEqualTo("B E D C A");
assertThat(graph.depthFirstSearch(Point.C)).isEqualTo("C D E B A");
assertThat(graph.depthFirstSearch(Point.D)).isEqualTo("D E B A C");
assertThat(graph.depthFirstSearch(Point.E)).isEqualTo("E D C A B");
}그림을 그려보면서 하시면 간단할 겁니다.
책에서는 알파벳 순서대로 출력되지만, 스택을 사용하고, 저장된 순서의 역순으로 탐색하므로 저희는 좀 다르게 나옵니다.
정렬 기준에 관계없이 순서대로 저장하기 때문에 순서가 달라지면 결과가 변경됩니다. 이건 규칙이 필요한 경우 SortedList 구현체를 직접 사용하는식으로 하면 될 것 같네요.
책의 구현은 그다지 맘에 드는 방식이 아니고, 구현에 차이도 있어서 코드를 이해하기 쉽게 짜려고 노력했습니다.
@Override
public String depthFirstSearch(Enum<?> startV) {
boolean[] visited = new boolean[vertices.length];
StringJoiner sj = new StringJoiner(" ");
Stack<Enum<?>> vertexStack = new ListStack<>();
vertexStack.push(startV);
while (!vertexStack.isEmpty()) {
Enum<?> visitV = vertexStack.pop();
if (visitVertex(visited, visitV)) {
sj.add(visitV.toString());
}
List<Enum<?>> vertexList = vertices[visitV.ordinal()];
for (int i = 0; i < vertexList.size(); i++) {
Enum<?> vertex = vertexList.get(i);
if (!visited[vertex.ordinal()]) {
vertexStack.push(vertex);
}
}
}
return sj.toString();
}
private boolean visitVertex(boolean[] visited, Enum<?> vertex) {
if (visited[vertex.ordinal()]) {
return false;
}
visited[vertex.ordinal()] = true;
return true;
}너비 우선 탐색은 큐를 활용합니다.
마찬가지로 인터페이스에 메소드 시그니처를 추가합니다.
/**
* startV를 기점으로 BFS를 수행한 결과를 반환합니다.
*
* @param startV BFS를 시작하는 정점
* @return startV를 기점으로 하는 BFS 결과
*/
String breadthFirstSearch(Enum<?> startV);@Test
void bfsTest() {
setVertices();
assertThat(graph.breadthFirstSearch(Point.A)).isEqualTo("A B C E D");
assertThat(graph.breadthFirstSearch(Point.B)).isEqualTo("B A D E C");
assertThat(graph.breadthFirstSearch(Point.C)).isEqualTo("C A D B E");
assertThat(graph.breadthFirstSearch(Point.D)).isEqualTo("D B C E A");
assertThat(graph.breadthFirstSearch(Point.E)).isEqualTo("E A B D C");
}
private void setVertices() {
graph.addEdge(Point.A, Point.B);
graph.addEdge(Point.A, Point.C);
graph.addEdge(Point.A, Point.E);
graph.addEdge(Point.B, Point.D);
graph.addEdge(Point.B, Point.E);
graph.addEdge(Point.C, Point.D);
graph.addEdge(Point.D, Point.E);
}여기서는 큐를 사용하므로 순서대로 나오게됩니다.
직접 구현해보시면 왜 이렇게 나오는지 아시게 될 것 같네요!
책 때문에 더 헷갈렸습니다.
사실 트리는 그래프의 한 유형입니다. 근데 트리를 먼저 배우는 것은 훨씬 이해가 쉽기 때문이죠
두 개의 정점을 잇는 간선을 순서대로 나열한 것을 가리켜 '경로'라 합니다.
그리고 동일한 간선을 중복하여 포함하지 않는 경로를 가리켜 '단순 경로(simple path)'라 합니다.
단순 경로이면서 시작과 끝이 같은 경로를 가리켜 '사이클(cycle)'이라 합니다.
그림을 통해서 이해해봅시다.
사이클을 형성하지 않는 그래프는 트리입니다. 정확히 말해 '신장 트리(spanning tree)'라고 합니다.
신장 트리의 특징 두 가지
- 그래프의 모든 정점이 간선에 의해서 하나로 연결되어 있다.
- 그래프 내에서 사이클을 형성하지 않는다.
신장 트리의 모든 간선의 가중치 합이 최소인 그래프가 '최소 비용 신장 트리(minimum cost spanning tree)'또는 '최소 신장 트리'라 합니다.
- 도로 건설
- 전기회로 구성
- 네트워크 구축
최소 비용 신장 트리의 구성에 사용되는 대표적인 알고리즘 두 가지
- 크루스칼(Kruskal) 알고리즘 가중치를 기준으로 간선을 정렬한 후에 MST가 될 때까지 간선을 하나씩 선택 또는 삭제해나가는 방식
- 프림(Prim) 알고리즘 하나의 정점을 시작으로 MST가 될 때까지 트리를 확장해나가는 방식
MST는 간선의 수 + 1 = 정점의 수라는 특성을 가집니다.
크루스칼 알고리즘의 핵심
- 가중치를 기준으로 간선을 오름차순으로 정렬한다.
- 낮은 가중치의 간선부터 시작해서 하나씩 그래프에 추가한다.
- 사이클을 형성하는 간선은 추가하지 않는다.
- 간선의 수가 정점의 수보다 하나 적을 때 MST가 완성된다.
전과는 반대로 내림차순으로 정렬해 하나씩 빼는 방식으로도 진행할 수 있습니다.
다만 간선이 사라지면 정점간의 연결이 끊기는 경우 제거하지 않는 식으로 구성합니다.
- 가중치를 기준으로 간선을 내림차순으로 정렬한다.
- 높은 가중치의 간선부터 시작해서 하나씩 그래프에서 제거한다.
- 두 정점을 연결하는 다른 경로가 없을 경우 해당 간선은 제거하지 않는다.
- 간선의 수가 정점의 수보다 하나 적을 때 MST는 완성된다.
책에서는 2번 방법으로 구현한다고 합니다.
기존에 만들었던 그래프는 가중치를 가지지 않는 그래프이므로 가중치를 가지는 것도 고려해야합니다.
가중치 그래프를 표현할 인터페이스를 선언합니다.
가중치 정보는 클래스의 내부 클래스로 선언해서 은닉하고자 합니다.
WeightedGraph.java
/**
* 가중치 그래프의 인터페이스
*
* @author dion
*/
public interface WeightedGraph extends Graph {
/**
* 매개변수 fromV와 toV로 전달된 정점을 연결하는 간선에 가중치를 부여하여 그래프에 추가합니다.
*
* @param fromV 시작하는 정점
* @param toV 도달하는 정점
* @param weight 간선의 가중치
*/
void addEdge(Enum<?> fromV, Enum<?> toV, int weight);
/**
* 그래프의 간선정보 및 가중치를 반환합니다.
*
* @return 그래프의 간선정보 및 가중치
*/
String showGraphEdgeWeightInfo();
/**
* 크루스칼 알고리즘을 이용해 최소신장 트리로 변환합니다.
*/
void convertToMST();
}WeightedGraphTest.java
class WeightedGraphTest {
WeightedGraph graph;
@BeforeEach
void setUp() {
this.graph = new ListWeightGraph(6, Point.class);
}
@Test
void 가중치_그래프_초기화_테스트() {
assertThat(this.graph).isNotNull();
}
@Test
void 가중치_없이_생성하면_UnsupportedOperationException_발생_테스트() {
assertThatThrownBy(() -> graph.addEdge(Point.A, Point.B))
.isInstanceOf(UnsupportedOperationException.class);
}
@Test
void 가중치_그래프_정점_연결_테스트() {
graph.addEdge(Point.A, Point.B, 9);
assertThat(graph.showGraphEdgeInfo()).isEqualTo("A: B\nB: A\n");
assertThat(graph.showGraphEdgeWeightInfo()).isEqualTo("(A-B), w: 9\n");
graph.addEdge(Point.B, Point.C, 2);
assertThat(graph.showGraphEdgeInfo()).isEqualTo("A: B\nB: A C\nC: B\n");
assertThat(graph.showGraphEdgeWeightInfo()).isEqualTo("(A-B), w: 9\n(B-C), w: 2\n");
graph.addEdge(Point.A, Point.C, 12);
assertThat(graph.showGraphEdgeInfo()).isEqualTo("A: B C\nB: A C\nC: B A\n");
assertThat(graph.showGraphEdgeWeightInfo())
.isEqualTo("(A-C), w: 12\n(A-B), w: 9\n(B-C), w: 2\n");
graph.addEdge(Point.A, Point.D, 8);
assertThat(graph.showGraphEdgeInfo()).isEqualTo("A: B C D\nB: A C\nC: B A\nD: A\n");
assertThat(graph.showGraphEdgeWeightInfo())
.isEqualTo("(A-C), w: 12\n(A-B), w: 9\n(A-D), w: 8\n(B-C), w: 2\n");
graph.addEdge(Point.D, Point.C, 6);
assertThat(graph.showGraphEdgeInfo()).isEqualTo("A: B C D\nB: A C\nC: B A D\nD: A C\n");
assertThat(graph.showGraphEdgeWeightInfo())
.isEqualTo("(A-C), w: 12\n(A-B), w: 9\n(A-D), w: 8\n(D-C), w: 6\n(B-C), w: 2\n");
graph.addEdge(Point.A, Point.F, 11);
assertThat(graph.showGraphEdgeInfo()).isEqualTo("A: B C D F\nB: A C\nC: B A D\nD: A C\nF: A\n");
assertThat(graph.showGraphEdgeWeightInfo()).isEqualTo(
"(A-C), w: 12\n(A-F), w: 11\n(A-B), w: 9\n(A-D), w: 8\n(D-C), w: 6\n(B-C), w: 2\n");
graph.addEdge(Point.F, Point.D, 4);
assertThat(graph.showGraphEdgeInfo())
.isEqualTo("A: B C D F\nB: A C\nC: B A D\nD: A C F\nF: A D\n");
assertThat(graph.showGraphEdgeWeightInfo()).isEqualTo(
"(A-C), w: 12\n(A-F), w: 11\n(A-B), w: 9\n(A-D), w: 8\n(D-C), w: 6\n(F-D), w: 4\n(B-C), w: 2\n");
graph.addEdge(Point.D, Point.E, 3);
assertThat(graph.showGraphEdgeInfo())
.isEqualTo("A: B C D F\nB: A C\nC: B A D\nD: A C F E\nE: D\nF: A D\n");
assertThat(graph.showGraphEdgeWeightInfo()).isEqualTo(
"(A-C), w: 12\n(A-F), w: 11\n(A-B), w: 9\n(A-D), w: 8\n(D-C), w: 6\n(F-D), w: 4\n(D-E), w: 3\n(B-C), w: 2\n");
graph.addEdge(Point.E, Point.C, 7);
assertThat(graph.showGraphEdgeInfo())
.isEqualTo("A: B C D F\nB: A C\nC: B A D E\nD: A C F E\nE: D C\nF: A D\n");
assertThat(graph.showGraphEdgeWeightInfo()).isEqualTo(
"(A-C), w: 12\n(A-F), w: 11\n(A-B), w: 9\n(A-D), w: 8\n(E-C), w: 7\n(D-C), w: 6\n(F-D), w: 4\n(D-E), w: 3\n(B-C), w: 2\n");
graph.addEdge(Point.F, Point.E, 13);
assertThat(graph.showGraphEdgeInfo())
.isEqualTo("A: B C D F\nB: A C\nC: B A D E\nD: A C F E\nE: D C F\nF: A D E\n");
assertThat(graph.showGraphEdgeWeightInfo()).isEqualTo(
"(F-E), w: 13\n(A-C), w: 12\n(A-F), w: 11\n(A-B), w: 9\n(A-D), w: 8\n(E-C), w: 7\n(D-C), w: 6\n(F-D), w: 4\n(D-E), w: 3\n(B-C), w: 2\n");
}
@Test
void 가중치_그래프_MST변환_테스트() {
graph.addEdge(Point.A, Point.B, 9);
graph.addEdge(Point.B, Point.C, 2);
graph.addEdge(Point.A, Point.C, 12);
graph.addEdge(Point.A, Point.D, 8);
graph.addEdge(Point.D, Point.C, 6);
graph.addEdge(Point.A, Point.F, 11);
graph.addEdge(Point.F, Point.D, 4);
graph.addEdge(Point.D, Point.E, 3);
graph.addEdge(Point.E, Point.C, 7);
graph.addEdge(Point.F, Point.E, 13);
graph.convertToMST();
assertThat(graph.showGraphEdgeInfo()).isEqualTo("A: D\nB: C\nC: B D\nD: C F E A\nE: D\nF: D\n");
assertThat(graph.showGraphEdgeWeightInfo())
.isEqualTo("(A-D), w: 8\n(D-C), w: 6\n(F-D), w: 4\n(D-E), w: 3\n(B-C), w: 2\n");
}
private enum Point {
A, B, C, D, E, F, G, H, I, J
}
}ListWeightGraph.java
public class ListWeightGraph implements WeightedGraph {
public ListWeightGraph(int vertexCount, Class<? extends Enum<?>> clazz) {
}
@Override
public void addEdge(Enum<?> fromV, Enum<?> toV, int weight) {
}
@Override
public String showGraphEdgeWeightInfo() {
return null;
}
@Override
public void convertToMST() {
}
@Override
public void addEdge(Enum<?> fromV, Enum<?> toV) {
throw new UnsupportedOperationException("이 메소드는 지원하지 않습니다.");
}
@Override
public String showGraphEdgeInfo() {
return null;
}
@Override
public String depthFirstSearch(Enum<?> startV) {
return null;
}
@Override
public String breadthFirstSearch(Enum<?> startV) {
return null;
}
private static class WeightEdge {
public WeightEdge(int weight, Enum<?> fromVertex, Enum<?> toVertex) {
this.weight = weight;
this.fromVertex = fromVertex;
this.toVertex = toVertex;
}
private final int weight;
private final Enum<?> fromVertex;
private final Enum<?> toVertex;
}
}일단 클래스의 구조를 간단히 파악해봅시다.
초기화 부분
private final List<Enum<?>>[] vertices;
private final PriorityQueue<WeightEdge> edgePriorityQueue;
public ListWeightGraph(int vertexCount, Class<? extends Enum<?>> clazz) {
edgePriorityQueue = new HeapPriorityQueue<>(Comparator.comparingInt(o -> o.weight));
Enum<?>[] enumConstants = clazz.getEnumConstants();
int min = Math.min(vertexCount, enumConstants.length);
this.vertices = new List[min];
for (int i = 0; i < min; i++) {
this.vertices[i] = new DummyDoublyLinkedList<>();
this.vertices[i].insert(enumConstants[i]);
}
}기존과 달라진 부분은 우선순위 큐가 들어간 부분입니다. 가중치에 따라 우선순위를 매깁니다. (내림차순)
간선 추가 부분
@Override
public void addEdge(Enum<?> fromV, Enum<?> toV, int weight) {
WeightEdge edge = new WeightEdge(weight, fromV, toV);
vertices[fromV.ordinal()].insert(toV);
vertices[toV.ordinal()].insert(fromV);
edgePriorityQueue.enqueue(edge);
}간선만들고 priorityqueue에 추가하는 부분만 추가되었습니다.
기존과 달라지지 않는 부분
@Override
public String showGraphEdgeInfo() {
StringBuilder sb = new StringBuilder();
for (List<Enum<?>> vertex : vertices) {
if (vertex.size() > 1) {
for (int i = 0; i < vertex.size(); i++) {
sb.append(vertex.get(i));
if (i == 0) {
sb.append(": ");
} else if (i < vertex.size() - 1) {
sb.append(" ");
}
}
sb.append("\n");
}
}
return sb.toString();
}
@Override
public String depthFirstSearch(Enum<?> startV) {
boolean[] visited = new boolean[vertices.length];
StringJoiner sj = new StringJoiner(" ");
Stack<Enum<?>> vertexStack = new ListStack<>();
vertexStack.push(startV);
while (!vertexStack.isEmpty()) {
Enum<?> visitV = vertexStack.pop();
if (visitVertex(visited, visitV)) {
sj.add(visitV.toString());
}
List<Enum<?>> vertexList = vertices[visitV.ordinal()];
for (int i = 0; i < vertexList.size(); i++) {
Enum<?> vertex = vertexList.get(i);
if (!visited[vertex.ordinal()]) {
vertexStack.push(vertex);
}
}
}
return sj.toString();
}
@Override
public String breadthFirstSearch(Enum<?> startV) {
boolean[] visited = new boolean[vertices.length];
StringJoiner sj = new StringJoiner(" ");
Queue<Enum<?>> vertexQueue = new LinkedListQueue<>();
vertexQueue.enqueue(startV);
while (!vertexQueue.isEmpty()) {
Enum<?> visitV = vertexQueue.dequeue();
if (visitVertex(visited, visitV)) {
sj.add(visitV.toString());
}
List<Enum<?>> vertexList = vertices[visitV.ordinal()];
for (int i = 0; i < vertexList.size(); i++) {
Enum<?> vertex = vertexList.get(i);
if (!visited[vertex.ordinal()]) {
vertexQueue.enqueue(vertex);
}
}
}
return sj.toString();
}
private boolean visitVertex(boolean[] visited, Enum<?> vertex) {
if (visited[vertex.ordinal()]) {
return false;
}
visited[vertex.ordinal()] = true;
return true;
}@Override
public void convertToMST() {
int vertexCount = this.vertices.length;
int edgeCount = this.edgePriorityQueue.size() + 1;
List<WeightEdge> edges = new DummyDoublyLinkedList<>();
// MST가 될 때까지 while문을 반복
while (edgeCount != vertexCount) {
WeightEdge edge = this.edgePriorityQueue.dequeue();
removeEdge(edge.fromVertex, edge.toVertex); // 그래프에서 제거해본다.
edgeCount--;
if (!isConnectedWith(edge.fromVertex, edge.toVertex)) { // 연결되어 있지 않으면 복구
recoverEdge(edge);
edges.insert(edge);
edgeCount++;
}
}
// 간선 정보 복원
for (int i = 0; i < edges.size(); i++) {
this.edgePriorityQueue.enqueue(edges.get(i));
}
}
private boolean isConnectedWith(Enum<?> fromVertex, Enum<?> toVertex) {
boolean[] visited = new boolean[vertices.length];
Stack<Enum<?>> vertexStack = new ListStack<>();
vertexStack.push(fromVertex);
while (!vertexStack.isEmpty()) {
Enum<?> visitV = vertexStack.pop();
if (visitVertex(visited, visitV)) {
if (visitV.equals(toVertex)) {
return true;
}
}
List<Enum<?>> vertexList = vertices[visitV.ordinal()];
for (int i = 0; i < vertexList.size(); i++) {
Enum<?> vertex = vertexList.get(i);
if (!visited[vertex.ordinal()]) {
vertexStack.push(vertex);
}
}
}
return false;
}
private void recoverEdge(WeightEdge edge) {
vertices[edge.fromVertex.ordinal()].insert(edge.toVertex);
vertices[edge.toVertex.ordinal()].insert(edge.fromVertex);
}
private void removeEdge(Enum<?> fromVertex, Enum<?> toVertex) {
removeVertexFromLink(fromVertex, toVertex);
removeVertexFromLink(toVertex, fromVertex);
}
private void removeVertexFromLink(Enum<?> vertexA, Enum<?> vertexB) {
List<Enum<?>> vertexLinkInfo = this.vertices[vertexA.ordinal()];
for (int i = 0; i < vertexLinkInfo.size(); i++) {
if (vertexLinkInfo.get(i).equals(vertexB)) {
vertexLinkInfo.remove(i);
return;
}
}
throw new IllegalArgumentException("해당 정점들은 연결되어있지 않습니다.");
}자세한 설명은 책을 참고하시면서 보시면 될 것 같습니다.
연결되어있는지 확인은 DFS를 사용해서 연결상태를 파악합니다.
recoverEdge는 우선순위 큐에는 따로 추가하지 않고, 정점간의 연결 정보만 추가합니다. 왜냐하면 다시 넣으면 그 값이 다음번에 다시 쓰이기 때문입니다.
remove는 연결되어 있다면 연결을 끊는 역할입니다.
이상으로 구현을 마치겠습니다.
모두 코로나 때문에 고생많으셨고, 좀 더 열심히 준비해야함을 느꼈습니다. 고생하셨습니다!!