JS => 자료구조 (Graph)

Graph

컴퓨터 공학에서 얘기하는 그래프는
우리가 수학에서 접했던 그래프 모양이 아닌,
복잡한 네트워크 망과 같은 아래 모습을 가지고 있다.

위 사진처럼 그래프는 여러개의 점들이 서로 복잡하게 연결되어 있는 관계를 표현한 자료구조다.
직접적인 관계가 있는 경우 두 점 사이를 이어주는 선이 있고,
간접적인 관계라면 몇 개의 점과 선에 걸쳐 이어진다.

정점 : 그래프에서 하나의 점
간선 : 그래프에서 하나의 선

그래프의 실사용 예제로 네비게이션을 들 수 있다.
서울에 사는 내가 대전에 사는 친구를 픽업해서 부산으로 간다면,
아래와 같다.

정점: 서울, 대전, 부산
간선: 서울—대전, 대전—부산, 부산—서울

위의 간선에서는 거리 등의 정보를 알 수 없는데, 이를 비가중치 그래프라 하고,
거리가 들어가면 가중치 그래프라 한다.
즉,

정점: 서울, 대전, 부산
간선: 서울—140km-대전, 대전—200km-부산, 부산—325km-서울

---

알아야 할 그래프 용어

1. 무(방)향그래프
   위 내비게이션 예제는 무(방)향 그래프다.
   서울에서 부산으로 갈 수 있듯, 반대로 부산에서 서울로 가는것도 가능하다.
   하지만 단방향 그래프로 구현 된다면 서울에서 부산을 갈 수 있지만,
   부산에서 서울로 가는 것은 불가능하다(혹은 그 반대).
   만약 두 지점이 일방통행 도로로 이어져 있다면 단방향인 간선으로 표현할 수 있다.
   
   
2. 진입차수 / 진출차수
   한 정점에 진입(들어오는 간선)하고 진출(나가는 간선)하는 간선이 몇 개인지를 나타낸다.
   
   
3. 인접
   두 정점간에 간선이 직접 이어져 있다면 이 두 정점은 인접한 정점이다.
   
   
4. 자기 루프
   정점에서 진출하는 간선이 곧바로 자기 자신에게 진입하는 경우 자기 루프를 가졌다 라고 표현한다. 다른 정점을 거치지 않는다는 것이 특징이다.
   
   
5. 사이클
   한 정점에서 출발하여 다시 해당 정점으로 돌아갈 수 있다면 사이클이 있다고 표현한다.
   내비게이션 예시처럼 서울 —> 대전 —> 부산 —> 서울 로 이동이 가능한 사이클.

---

그래프의 표현 방식

1. 인접행렬

인접 행렬은 서로 다른 정점들이 인접한 상태인지를 표시한 행렬로,
2차원 배열의 형태로 나타낸 방식이다.

만약 A라는 정점과 B라는 정점이 이어져 있다면 1(true),
이어져 있지 않다면 0(false)으로 표시한 일종의 표다.

위 표를 예시로 들자면,
A의 진출차수는 1개: A —> C
[0][2] === 1
B의 진출차수는 2개: B —> A, B —> C
[1][0] === 1
[1][2] === 1
C의 진출차수는 1개: C —> A
[2][0] === 1

인접행렬은 언제 사용?!

1. 두 정점 사이에 관계가 있는지, 없는지 확인하기에 용이하다.
2. 가장 빠른 경로를 찾고자 할 때 주로 사용된다.

1. 인접리스트

인접 리스트는 각 정점이 어떤 정점과 인접한지를 리스트의 형태로 표현한 방식이다.
인접행렬 그래프를 인접리스트로 표현하면 아래와 같다.

인접리스트는 언제 사용?!

메모리를 효율적으로 사용하고 싶을 때 인접 리스트를 사용한다.
인접 행렬은 연결 가능한 모든 경우의 수를 저장하기 때문에 상대적으로 메모리를 많이 차지한다.

---

인접행렬 구현

class GraphWithAdjacencyMatrix {
	constructor() {
		this.matrix = [];
	}
<br>
	addVertex() { // 정점을 추가하는 함수
		const currentLength = this.matrix.length;
		for (let i = 0; i < currentLength; i++) {
			this.matrix[i].push(0);
		}
		this.matrix.push(new Array(currentLength + 1).fill(0)); // 정점의 수에 따라 행렬로 만들어주는 코드(정점이 3개라면 3X3 행렬)
	}
<br>
	contains(vertex) { // 해당 정점이 존재하는지 확인하는 함수
    if(this.matrix[vertex]) { // matrix에 해당 정점(vertex)이 존재한다면
      return true
    }
    return false;
	}
<br>
	addEdge(from, to) { // 정점 사이의 간선을 추가하는 함수
		const currentLength = this.matrix.length;
		if (from === undefined || to === undefined) { // from: 출발정점, to: 도착정점
			return;
		}
        // 간선을 추가할 수 없는 상황에서는 추가하지 않는다.
		if (from + 1 > currentLength || to + 1 > currentLength || from < 0 || to < 0) {
			return;
		}
        // 간선을 추가
    this.matrix[from][to] = 1
	}
<br>
	hasEdge(from, to) { // 정점 사이에 간선이 존재하는지 여부를 확인하는 함수
    if(this.matrix[from][to]) {
      return true;
    }
    return false
	}
<br>
	removeEdge(from, to) { // 정점 사이의 간선을 삭제하는 함수
		const currentLength = this.matrix.length;
		if (from === undefined || to === undefined) {
			return;
		}
        // 간선을 지울 수 없는 상황에서는 지우지 말아야 한다.
		if (from + 1 > currentLength || to + 1 > currentLength || from < 0 || to < 0) {
      return;
		}
    this.matrix[from][to] = 0
	}
}