🔖그래프: 정점(vertex)들의 집합 V와 이들을 연결 하는 간선(edge)들의 집합 E로 구성된 자료구조를 말하며, $G = (V, E)$로 표현한다.

📢여기서 잠깐! 그래프의 종류를 학습하기 전에, 이전 시간에 배운 트리와 그래프의 차이점을 알아보자.

트리도 그래프와 마찬가지로 정점(Node)와 간선(Edge)가 있지만, 깊이(depth)가 있어 계층 구조를 가진다는 점에서 그래프와 차이가 있다.
base condition의 역할: 트리는 구조적으로 사이클이 없기 때문에 if (root == null) return null;과 같은 체크만으로 충분하지만, 그래프는 보통 무향 그래프(undirected graph)로 주어져 사이클이 존재할 수 있기 때문에 방문 여부 확인이 base condition의 역할을 한다.

그래프의 종류

🔖방향 그래프(Directed graph): 들어오는 edge와 나가는 edge가 따로 정해져있는 그래프를 의미함

🔖indegree: 하나의 정점에 들어오는 edge
🔖outdegree: 하나의 정점에서 나가는 edge

🔖무향 그래프(Undirected graph): 방향이 안 정해져 있어 두 정점 간에 edge로 연결이 되어있으면 V -> W 또는 W -> V로 갈 수 있는 그래프를 의미함

🔖simple graph: 두 정점간에 edge가 1개로만 이루어져 있는 그래프
🔖다중그래프: 인접해있는 두 정점 사이에 outdegree와 indegree가 2개 이상인 그래프

📢코테에서는 Undirected graph와 simple graph를 주로 다룸!

🔖가중치 그래프: 각 경로(edge)마다 가중치(비용 또는 시간)가 다른 그래프

📢가중치 그래프는 다익스트라 알고리즘에서 주로 쓰이기 때문에 추후 심화편에서 다룰 예정임

그래프의 구현

그래프를 구현하는 방법으로는 인접 행렬, 인접 리스트, 그리고 암시적 그래프로 총 3가지가 있다.

인접 행렬

row와 column에 따라, 즉 2차원 배열로 그래프를 구현한 것을 말한다.

위와 같은 그래프를 행렬로 나타내면 다음과 같다👇

• 인접 행렬의 특징은 대각 성분을 기준으로 대칭성을 갖고 있다는 것이다.(∵undirected graph)
  • 자기 자신을 연결하는 edge는 존재하지 않아서 대각 성분은 모두 0이다.
• 각 정점들을 row와 column으로 나타낼 수 있고, edge로 연결되어 있으면 1, 그렇지 않으면 0으로 표현할 수 있다.

🚩그런데, 인접 행렬은 위와 같이 정점은 많은데 간선의 개수가 적을 때는 0의 값까지 메모리에 저장해야 하기 때문에 비효율적이다.

🔨따라서 인접 리스트로 위의 문제를 해결할 수 있다.

인접 리스트

해시맵의 형태로 정의되고, Key는 정점들이 들어가고, Value에는 list 형태로 연결 관계를 표시해준다.

위의 그래프를 인접 리스트로 표현하면 다음과 같다.

public class GraphSort {
    public static void main(String[] args) {
        HashMap<String, List<String>> graph = new HashMap<>();
        graph.put("A", List.of("B"));
        graph.put("B", List.of("A", "C", "E"));
        graph.put("C", List.of("B", "D"));
        graph.put("D", List.of("C", "E", "F"));
        graph.put("E", List.of("B", "D", "F"));
        graph.put("F", List.of("D", "E"));

        System.out.println(graph);
    }
}

• 💡자바9 이상부터 사용되는 List.of()는 하나 이상의 원소를 포함하는 불변 리스트 객체를 리턴한다.
  • 얘는 ImmutableCollections 클래스의 인스턴스를 주입해서 사용하기 때문에 불변 객체를 리턴함

암시적 그래프

보통, 미로 문제가 나오면 다음과 같이 그래프를 암시적으로 표현할 수 있다.

검은색이 벽이고 흰 색이 길인데, 벽을 1로 길을 0으로 표현함으로써 구분할 수가 있다.

뿐만 아니라, 각 영역에 좌표 개념을 도입하여 row와 col로 인접 행렬과 비슷하게 표현할 수도 있다.

public class GraphSort {
    public static void main(String[] args) {
        int[][] maze = {
                {1, 1, 1, 1, 1},
                {0, 0, 0, 1, 1},
                {1, 1, 0, 1, 1},
                {1, 0, 0, 0, 0},
                {1, 1, 1, 1, 1}
        };
        
        System.out.println(maze[2][1]);
    }
}

만약, (2, 1)에 접근하고 싶으면, maze[2][1]를 통해 값을 알아낼 수 있다.