[자료구조] 그래프의 표현

1. 에지 리스트

1) 개념

에지 리스트는 에지를 중심으로 그래프를 표현한다. 2차원 배열에 각 에지의 출발 노드와 도착 노드를 저장한다. 만약 가중치가 있는 에지일 경우 각 에지의 출발 노드, 도착 노드, 가중치를 저장한다.

 

2) 종류

ⓛ 가중치가 없는 에지

int[2][6] edgeList = {{1,2},{1,3},{2,5},{2,4},{3,4},{4,5}};

② 가중치가 있는 에지

int[2][6] edgeList = {{1,2,4},{1,3,1},{2,5,2},{2,4,1},{3,4,7},{4,5,4}};

+ 만약 방향이 없는 에지면 {1,2}와 {2,1}은 같은 것이니 둘 중 하나만 저장하면 된다.

 

3) 특징

• 구현하기가 쉽다
• 에지만 딱 나와있기 때문에 특정 노드가 어떤 에지와 연결되어 있는지, 그래서 특정 노드가 어떤 다른 노드와 연관되어 있는지 파악하기가 힘들다.
• 벨만 포드, 크루스칼 알고리즘에 사용된다.

 

2. 인접 행렬

1) 개념

노드 중심으로 그래프를 표현한다. 노드개수*노드개수 만큼 2차원 행렬을 만들고, 출발 노드를 행으로, 도착 노드를 열로 본다. 그리고 노드 하나씩 살피면서 출발노드와 도착노드가 정해지는 경우, 즉 에지가 있어서 노드끼리 연결되는 경우 해당 행열에 표시를 한다. 만약 가중치가 없으면 그냥 1로 있다는 표시를 하고, 가중치가 있으면 해당 가중치를 저장한다.

 

2) 종류

 

ⓛ 가중치가 없는 에지

 

int[5][5] adjMatrix = {{0,1,1,0,0},{0,0,0,1,1},{0,0,0,1,0},{0,0,0,0,1},{0,0,0,0,0}};

② 가중치가 있는 에지

int[5][5] adjMatrix = {{0,6,7,0,0},{0,0,0,3,2},{0,0,0,1,0},{0,0,0,0,8},{0,0,0,0,0}};

 

3) 특징

• 구현이 쉽다.
• 노드끼리 연결이 되어 있는지와 가중치를 배열에 직접 접근하면 바로 확인할 수 있다. adjMatrix[1][2] 와 같이 접근을 했을 때 값이 0이면 노드 1과 2가 연결이 안 되어 있다는 것이고, 값이 존재하면 노드가 연결되어 있다는 것이다. 또한, 가중치를 저장했을 경우 연결이 되어 있다는 것과 동시에 연결된 에지의 가중치도 바로 확인할 수 있다.
• 하지만 특정 노드와 관련되어 있는 에지를 탐색하려면 노드의 수만큼 접근해야 한다. 예를 들어 1번 노드와 관련된 에지를 탐색하려면 adjMatrix[1][1] 부터 adjMatrix[1][5] 를 모두 살펴야만 알 수 있다. (인덱스 시작이 1이라고 가정) 그래서 노드 개수에 비해 에지가 적을 때는 배열에 남는 공간이 많이 생겨 공간 효율성이 떨어진다. 배열의 공간은 노드 개수에 의해 정해지는데, 에지가 많이 없으면 빈 공간이 많게 된다.
• 배열의 공간은 노드개수*노드개수이기 때문에 노드 개수가 너무 많으면 2차원 배열 자체를 선언 못할 수도 있다.

 

3. 인접 리스트

1) 개념

노드의 개수만큼 1차원 배열을 선언한다. 1차원 배열의 인덱스는 노드 번호를 의미한다. 각 인덱스 안에는 ArrayList가 들어있고, 해당 ArrayList는 인덱스가 가리키는 노드와 연결되어 있는 노드를 담고 있다.

 

2) 종류

ⓛ 가중치가 없는 에지

ArrayList<Integer>[] adjList = new ArrayList[6]; //인덱스 1부터 사용하기 위해 노드개수보다 1 큰 6으로 설정
// 각 배열에 ArrayList 담기 위해 초기화
for(int i = 1; i<=5; i++){
	adjList[i] = new ArrayList<Integer>();
}
// 에지 돌면서 담기(무방향을 가정)
for(int i = 0; i<6; i++){
	adjList[노드인덱스1].add(노드인덱스2);
    adjList[노드인덱스2].add(노드인덱스1);
}

② 가중치가 있는 에지

ArrayList<Integer>[] adjList = new ArrayList[6]; //인덱스 1부터 사용하기 위해 노드개수보다 1 큰 6으로 설정
// 각 배열에 ArrayList 담기 위해 초기화
for(int i = 1; i<=5; i++){
	adjList[i] = new ArrayList<Integer>();
}
// 에지 돌면서 담기(무방향을 가정)
for(int i = 0; i<6; i++){
	adjList[노드인덱스1].add(new Node(노드인덱스2, 가중치));
    adjList[노드인덱스2].add(new Node(노드인덱스1, 가중치));
}

class Node(){
	int e;
    int value;
    public Node(int e, int value){
    	this.e = e;
        this.value = value;
    }
}

 

3) 특징

• 구현이 복잡하다.
• 노드와 연결되어 있는 다른 노드들을 파악하고자 할 때 효율이 좋다.
• 노드 개수가 커도 노는 배열 공간이 없어서 공간 효율이 좋다.
• 실제 코테에서 많이 사용하는 방식