유향 그래프는 여러 개의 정점(Node)과 간선(Edge)으로 이루어진 자료구조입니다. 각 정점은 다른 정점과 방향 있는 간선으로 연결되어 있습니다. 이번 블로그 포스트에서는 배열을 활용하여 유향 그래프 자료구조를 구현하는 방법에 대해 알아보겠습니다.

그래프 구조 설계

먼저, 그래프 자료구조를 구현하기 위해 필요한 요소를 정의해야 합니다. 여기서는 노드의 개수를 나타내는 n과 그래프의 인접 행렬을 나타내는 graph 배열을 사용할 것입니다. 인접 행렬은 2차원 배열로, graph[i][j] 값이 1이라면 정점 i에서 정점 j로의 간선이 존재함을 의미합니다.

int[][] graph;
int n;

그래프 초기화

다음으로, 생성자를 이용하여 그래프를 초기화하는 방법에 대해 알아보겠습니다. 생성자는 인접 행렬의 크기를 설정하고, 모든 값을 0으로 초기화합니다.

public Graph(int n) {
   this.n = n;
   graph = new int[n][n];
   // 인접 행렬의 모든 값 0으로 초기화
   for (int i = 0; i < n; i++) {
       for (int j = 0; j < n; j++) {
           graph[i][j] = 0;
       }
   }
}

간선 추가하기

다음으로, 유향 그래프에 간선을 추가하는 방법에 대해 알아보겠습니다. addEdge 메소드는 매개변수로 시작 정점과 도착 정점을 받아와서 해당하는 인덱스의 값에 1을 설정하여 간선을 추가합니다.

public void addEdge(int start, int end) {
    graph[start][end] = 1;
}

실행 예제

위에서 구현한 그래프 자료구조를 실제로 사용해보기 위해 간단한 예제를 살펴보겠습니다.

public static void main(String[] args) {
    Graph graph = new Graph(5);
    
    graph.addEdge(0, 1);
    graph.addEdge(1, 2);
    graph.addEdge(2, 3);
    graph.addEdge(3, 4);

    // 인접 행렬 출력
    for (int i = 0; i < graph.n; i++) {
        for (int j = 0; j < graph.n; j++) {
            System.out.print(graph.graph[i][j] + " ");
        }
        System.out.println();
    }
}

위 예제에서는 0부터 4까지의 정점을 가지는 그래프를 생성하고, 각 정점들을 간선으로 연결했습니다. 마지막으로, 인접 행렬을 출력하여 그래프의 구조를 확인할 수 있습니다.

마무리

이번 포스트에서는 배열을 활용한 유향 그래프 자료구조의 구현 방법을 알아보았습니다. 배열을 이용하여 그래프를 표현하면 간단하고 직관적인 구조를 가지게 됩니다. 그래프를 구현하는 다양한 방법 중에서도 배열을 활용하는 방법은 유용하게 사용될 수 있으므로, 그래프를 다루는 프로그램을 개발할 때 참고해보시기 바랍니다.

참조링크

• 유향 그래프 - 위키백과
• 예제 코드 GitHub