그래프를 구현하는 3가지 방법 : 에지 리스트 / 인접 행렬 / 인접 리스트

그래프란?

노드와 에지로 구성된 집합

* 노드 : 데이터를 표현하는 단위

* 에지 : 노드를 연결

 

 

그래프를 구현하는 3가지 방법에 대해 알아보자.

---

에지 리스트

에지 리스트는 에지를 중심으로 그래프를 표현함

 

 

1. 가중치가 없는 에지 리스트

: 출발 노드와 도착 노드만 표현하면 되므로 배열의 행은 2개면 충분함

 

-> 1에서 2로 뻗어나가는 에지는 [1, 2]로 표현

-> 방향이 있는 그래프는 순서에 맞게 노드를 배열에 저장하는 방식으로 표현

-> 만약 방향이 없다면 [1, 2]와 [2, 1]은 같은 표현

 

 

2. 가중치가 있는 에지 리스트

: 가중치를 저장하는 행을 추가하여 총 배열의 행이 3개 필요

 

-> 1에서 2로 향하는 가중치가 8이므로 [1, 2, 8]로 표현

-> 구현하기가 쉬우나 특정 노드와 관련되어 있는 에지를 탐색하기는 어려움

 

 

 

=> 에지 리스트는 벨만 포드나 크루스칼 알고리즘에 사용하며, 노드 중심 알고리즘에는 잘 사용하지 않음

---

인접 행렬

2차원 배열을 자료구조로 이용해 그래프를 표현

에지 리스트와 다르게 노드 중심으로 그래프 표현함

 

 

1. 가중치 없는 그래프 표현

 

-> 1에서 2를 향하는 에지를 1행 2열에 1을 저장하는 방식으로 표현

 

 

2. 가중치 있는 그래프 표현

 

 

-> 기존에 1을 저장하는 대신 가중치를 저장해 표현

 

 

=> 노드와 관련된 에지를 탐색하려면 N번 접근해야 하므로 노드 개수에 비해 에지가 적을 때는 공간 효율성이 떨어짐

=> 만약 2에서 출발하는 에지를 찾으려면 A[2]에 접근한 후, N번 탐색해야 함

=> 노드 개수가 많은 경우 2차원 배열 선언 자체가 어려움(노드가 3만 개가 넘으면 힙 스페이스 에러 발생)

---

인접 리스트(제일 중요!)

노드 개수만큼 ArrayList를 선언해 그래프 표현

 

 

1. 가중치 없는 그래프 표현

 

-> 노드 1과 연결된 2, 3 노드는 ArrayList[1]에 [2, 3]을 연결하는 방식으로 표현

 

 

2. 가중치 있는 그래프 표현

 

-> 자료형을 클래스로 사용

-> (도착 노드, 가중치)를 갖는 Node 클래스를 선언해 ArrayList에 사용

-> 구현이 복잡하지만, 노드와 연결된 에지를 탐색하는 시간이 매우 뛰어남

-> 노드 개수가 커도 공간 효율이 좋아 메모리 초과 에러도 발생하지 않음

---

백준 온라인저지 18352번

import java.util.*;

public class P18352_특정거리의도시찾기 {

    static int[] visited;
    static ArrayList<Integer>[] arr;

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt(); // 도시 개수(노드)
        int M = sc.nextInt(); // 도로 개수(에지)
        int K = sc.nextInt(); // 거리 정보(에지 정보)
        int X = sc.nextInt(); // 출발 도시 번호

        // 그래프를 표현할 인접리스트 초기화
        arr = new ArrayList[N+1];
        for(int i=0; i<N+1; i++) {
            arr[i] = new ArrayList<Integer>();
        }

        // 방문 배열 초기화 : -1로
        visited = new int[N+1];
        for(int i=0; i<N+1; i++) {
            visited[i] = -1;
        }

        // 거리 정보 입력 받기
        for(int i=0; i<M; i++) {
            int s = sc.nextInt();
            int e = sc.nextInt();
            arr[s].add(e);
        }

        BFS(X);

        ArrayList<Integer> answer = new ArrayList<>();
        for(int i=1; i<=N; i++) {
            if(visited[i] == K) {
                answer.add(i);
            }
        }

        Collections.sort(answer);

        if(answer.size() < 1) {
            System.out.println(-1);
        } else {
            for(int tmp : answer) {
                System.out.println(tmp);
            }
        }
    }


    private static void BFS(int node) {
        Queue<Integer> q = new LinkedList<>();

        q.add(node);
        visited[node]++;

        while(!q.isEmpty()) {
            int newNode = q.poll();

            for(int i=0; i<arr[newNode].size(); i++) {
                if(visited[arr[newNode].get(i)] == -1) {
                    visited[arr[newNode].get(i)] = visited[newNode] + 1;
                    q.add(arr[newNode].get(i));
                }
            }
        }
    }
}

---

 

 

* 이분 그래프란?

각 집합에 속한 노드끼리 서로 인접하지 않는 두 집합으로 그래프의 노드를 나눌 수 있을 때

 

-> 트리는 항상 이분 그래프가 됨 : 사이클이 발생하지 않으면 다음 노드를 이번 노드와 다른 집합으로 지정하면 되기 때문

-> 사이클이 발생했을 때는 이분 그래프가 불가능할 경우가 존재함

이분 그래프 X

 

이분 그래프 판별법

기존 탐색 메커니즘에서 탐색한 노드에 다시 접근하게 됐을 때 현재 노드의 집합과 같으면 이분 그래프가 불가능한 것으로 판별

 

 

백준 온라인저지 1707번

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.sql.Array;
import java.util.ArrayList;

public class P1707_이분그래프 {

    static ArrayList<Integer>[] arr;
    static int[] check;
    static boolean visited[];
    static boolean isEven; // 이분 그래프 여부

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int testCase = Integer.parseInt(br.readLine());

        for(int i=0; i<testCase; i++) {
            String[] s = br.readLine().split(" ");
            int V = Integer.parseInt(s[0]); // 노드 수
            int E = Integer.parseInt(s[1]); // 에지 수

            // 인접리스트 초기화
            arr = new ArrayList[V+1];
            for(int v=0; v<V+1; v++) {
                arr[v] = new ArrayList<Integer>();
            }

            visited = new boolean[V+1];
            check = new int[V+1];
            isEven = true;

            // 에지 데이터 저장
            for(int j=0; j<E; j++) {
                s = br.readLine().split(" ");
                int start = Integer.parseInt(s[0]);
                int end = Integer.parseInt(s[1]);

                arr[start].add(end);
                arr[end].add(start);
            }

            // 모든 노드에서 탐색 수행
            for(int k=1; k<=V; k++) {
                if(isEven) {
                    DFS(k);
                } else {
                    break;
                }
            }

            if(isEven) {
                System.out.println("YES");
            } else {
                System.out.println("NO");
            }
        }
    }
    private static void DFS(int node) {
        visited[node] = true;

        for(int i : arr[node]) {
            if(!visited[i]) {
                /**
                 * 직전 노드와 다른 집합으로 셋팅 : 1 또는 0으로
                 * 직전 노드가 1이었으면 0이 입력되고 0이었으면 1이 입력됨
                 */
                check[i] = (check[node] + 1) % 2;
                DFS(i);
            } else {
                if(check[node] == check[i]) {
                    isEven = false;
                }
            }
        }
    }
}