Java 그래프 자료구조 마스터하기 - 초보자를 위한 가이드

소개

이 튜토리얼에서는 Java 에서 그래프 데이터 구조를 생성하고 조작하는 방법을 배우게 됩니다. 그래프는 객체 간의 관계를 나타내는 데 사용되는 기본적인 데이터 구조입니다. 다양한 유형의 그래프, 그래프를 표현하는 방법, 정점 (vertex) 과 간선 (edge) 을 추가 및 제거하는 것과 같은 일반적인 연산, 너비 우선 탐색 (breadth-first search), 깊이 우선 탐색 (depth-first search) 등을 구현하는 방법을 살펴보겠습니다.

노드 클래스 생성

먼저, 그래프의 정점 (vertex) 을 나타내는 Node 클래스를 생성합니다. 각 노드는 이름과 값 또는 가중치와 같은 다른 정보를 가질 수 있습니다.

public class Node {
    private String name;

    public Node(String name) {
        this.name = name;
    }

    public String getName() {
        return name;
    }
}

그래프 클래스 생성

다음으로, 그래프 자체를 나타내는 Graph 클래스를 생성합니다. 인접 리스트 (adjacency list) 를 사용하여 간선 (edge) 과 해당 끝점을 저장합니다.

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Graph {
    private Map<Node, List<Node>> adjacencyList;

    public Graph() {
        this.adjacencyList = new HashMap<>();
    }

    public void addNode(Node node) {
        adjacencyList.putIfAbsent(node, new ArrayList<>());
    }

    public void addEdge(Node node1, Node node2) {
        adjacencyList.get(node1).add(node2);
        adjacencyList.get(node2).add(node1);
    }

    public void removeNode(Node node) {
        adjacencyList.values().stream().forEach(e -> e.remove(node));
        adjacencyList.remove(node);
    }

    public void removeEdge(Node node1, Node node2) {
        List<Node> list1 = adjacencyList.get(node1);
        List<Node> list2 = adjacencyList.get(node2);
        if (list1 != null) {
            list1.remove(node2);
        }
        if (list2 != null) {
            list2.remove(node1);
        }
    }

    public List<Node> getNeighbors(Node node) {
        return adjacencyList.get(node);
    }
}

그래프 생성

이제 그래프를 생성하고 몇 개의 노드와 간선을 추가해 보겠습니다.

Graph graph = new Graph();
Node nodeA = new Node("A");
Node nodeB = new Node("B");
Node nodeC = new Node("C");
Node nodeD = new Node("D");

graph.addNode(nodeA);
graph.addNode(nodeB);
graph.addNode(nodeC);
graph.addNode(nodeD);

graph.addEdge(nodeA, nodeB);
graph.addEdge(nodeB, nodeC);
graph.addEdge(nodeC, nodeD);
graph.addEdge(nodeD, nodeA);

너비 우선 탐색 (BFS) 구현

이제 그래프의 노드를 너비 우선 순서로 순회하기 위해 너비 우선 탐색 알고리즘을 구현합니다.

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

public class BreadthFirstSearch {
    public List<Node> bfs(Graph graph, Node start) {
        List<Node> visited = new ArrayList<>();
        Deque<Node> queue = new ArrayDeque<>();
        visited.add(start);
        queue.add(start);

        while (!queue.isEmpty()) {
            Node node = queue.poll();
            List<Node> neighbors = graph.getNeighbors(node);
            for (Node neighbor : neighbors) {
                if (!visited.contains(neighbor)) {
                    visited.add(neighbor);
                    queue.add(neighbor);
                }
            }
        }

        return visited;
    }
}

실행 방법 예시:

javac Graph.java BreadthFirstSearch.java Node.java && java BreadthFirstSearch

깊이 우선 탐색 (DFS) 구현

이제 그래프의 노드를 깊이 우선 순서로 순회하기 위해 깊이 우선 탐색 알고리즘을 구현합니다.

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class DepthFirstSearch {
    public List<Node> dfs(Graph graph, Node start) {
        List<Node> visited = new ArrayList<>();
        dfsHelper(graph, start, visited, new HashSet<>());
        return visited;
    }

    private void dfsHelper(Graph graph, Node current, List<Node> visited, Set<Node> seen) {
        visited.add(current);
        seen.add(current);
        for (Node neighbor : graph.getNeighbors(current)) {
            if (!seen.contains(neighbor)) {
                dfsHelper(graph, neighbor, visited, seen);
            }
        }
    }
}

실행 방법 예시:

javac Graph.java DepthFirstSearch.java Node.java && java DepthFirstSearch

노드 삭제 방법 (삭제 알고리즘)

그래프에서 노드를 제거하고 해당 노드에 연결된 모든 엣지 (edge) 도 제거할 수 있습니다.

Graph graph = new Graph();
Node nodeA = new Node("A");
Node nodeB = new Node("B");
Node nodeC = new Node("C");
Node nodeD = new Node("D");

graph.addNode(nodeA);
graph.addNode(nodeB);
graph.addNode(nodeC);
graph.addNode(nodeD);

graph.addEdge(nodeA, nodeB);
graph.addEdge(nodeB, nodeC);
graph.addEdge(nodeC, nodeD);
graph.addEdge(nodeD, nodeA);

graph.removeNode(nodeC);

간선 삭제 (그래프 간선 제거) 방법

그래프에서 두 노드 사이의 엣지 (edge) 를 제거할 수 있습니다.

Graph graph = new Graph();
Node nodeA = new Node("A");
Node nodeB = new Node("B");

graph.addNode(nodeA);
graph.addNode(nodeB);

graph.addEdge(nodeA, nodeB);
graph.addEdge(nodeB, nodeC);

graph.removeEdge(nodeA, nodeB);

요약

이 튜토리얼에서는 노드 (node) 와 인접 리스트 (adjacency list) 표현을 사용하여 Java 에서 그래프 데이터 구조를 만드는 방법을 배웠습니다. 또한 노드와 엣지 (edge) 를 추가하고 제거하는 것을 포함하여 그래프를 조작하는 연산을 구현했습니다. 마지막으로, 너비 우선 탐색 (breadth-first search) 과 깊이 우선 탐색 (depth-first search) 의 두 가지 검색 알고리즘을 구현했습니다.

Java 를 이용한 그래프 자료구조

소개