Graph(그래프) ✍🏻

Graph(그래프)📍

---

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

그래프의 실사용 예제 📌

• 포탈 사이트의 검색 엔진, SNS에서 사람들과의 관계, 네이게이션(길찾기) 등에서 사용하는 자료구조가 그래프다.
• 세 가지 모두 수 많은 정점을 가지고 있고, 서로 관계가 있는 정점은 간선으로 이어져 있다.

알아둬야 할 그래프 용어들 📌

• 단방향그래프(directed graph) : 네이게이션은 단방향 그래프이다. 서울에서 부산으로 갈 수 있듯, 반대로 부산에서 서울로 가는것도 가능하다. 하지만 단방향(directed) 그래프로 구현되다면 서울에서 부산을 갈 수 있지만, 부산에서 서울로 가는 것은 불가능하다(혹은 그 반대). 만약 두 지점이 일방통행 도로로 이어져 있다면 단방향인 간선으로 표현할 수 있다.

• 진입차수(in-degree) / 진출차수 (out-degree) : 한 정점에 진입(들어오는 간선)하고 진출(나가는 간선)하는 간선이 몇 개인지를 나타낸다.

• 인접(adjacency) : 두 정점간에 간선이 직접 이어져 있다면 이 두 정점은 인접한 정점입니다.

• 자기 루프(self loop) : 정점에서 진출하는 간선이 곧바로 자기 자신에게 진입하는 경우 자기 루프를 가졌다 라고 표현한다. 다른 정점을 거치지 않는다는 것이 특징

• 사이클(cycle) : 한 정점에서 출발하여 다시 해당 정점으로 돌아갈 수 있다면 사이클이 있다고 표현한다.
  내비게이션 그래프는 서울 -> 대전 -> 부산 -> 서울 로 이동이 가능하므로, 사이클이 존재하는 그래프 이다.

그래프의 표현 방식 (인접 행렬 & 인접 리스트)

인접 행렬

• 두 정점을 바로 이어 주는 간선이 있다면 이 두 정점은 인접하다.
• 인접 행렬은 서로 다른 정점들이 인접한 상태인지를 표시한 행렬로 2차원 배열의 형태로 나타낸다.
• 만약 A라는 정점과 B라는 정점이 이어져 있다면 1(true), 이어져 있지 않다면 0(false)으로 표시한 일종의 표
• 만약 가중치 그래프라면 1 대신 관계에서 의미 있는 값을 저장한다.

인접 리스트

• 보통은 중요하지 않다.
• 그래프, 트리, 스택, 큐 등 모든 자료 구조는 구현하는 사람의 편의와 목적에 따라 기능을 추가/삭제할 수 있다.
• 그래프를 인접 리스트로 구현할 때, 정점별로 살펴봐야 할 우선 순위를 고려해 구현할 수 있다. 이때, 리스트에 담겨진 정점을 우선 순위별로 정렬할 수 있다. 우선 순위가 없다면, 연결된 정점들을 단순하게 나열한 리스트가 된다.
• 우선 순위를 다뤄야 한다면 더 적합한 자료구조(ex. queue, heap)를 사용하는 것이 합리적이다. 따라서 보통은 중요하지 않다. (언제나 예외는 있다...)

Graph 자료구조

// directed graph (방향 그래프)
// unweighted (비가중치)
// adjacency matrix (인접 행렬)
// 이해를 돕기 위해 기존 배열의 인덱스를 정점으로 사용합니다 (0, 1, 2, ... --> 정점)

class GraphWithAdjacencyMatrix {
	constructor() {
		this.matrix = [];
	}

	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));
	}

	contains(vertex) {
        //TODO: 버텍스(인덱스)가 있는지 확인합니다.
        if(0 <= vertex && vertex < this.matrix.length){ 
          return true;
        }
        return false;
	}

	addEdge(from, to) {
		const currentLength = this.matrix.length;
		if (from === undefined || to === undefined) {
			console.log("2개의 인자가 있어야 합니다.");
			return;
		}
        //TODO: 간선을 추가할 수 없는 상황에서는 추가하지 말아야 합니다.
		if (from + 1 > currentLength || to + 1 > currentLength || from < 0 || to < 0) {
			console.log("범위가 매트릭스 밖에 있습니다.");
			return;
		}
        //TODO: 간선을 추가해야 합니다.
      this.matrix[from][to] = 1;
	}

	hasEdge(from, to) {
		//TODO: 두 버텍스 사이에 간선이 있는지 확인합니다.
    if(this.matrix[from][to] === 1){
      return true;
    }
    return false;
	}

	removeEdge(from, to) { //엣지 제거
		const currentLength = this.matrix.length;
		if (from === undefined || to === undefined) {
			console.log("2개의 인자가 있어야 합니다.");
			return;
		}
        //TODO: 간선을 지울 수 없는 상황에서는 지우지 말아야 합니다.
		if (from + 1 > currentLength || to + 1 > currentLength || from < 0 || to < 0) { //from, to 범위가 넘어서는 경우 간선을 지울 수 없다.
      return;
		}
        //TODO: 간선을 지워야 합니다.
        this.matrix[from][to] = 0;
	}
}