[Algorithm] Graph 표현 방식

알고리즘에서 '그래프(Graph)' 는 굉장히 중요한 자료구조이다.

실제 코딩 테스트에서도 그래프 관련 문제가 자주 나오기 때문에 알고리즘 공부를 한다면 꼭 알아야 한다.

 

그래프란 노트(Node) 와 에지(Edge) 로 구성된 집합이다. 노드는 데이터의 표현 단위이며 에지는 이를 연결한다.

가장 잘 알려진 그래프 알고리즘인 DFS, BFS, Dijkstra 등 모두 그래프를 알아야 이해할 수 있다.

 

오늘은 그래프를 표현하는 여러 방법 중 몇 가지를 알아보고자 한다.

코딩 테스트를 준비한다면 꼭 꼭 개념을 공부하고 넘어가도록 하자.

---

1️⃣ 에지 리스트(Edge List)

에지 리스트는 말 그대로 에지를 중심으로 그래프를 표현하는 방법이다.

보통 2차원 배열을 사용하며 배열에 출발, 도착 노드와 가중치를 저장하여 그래프를 표현한다.

 

1) 가중치 없는 그래프

가중치 없는 그래프는 말 그대로 노드와 노드 사이에 가중치가 없는 에지로 연결된 그래프를 말한다.

이는 연결 노드만 알면 되기 때문에 2차원 배열을 사용한다. 노드의 자료형은 다양하게 사용할 수 있다.

 

노드의 개수와 상관 없이 N개의 에지가 있다고 하자.

그렇다면 에지 리스트의 크기는 Edge[N][2] 이 된다.

 

여기서 행의 크기는 에지의 개수와 같다. 열의 크기는 2로, 각각 출발 노드와 도착 노드를 말한다.

다음과 같은 그래프가 있다고 하자.

 

 

 

 

위 그래프를 2차원 배열로 표현하면 다음과 같을 것이다.

 

1	2
1	5
2	3
2	4
3	5
4	5

 

 

배열의 인덱스와는 상관 없이 0행을 보면 [1][2]는 '1번 노드에서 2번 노드로 가는 에지가 있다.' 라는 뜻이다.

이처럼 직관적으로 그래프를 표현하며 어떤 노드끼리 연결되어있는지 알 수 있다.

또한 에지의 수가 행의 개수와 똑같다.

 

* 위 그래프는 방향이 있지만, 무방향 그래프의 경우 [1][2]와 [2][1]은 똑같은 표현이다.

 

2) 가중치 있는 그래프

가중치가 있다면 3차원 배열을 사용하면 된다.  가중치 없는 그래프에서 사용했던 2차원 배열에 가중치만 추가하는 것이다.

즉, 에지 리스트의 크기는 Edge[N][2][1]가 될 것이다.

 

 

 

위 그래프는 각 에지마다 가중치가 있다.

이를 에지 리스트로 표현하면 다음과 같다.

 

1	2	1
1	5	3
2	3	6
2	4	2
3	5	4
4	5	5

 

단, 무방향 그래프이기 때문에 출발 노드와 도착 노드를 바꿔도 상관은 없다.

이처럼 에지 리스트는 직관적인 그래프 표현이 가능하며, 비교적 구현이 쉽다.

 

그러나 특정 노드와 관련된 에지를 탐색하기는 쉽지 않다는 단점이 있다. 

따라서 노드 중심의 알고리즘에는 잘 사용되지 않는다.

주로 벨만 포드나 크루스칼 알고리즘에 사용된다.

---

2️⃣ 인접 행렬(Adjacency Matrix)

1) 가중치 없는 그래프

인접 행렬은 역시 2차원 배열을 이용하여 그래프를 표현한다. 

또한 에지 리스트와는 다르게 노드를 중심으로 표현한다.

따라서 행의 개수는 에지의 개수가 아닌 노드의 개수에 따라 달라진다.

 

 

 

 

다시 위 그래프를 보자.

 

노드 1에서 노드2로 가는 에지를 인접 행렬에서는 노드의 번호인 1과 2를 인덱스로 사용한다.

즉, 2차원 배열에서 1행 2열에 1을 저장함으로써 에지가 있다는 것을 표현한다.

노드 2와 노드 3간에는 에지가 없으므로 2행 3열에는 0이 저장된다.

 

index	1	2	3	4	5	6
1	0	1	0	0	0	0
2	0	0	0	1	0	0
3	1	0	0	0	0	0
4	0	0	1	0	1	1
5	0	0	0	0	0	0
6	0	0	0	0	0	0

 

쉽게 말해 노드의 번호를 인덱스화하여 표현한다고 생각하면 된다.

행은 출발 노드 번호, 열은 도착 노드 번호, 배열의 값이 1이면 에지가 있고 0이면 없음을 의미한다.

 

2) 가중치 있는 그래프

 

 

만약 위처럼 가중치가 있는 그래프의 경우, 0과 1 대신 가중치를 넣어주면 된다.

이를 인접 행렬로 표현하면 다음과 같다.

 

index	1	2	3	4	5
1	0	1	0	0	3
2	1	0	6	2	0
3	0	6	0	0	4
4	0	2	0	0	5
5	3	0	4	5	0

 

인접 행렬을 이용한 그래프는 비교적 구현이 쉽다.

다음은 인접 행렬을 저장하는 간단한 코드이다.

 

public class Main{
	public static void main(String[] args){
    	Scanner sc = new Scanner(System.in);
        
        // 노드의 개수
        int N = sc.nextInt();
        
        int[][] graph = new int[N+1][N+1];
        
        for(int i=0;i<N;i++){
            for(int j=0;j<N;j++){
            	int start = sc.nextInt();
                int end = sc.nextInt();
                int weight = sc.nextInt();
                
                graph[start][end] = weight;
            }
       	}
    }
}

 

인접 행렬은 두 노드를 연결하는 에지의 여부와 가중치값을 직접 접근, 확인할 수 있기에 많이 사용된다. 

그러나 노드와 관련된 에지를 탐색하기 위해선 N번 접근해야하므로 노드보다 에지의 개수가 적을 때엔 공간 효율성이 떨어진다. 또한 노드의 개수가 많아지면 배열의 크기가 커진다. (3만 개 이상이면 오류 발생)

---

3️⃣ 인접 리스트 (Adjacency List)

1) 가중치 없는 그래프

인접 리스트는 배열과 ArrayList 로 표현한다. 노드의 개수와 같은 행의 배열 안에 리스트가 들어간다.

다시 예시를 보자.

 

 

인접 리스트를 사용하기 위해선 먼저 리스트를 값으로 갖는 배열을 생성해야 한다.

N 개의 노드를 표현하기 위해선 N 행의 배열을 만들고, 각 행별 리스트는 해당 노드와 연결된 노드를 저장한다.

 

1	->	2
2	->	4
3	->	1
4	->	3	5	6
5	->
6	->

 

코드로 알아보도록 하자.

 

public class Main{
	public static void main(String[] args){
    
    	// N 은 노드의 개수
    	List<Integer>[] = graph[N+1];
        
        // 초기화 필수
        for(int i = 1; i <= N; i++){
        	graph[i] = new ArrayList<>();
        }
        
        for(int i=0; i < 에지의 개수; i++){
        	int start = sc.nextInt();
            int end = sc.nextInt();
            
            graph[start].add(end);
        }
    }
}

 

2) 가중치 있는 그래프

인접 리스트로 가중치 있는 그래프를 표현하기 위해서는 노드 클래스를 하나 만들어주어야 한다.

필자는 상황에 따라 클래스명을 정의하는데, 보통 'Node', 'Point' 등으로 정의한다.

해당 클래스엔 도착 노드, 가중치값이 멤버 변수로 들어간다.

 

class Node{
    int next, weight;
    
    public Node(int next, int weight){
        this.next = next;
       	this.weigth = weight;
    }
}

 

다음 그래프를 보자.

 

 

1	->	[2,1]	[5,3]
2	->	[1,1]	[3,6]	[4,2]
3	->	[2,6]	[5,4]
4	->	[2,2]	[5,5]
5	->	[1,3]	[3,4]	[4,5]

 

 

한 가지 다른 점이 있다면 리스트의 값으로 Node 클래스가 들어가는 것이다.

해당 배열을 'graph' 라고 하면 graph[1] = {[2,1] , [5,3]} 이 저장된다.

이는 1번 노드는 2번 노드와 가중치 1인 에지로, 5번 노드와 가중치 3인 에지로 연결된다는 뜻이다.

---

이처럼 그래프를 표현하는 방법엔 여러 가지가 있다.

DFS, BFS, Dijkstra, 벨만-포드, 플로이드 워셜, MST 등 그래프와 관련된 여러 가지 알고리즘이 있지만,

문제와 어떤 알고리즘을 사용하느냐에 따라 그래프를 표현하는 방법은 각양각색이다.

 

모든 방법을 충분히 익혀야 데이터를 자유자재로 저장할 수 있으며, 효율적인 방법으로 문제를 접근할 수 있을 것이다.