221112 그래프 구현

Jongleee·2022년 11월 12일

TIL 알고리즘

TIL

목록 보기

103/737

그래프

그래프는 vertex와 edge로 구성된 한정된 자료구조를 의미한다.

vertex : 정점
edge : 정점과 정점을 연결하는 간선

아래는 대표적인 그래프 종류들의 예시다.

이러한 그래프는 인접 행렬, 인접 리스트 방식으로 표현할 수 있다.

1. 인접 행렬

먼저, 행렬로 구현하는 방식을 살펴보자

정점 a와 정점 b를 잇는 간선이 있을 경우, 행렬(a,b)에 1을 표기해준다.
-> 가중치가 있는 그래프라면 1 대신 가중치

기본적으로 무방향 그래프의 경우는 (a,b) (b,a)에 모두 간선 값을 넣지만, 방향 그래프같은 경우는 위의 표와 같이 방향에 맞는 간선만 표기한다.

ex) 정점 1과 3을 잇는 간선이 존재할 때 : graph[1][3] = 1, graph[3][1] = 1

위의 무방향 그래프를 코드로 표현해보자.

public class Main {
    public static void putEdge(int[][] graph, int x, int y) {
        graph[x][y] = 1;
        graph[y][x] = 1;
    }
 
    public static void main(String[] args) {
        int n = 5; //그래프 정점의 개수
        int[][] graph = new int[n+1][n+1]; //index를 1부터 맞추기 위해 n+1
 
        putEdge(graph, 1, 2);
        putEdge(graph, 1, 3);
        putEdge(graph, 1, 4);
        putEdge(graph, 2, 3);
        putEdge(graph, 2, 5);
        putEdge(graph, 3, 4);
        putEdge(graph, 4, 5);
 
    }
}

2. 인접 리스트

이번엔 인접 리스트로 구현하는 방식이다.

해당 노드와 연결되어있는 노드들을 리스트로 쭉 붙이는 방식이다.

ArrayList를 사용하여 코드로 구현해보자.

public class Main {
    public static void putEdge(ArrayList<ArrayList<Integer>> graph, int x, int y) {
        graph.get(x).add(y);
        graph.get(y).add(x);
    }
 
    public static void main(String[] args) {
        int n = 5; //그래프 정점의 개수
        ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
 
        for (int i = 0; i <= n; i++)
            graph.add(new ArrayList<>()); //각 노드 별 리스트를 만들어준다.
        putEdge(graph, 1, 2);
        putEdge(graph, 1, 3);
        putEdge(graph, 1, 4);
        putEdge(graph, 2, 3);
        putEdge(graph, 2, 5);
        putEdge(graph, 3, 4);
        putEdge(graph, 4, 5);
 
    }
}