Graph의 정의

그래프는 여러개의 점들이 서로 복잡하게 연결되어 있는 관계를 표현한 자료구조

Graph의 구조

직접적인 관계가 있는 경우 두 점 사이를 이어주는 선이 있습니다.
간접적인 관계라면 몇 개의 점과 선에 걸쳐 이어집니다.
하나의 점을 그래프에서는 정점(vertex)이라고 표현하고, 하나의 선은 간선(edge)이라고 합니다.

Graph의 표현 방식

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

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

• 인접 리스트
  인접 리스트는 각 정점이 어떤 정점과 인접하는지를 리스트의 형태로 표현합니다
  메모리를 효율적으로 사용하고 싶을 때 인접 리스트를 사용합니다.
  인접 행렬은 연결 가능한 모든 경우의 수를 저장하기 때문에 상대적으로 메모리를 많이 차지합니다.

알아둬야 할 Graph 용어들

정점 (vertex): 노드(node)라고도 하며 데이터가 저장되는 그래프의 기본 원소입니다.
간선 (edge): 정점 간의 관계를 나타냅니다. (정점을 이어주는 선)
인접 정점 (adjacent vertex): 하나의 정점에서 간선에 의해 직접 연결되어 있는 정점을 뜻합니다.
가중치 그래프 (weighted Graph): 연결의 강도(추가적인 정보, ex. 서울-부산으로 가는 거리 등)가 얼마나 되는지 적혀져 있는 그래프를 뜻합니다.
비가중치 그래프 (unweighted Graph): 연결의 강도가 적혀져 있지 않는 그래프를 뜻합니다.
무(방)향 그래프 (undirected graph): 앞서 보았던 내비게이션 예제는 무(방)향 그래프입니다. 서울에서 부산으로 갈 수 있듯, 반대로 부산에서 서울로 가는 것도 가능합니다. 하지만 단방향(directed) 그래프로 구현된다면 서울에서 부산을 갈 수 있지만, 부산에서 서울로 가는 것은 불가능합니다(혹은 그 반대). 만약 두 지점이 일방통행 도로로 이어져 있다면 단방향인 간선으로 표현할 수 있습니다.
진입차수 (in-degree) / 진출차수 (out-degree): 한 정점에 진입(들어오는 간선)하고 진출(나가는 간선)하는 간선이 몇 개인지를 나타냅니다.
인접 (adjacency): 두 정점 간에 간선이 직접 이어져 있다면 이 두 정점은 인접한 정점입니다.
자기 루프 (self loop): 정점에서 진출하는 간선이 곧바로 자기 자신에게 진입하는 경우 자기 루프를 가졌다 라고 표현합니다. 다른 정점을 거치지 않는다는 것이 특징입니다.
사이클 (cycle): 한 정점에서 출발하여 다시 해당 정점으로 돌아갈 수 있다면 사이클이 있다고 표현합니다. 내비게이션 그래프는 서울 —> 대전 —> 부산 —> 서울 로 이동이 가능하므로, 사이클이 존재하는 그래프입니다.

class GraphWithAdjacencyMatrix {
	constructor() {
		this.matrix = [];//빈 매트릭스 선언
	}

	addVertex() {
        //버텍스(정점)를 추가합니다.
        //버텍스를 추가합니다.
    // 처음 추가 될때 for문 조건 불만족. 18번째 줄 실행 [0]
    // 2번째 추가시 조건만족 for문에서 [0,0]
    // 18번째 줄을 실행하면 [[0,0],[0,0]]
    // 3번째 추가시 [[0,0,0],[0,0,0]]
    // 18번째 줄 실행 [[0,0,0],[0,0,0],[0,0,0]]
		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(this.matrix[vertex]){
          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
  return this.matrix[from][to] === 1
	}

	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) {
      console.log("범위가 매트릭스 밖에 있습니다.");
      return;
		}
        //TODO: 간선을 지워야 합니다.
        this.matrix[from][to]= 0;
	}
}