Java에서 그래프(Graph)와 탐색 알고리즘 활용하기

그래프(Graph)란?

• 그래프는 노드(정점)들과 이들을 연결하는 간선들로 구성된 자료구조입니다.
• 네트워크, 소셜 미디어, 경로 찾기 등 다양한 분야에서 사용됩니다.

Java에서 그래프 구현

• Java에서는 그래프를 인접 리스트로 구현할 수 있습니다. 여기서는 간단한 그래프 구현을 보여드립니다.

사용자 정의 노드 클래스

class Node {
    int data;
    List<Node> adjacent; // 인접 노드 리스트

    Node(int data) {
        this.data = data;
        adjacent = new ArrayList<>();
    }

    // 인접 노드 추가 메서드
    void addAdjacent(Node node) {
        adjacent.add(node);
    }
}

그래프 클래스

class Graph {
    List<Node> nodes;

    Graph() {
        nodes = new ArrayList<>();
    }

    // 노드 추가 메서드
    void addNode(Node node) {
        nodes.add(node);
    }
}

 

 

그래프 순회 방법

• 그래프를 탐색하는 주요 방법으로 깊이 우선 탐색(DFS)와 너비 우선 탐색(BFS)가 있습니다.

깊이 우선 탐색(DFS)

• DFS는 스택 또는 재귀를 사용해 그래프를 탐색합니다.

DFS 구현 예시

void dfs(Node root) {
    if (root == null) return;
    System.out.print(root.data + " "); // 노드 방문
    root.visited = true; // 방문 표시
    for (Node node : root.adjacent) {
        if (!node.visited) {
            dfs(node); // 재귀 호출
        }
    }
}

 

너비 우선 탐색(BFS)

• BFS는 큐를 사용해 그래프의 각 레벨을 순차적으로 탐색합니다.

BFS 구현 예시

void bfs(Node root) {
    Queue<Node> queue = new LinkedList<>();
    root.visited = true;
    queue.add(root);

    while (!queue.isEmpty()) {
        Node node = queue.poll();
        System.out.print(node.data + " "); // 노드 방문
        for (Node adjacent : node.adjacent) {
            if (!adjacent.visited) {
                adjacent.visited = true;
                queue.add(adjacent);
            }
        }
    }
}

 

 

그래프의 활용

• 그래프는 데이터의 복잡한 관계를 표현하고 분석하는 데 유용합니다.
• 소셜 네트워크, 경로 최적화, 데이터 구조 분석 등 다양한 분야에서 활용됩니다.

결론

• Java에서 그래프를 구현하고 활용하는 것은 복잡한 데이터 구조를 다루고 문제를 해결하는 데 중요한 역할을 합니다.
• 그래프의 이해와 올바른 구현은 Java 프로그래밍의 중요한 측면 중 하나입니다.