[그래프] 그래프의 표현 - 엣지리스트, 인접행렬, 인접리스트 정리

그래프의 표현

그래프를 표현할때는 대표적으로 엣지리스트, 인접행렬, 인접리스트 3가지 방법으로 표현한다.

 

그래프 예

① → ② → ⑤ ↓　  ↓ ↗ ③ → ④

 

엣지리스트

엣지를 중심으로 그래프를 표현한다.

배열에 출발,도착 노드를 각각 저장하여 엣지를 표현한다.

가중치가 있는 노드의 경우 배열에 가중치를 추가 행으로 함께 저장한다.

 

가중치 없는 그래프 표현

출발, 도착 2개의 노드만 2개의 배열행을 구성하여 표현한다.

ex) 첫번째 행을 [1, 2]로 표현하며 1에서 2로 뻗어가는 엣지를 뜻한다.

ⓢ	ⓔ
1	2
1	3
3	4
2	4
2	5
4	5

이처럼 방향이 있는 그래프는 순서에 맞게 노드를 배열에 저장하는 방식으로 표현한다.

노드를 배열에 저장하여 엣지를 표현하므로 엣지리스트 라고 한다.

 

방향이 없는 그래프의 경우

만약 방향이 없는 그래프라면 [1, 2]와 [2, 1]은 같은표현이다.

따라서 최 상단에 출발,도착 노드를 두지 않거나 아래 표와 같이 양방향 그래프와 같이 중복해서 표현한다.

ⓢ	ⓔ
1	2
2	1
1	3
3	1
3	4
4	3
2	4
4	2
2	5
5	2
4	5
5	4

 

가중치 있는 그래프 표현

기존 배열에서 가중치를 저장할 행을 1개 늘린다

1에서 2로 향하는 가중치가 8인 엣지는 [1, 2, 8]로 표현한다.

ⓢ	ⓔ	ⓥ
1	2	8
1	3	3
3	4	13
2	4	4
2	5	15
4	5	2

 

단점

엣지를 중심으로 그래프를 표현하므로 노드 디펜던시 존재 즉, 특정 노드와 관련되어 있는 엣지 탐색의 경우 탐색이 어렵다.

예를들어 노드 ②에서 출발하는 엣지 검색시 ⓢ를 기준으로 정렬하기도 어렵거니와, 모든 시작 노드를 검사해야 한다.

(모든 시작 노드에서 ②를 찾아야 하므로)

 

따라서 노드 중심 알고리즘 보다는 노드 디펜던시 하지 않은 엣지 기준 탐색인 벨만포드, 크루스칼 알고리즘에 사용된다.

---

인접행렬

2차원 배열을 자료구조로 이용하여 그래프를 표현한다.

엣지 리스트와 다르게 노드 중심의 그래프를 표현한다.

예를들어 5개의 노드가 있을 경우 5X5 인접 행렬로 표현한다.

노드가 N개일 경우 [N][N] 으로 표현한다.

엣지리스트와의 차이점은 인덱스를 이용하여 시작/도착 노드를 표현한다.

 

가중치 없는 그래프 표현

	도착노드→
출 발 노 드 ↓	인덱스	1	2	3	4	5
	1		1	1
	2				1	1
	3				1
	4					1
	5

위와 같이 연결된 각 노드의 교차지점에 1을 저장하여 표현한다.

(1을 저장하는 이유는 가중치가 없기때문)

 

가중치 있는 그래프 표현

	도착노드→
출 발 노 드 ↓	인덱스	1	2	3	4	5
	1		8	3
	2				4	15
	3				13
	4					2
	5

가중치가 있는 그래프의 경우 1이 저장되는 교차지점에 1 대신 가중치를 저장한다.

 

장점

• 노드 중심이므로 두 노드를 연결하는 엣지 여부와 가중치 값은 배열 직접 접근시 바로 확인이 가능하다.

단점

1. 노드와 관련된 엣지 탐색시 N번 접근해야 하므로 노드 개수에 비해 엣지가 적을 경우 공간 효율성이 감소한다.
   (N번 접근하는 이유 - 노드 ②에서 출발하는 엣지 검색시 [2][N] 이므로
   2 → 5 엣지를 탐색한다고 가정한다면 5번만에 탐색된다.)
2. 노드가 많은 경우 2차원 배열 선언 자체가 불가능한 결함이 발생할 가능성이 존재한다.

인접 행렬은 노드의 개수에 따라 사용 여부를 적절하게 판단하는 능력이 필요하다.

---

인접리스트

가변적 이므로 ArrayList로 그래프를 표현한다.

(노드 ①과 노드 ⑤의 에지리스트 수가 항상 일정하지 않기 때문)

노드의 개수만큼 ArrayList를 선언하며 ArrayList<자료형>[N] 과 같이 표현한다.

실제 그래프 알고리즘은 Edge < Node 중심 이므로 인접 리스트 사용 빈도가 제일 높다.

 

 

가중치 없는 그래프

ⓢ	ⓔ
1	[[2], [3]]
2	[[3], [5]]
3	[[4]]
4	[[5]]
5

ArrayList[1]에 [[2], [3]]이 연결된 형태이다.

이는 노드 1과 2가 엣지로, 노드 1과 3이 엣지로 연결되어 있다는 것을 의미한다.

이를 JAVA코드로 나타내면 아래와 같이 비유할 수 있다.

class Node {
    int end; // 도착노드
    
    public Node(int end) {
    }
}

public class Solution {
    public static void main(arg[]) {
    
        Object[] nodeArr = new Object[N]; //노드의 갯수 초기화
        ArrayList<Node> node1EdgeList = new ArrayList<>();
        node1EdgeList.add(new Node(2));// 첫번째 1->2 저장한다.
        node1EdgeList.add(new Node(3));// 첫번째 1->3 저장한다.
        nodeArr[0] = node1EdgeList; // 1번 노드에 대한 엣지들을 담은 리스트를 배열 0번에 저장
        
        /* 0~4까지 노드 1~5까지의 에지 저장 반복 */
        
    }
}

 

가중치 있는 그래프

(실제 코딩 테스트에서는 대부분 가중치가 존재 - 90% )

ⓢ	ⓔ
1	[[2, 8], [3, 3]]
2	[[4, 4], [5, 15]]
3	[[4, 13]]
4	[[5, 2]]
5

 

ArrayList[1]에 [[2,8], [3,3]]이 연결된 형태이다.

이는 노드 1과 2가 가중치 8의 엣지로, 노드 1과 3이 가중치 3엣지로 연결되어 있다는 것을 의미한다.

이를 JAVA 코드로 나타내면 아래와 같이 비유할 수 있다.

class Node {
    int end; // 도착노드
    int value; // 가중치
    
    public Node(int end, int value) {
    }
}

public class Solution {
    public static void main(arg[]) {
    
        Object[] nodeArr = new Object[N]; //노드의 갯수 초기화
        ArrayList<Node> node1EdgeList = new ArrayList<>();
        node1EdgeList.add(new Node(2, 8));// 첫번째 1->2 가중치 8을 저장한다.
        node1EdgeList.add(new Node(3, 3));// 첫번째 1->3 가중치 3을 저장한다.
        nodeArr[0] = node1EdgeList; // 1번 노드에 대한 엣지들을 담은 리스트를 배열 0번에 저장
        
        /* 0~4까지 노드 1~5까지의 에지 저장 반복 */
        
    }
}

 

인접 리스트를 이용한 그래프 표현은 그래프를 표현하는 다른 방법에 비해 복잡한 편이다.

하지만 노드와 연결되어 있는 엣지를 탐색하는 시간이 매우 뛰어나다.

(코드상에서 nodeArr[2]로 노드배열 인덱스로 노드에 접근하기만 하면 나머지 엣지리스트에 대해 검색하면 되므로)

인접 행렬과 비교했을때 인접행렬은 빈공간을 탐색한다. 이는 시,공간 복잡도 효율성이 모두 떨어진다.

(인접 행렬은 인접 노드를 순차적으로 탐색할때 까지 빈공간과 시간이 소요되기 때문에..)

인접 리스트는 노드 접근 후 리스트로 관리하므로 노드 개수가 커도 공간 효율성이 좋아 메모리 초과 에러 또한 발생하지 않는다.

 

따라서 이러한 장접으로 실제 코딩테스트에서 인접 리스트를 이용한 그래프를 표(구)현 하는것을 선호한다.