그래프는 정점과 간선으로 이루어진 자료 구조입니다. 그래프 탐색 알고리즘은 그래프 내의 모든 정점을 탐색하기 위한 방법을 제공합니다. 이번에는 스택을 이용한 그래프 탐색 알고리즘을 구현해보겠습니다.
스택(Stack) 개념 이해하기
스택은 후입선출(LIFO - Last In, First Out) 원칙에 따라 정점을 저장하는 자료 구조입니다. 정점을 추가(Push)할 때는 스택의 맨 위에 추가하고, 정점을 제거(Pop)할 때는 스택의 맨 위의 정점을 제거합니다. 스택은 배열이나 연결 리스트로 구현할 수 있습니다.
그래프(Graph) 구현하기
먼저, 그래프를 구현하기 위해 정점(Vertex)과 간선(Edge) 클래스를 생성합니다.
class Vertex {
int data;
boolean visited;
public Vertex(int data) {
this.data = data;
this.visited = false;
}
}
class Edge {
Vertex source;
Vertex destination;
public Edge(Vertex source, Vertex destination) {
this.source = source;
this.destination = destination;
}
}
그리고, 그래프 클래스를 생성하여 정점과 간선을 관리합니다.
class Graph {
List<Vertex> vertices;
List<Edge> edges;
public Graph() {
this.vertices = new ArrayList<>();
this.edges = new ArrayList<>();
}
public void addVertex(Vertex vertex) {
vertices.add(vertex);
}
public void addEdge(Vertex source, Vertex destination) {
Edge edge = new Edge(source, destination);
edges.add(edge);
}
}
스택을 이용한 그래프 탐색 알고리즘 구현하기
이제 스택을 이용하여 그래프 탐색 알고리즘을 구현해보겠습니다. 그래프의 깊이 우선 탐색(DFS - Depth First Search) 알고리즘은 스택을 사용하여 구현할 수 있습니다.
public void dfs(Graph graph, Vertex startVertex) {
Stack<Vertex> stack = new Stack<>();
stack.push(startVertex);
while (!stack.isEmpty()) {
Vertex currentVertex = stack.pop();
System.out.print(currentVertex.data + " ");
currentVertex.visited = true;
for (Edge edge : graph.edges) {
if (edge.source == currentVertex && !edge.destination.visited) {
stack.push(edge.destination);
}
}
}
}
위의 코드에서는 스택을 생성하고 시작 정점을 스택에 추가합니다. 스택이 비어있지 않은 동안에는 반복문을 실행하며 스택의 맨 위의 정점을 꺼내고, 해당 정점을 방문한 것으로 표시합니다. 그리고 해당 정점과 연결된 정점 중 방문하지 않은 정점을 스택에 추가합니다.
그래프 탐색 실행하기
실제로 그래프 탐색 알고리즘을 실행해보겠습니다. 아래의 코드에서는 그래프를 생성하고 정점과 간선을 추가한 후, 시작 정점에서 BFS를 실행합니다.
Graph graph = new Graph();
Vertex v1 = new Vertex(1);
Vertex v2 = new Vertex(2);
Vertex v3 = new Vertex(3);
Vertex v4 = new Vertex(4);
Vertex v5 = new Vertex(5);
Vertex v6 = new Vertex(6);
graph.addVertex(v1);
graph.addVertex(v2);
graph.addVertex(v3);
graph.addVertex(v4);
graph.addVertex(v5);
graph.addVertex(v6);
graph.addEdge(v1, v2);
graph.addEdge(v1, v3);
graph.addEdge(v2, v4);
graph.addEdge(v3, v4);
graph.addEdge(v4, v5);
graph.addEdge(v5, v6);
System.out.println("DFS 탐색 결과:");
graph.dfs(graph, v1);
실행 결과는 다음과 같이 출력될 것입니다:
DFS 탐색 결과:
1 3 4 5 6 2
결론
위에서 구현한 스택을 이용한 그래프 탐색 알고리즘은 그래프 내의 모든 정점을 탐색하는데 유용합니다. 스택을 이용하여 깊이 우선 탐색을 구현하는 방법을 익혀두면 그래프 문제를 효율적으로 해결할 수 있습니다.
참고 자료: