[자료구조] 그래프 (Graph) 구현 (JAVA)

그래프를 구현하는 방법은 크개 두 가지가 있다. 인접 행렬을 이용하거나 인접 리스트를 이용하는 방법을 주로 사용한다. 그래프에 대한 자세한 내용은 전 포스팅을 참고하기 바란다.

2024.06.26 - [CS/자료구조] - [자료구조] 그래프 (Graph)

[자료구조] 그래프 (Graph)

 

인접 리스트를 이용한 방법 (JAVA)

---

import java.util.LinkedList;
import java.util.List;

public class Vertex {
    String label;
    List<Vertex> adjVertices;

    Vertex(String label) {
        this.label = label;
        this.adjVertices = new LinkedList<>();
    }

    void addEdge(Vertex v) {
        adjVertices.add(v);
    }

    List<Vertex> getAdjVertices() {
        return adjVertices;
    }

    @Override
    public String toString() {
        return label;
    }
}

Vertex 클래스: 그래프의 기본이 되는 정점을 표현하기 위한 클래스이다.

 

import java.util.HashMap;
import java.util.Map;

class Graph {
    private Map<String, Vertex> vertices;

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

    void addVertex(String label) {
        vertices.putIfAbsent(label, new Vertex(label));
    }

    void addEdge(String label1, String label2) {
        Vertex v1 = vertices.get(label1);
        Vertex v2 = vertices.get(label2);

        if (v1 != null && v2 != null) {
            v1.addEdge(v2);
            v2.addEdge(v1); // 무향 그래프이므로 양쪽에 간선을 추가
        }
    }

    Vertex getVertex(String label) {
        return vertices.get(label);
    }

    void printGraph() {
        for (Vertex v : vertices.values()) {
            System.out.print(v + " -> ");
            for (Vertex adj : v.getAdjVertices()) {
                System.out.print(adj + " ");
            }
            System.out.println();
        }
    }
}

Graph 클래스: 정점과 간선을 추가할 수 있는 메소드와 크래프를 출력하는 메소드 등으로 구성되어 있다.

 

public class Main {
    public static void main(String[] args) {
        Graph graph = new Graph();
        
        // 정점 추가
        graph.addVertex("A");
        graph.addVertex("B");
        graph.addVertex("C");
        graph.addVertex("D");
        graph.addVertex("E");

        // 간선 추가
        graph.addEdge("A", "B");
        graph.addEdge("A", "C");
        graph.addEdge("B", "D");
        graph.addEdge("C", "E");
        graph.addEdge("D", "E");

        // 그래프 출력
        graph.printGraph();
    }
}

Main 클래스: 그래프를 만들고 정점과 간선을 구성하는 메인 함수가 존재한다. 그리고 그래프를 출력한다. 출력 결과는 다음과 같다.

A -> B C 
B -> A D 
C -> A E 
D -> B E 
E -> C D

방향이 없는 무향그래프이기 때문에 두 정점 사이, 양쪽 방향으로 간선이 존재한다.

 

인접 행렬을 이용한 방법 (JAVA)

---

class Graph {
    private boolean[][] adjMatrix;
    private int numVertices;

    // 그래프 초기화
    public Graph(int numVertices) {
        this.numVertices = numVertices;
        adjMatrix = new boolean[numVertices][numVertices];
    }

    // 간선 추가
    public void addEdge(int i, int j) {
        if (i >= 0 && i < numVertices && j >= 0 && j < numVertices) {
            adjMatrix[i][j] = true;
            adjMatrix[j][i] = true; // 무향 그래프이므로 대칭
        }
    }

    // 간선 제거
    public void removeEdge(int i, int j) {
        if (i >= 0 && i < numVertices && j >= 0 && j < numVertices) {
            adjMatrix[i][j] = false;
            adjMatrix[j][i] = false; // 무향 그래프이므로 대칭
        }
    }

    // 인접 행렬 출력
    public void printGraph() {
        for (int i = 0; i < numVertices; i++) {
            for (int j = 0; j < numVertices; j++) {
                System.out.print((adjMatrix[i][j] ? 1 : 0) + " ");
            }
            System.out.println();
        }
    }
}

Graph 클래스: 간선을 추가하고 제거하는 메소드와 행렬을 출력하는 메소드가 있다. 정점을 만드는 메소드가 없는 이유는 행렬은 인덱스가 있기 때문이다. 인덱스가 정점의 역할을 맡는다고 볼 수 있다.

 

public class Main {
    public static void main(String[] args) {
        int numVertices = 5;
        Graph graph = new Graph(numVertices);

        // 간선 추가
        graph.addEdge(0, 1);
        graph.addEdge(0, 2);
        graph.addEdge(1, 3);
        graph.addEdge(2, 4);
        graph.addEdge(3, 4);

        // 그래프 출력
        graph.printGraph();
    }
}

Main 클래스: 그래프를 만들고 그 그래프의 인접 행렬을 출력하는 코드이다. 실행 결과는 다음과 같다.

0 1 1 0 0 
1 0 0 1 0 
1 0 0 0 1 
0 1 0 0 1 
0 0 1 1 0

무향 그래프이기 때문에 대칭으로 행렬이 출력된 것을 확인할 수 있다. 참고로 인접 리스트에서의 그래프와 이 인접 행렬의 그래프는 같은 그래프이다.

 

궁금한 것이나 잘못된 것이 있다면 댓글에 남겨주세요!