What's Graph?

여러 점과 선으로 이어진 복잡한 네트워크 같은 모습의 그래프는 정점과 간선으로 이루어져있다.
정확히는 정점(Vertex)간의 관계를 표현하는 조직도.
그래프는 트리와는 달리, 정점마다 간선이 없을 수도 있고 부모자식이라는 개념이 존재하지 않는다.
또한 그래프는 네트워크 모델 즉, 객체와 이에 대한 관계를 나타내는 유연한 방식으로 이해할 수 있다. 실생활에서 예를 찾는다면 대표적으로 지하철 노선도를 들 수 있다.
그래프는 알고리즘에서 굉장히 많이 사용되는데 특히 그래프를 순회하는 방식인 DFS와 BFS 중요!

• 비가중치 그래프: 각 정점간의 연결 유무만을 판단
• 가중치 그래프: 간선에 연결 정도에 대한 정보를 담은 그래프

그래프 용어

• 정점(vertice) : 노드(node)라고도 하며 데이터가 저장된다.
• 간선(edge): 링크(arcs)라고도 하며 노드간의 관계를 나타낸다.
• 인접 정점(adjacent vertex) : 두 정점간에 간선이 직접 이어져 있다면 인접한 정점
• 단순 경로(simple-path): 경로 중 반복되는 정점이 없는 것, 같은 간선을 지나지 않는 경로
• 차수(degree): 무방향 그래프에서 하나의 정점에 인접한 정점의 수
• 진출 차수(out-degree) : 방향 그래프에서 사용되며, 한 노드에서 외부로 향하는 간선의 수
• 진입차수(in-degree) : 외부 노드에서 들어오는 간선의 수
• 자기 루프(self loop): 간선이 다른 정점을 거치지 않고 곧바로 자신에게 진입하는 경우
• 사이클(cycle): 출발과 도착이 동일한 정점인 경우

그래프의 표현 방식

인접행렬(Adjacency Materix)와 인접리스트(Adjacency List)방식이 있는데,
두 구현 방식은 각각의 상반된 장단점을 가지고 있다.

인접행렬 Adjacency Materix

인접행렬은 그래프의 노드를 2차원 배열로 만든 것
정점이 이어져 있다면 1(true), 아니면 0(false)으로 표시한 일종의 표이다.
만약 가중치 그래프라면 1 대신, 관계에서 의미 있는 값을 저장한다.

장점

• 2차원 배열 안에 모든 정점들의 간선 정보를 담기 때문에
  배열의 위치를 확인만 하면 연결 정보를 조회할 때 O(1)의 시간 복잡도로 가능하다.
• 구현이 비교적 간편하다.

단점

• 모든 정점에 간선 정보를 대입해야 하므로 O(n²)의 시간복잡도가 소요된다.
• 무조건 2차원 배열이 필요하기에 필요 이상의 공간이 낭비된다.

인접 행렬은 언제 사용할까?

큰 표의 모습인 인접 행렬은 두 정점 사이에 관계 유무 확인에 용이하다.
가장 빠른 경로(shortest path)를 찾고자 할 때 사용!

인접 행렬 구현

// 이해를 위해 기존 배열의 인덱스를 정점으로! (0, 1, 2, ... --> 정점)

class GraphWithAdjacencyMatrix {
    constructor() {
        this.matrix = []; // {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) {
        return !!this.matrix[vertex] 
        //vertex는 index니까 그 안에 값이 있으면 존재하는 거겠지?!
    }

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

    hasEdge(from, to) {
    	return !!this.matrix[from][to]
    }

    removeEdge(from, to) {
	const currentLength = this.matrix.length - 1;
	if (from === undefined || to === undefined) {
		console.log("2개의 인자가 있어야 합니다.");
		return;
	}
        // 간선을 지울 수 없는 상황
	if (from > currentLength || to > currentLength || 
            from < 0 || to < 0) {
                return;
	}
      this.matrix[from][to] = 0
    }
}

인접리스트 Adjacency List

인접리스트란 그래프의 노드들을 리스트로 표현한 것
각 정점마다 하나의 리스트를 가지며, 이 리스트는 자신과 인접한 다른 정점을 담고 있다.
주로 정점의 리스트 배열을 만들어 관계를 설정해 줌으로써 구현합니다.

장점

• 정점들의 연결 정보를 탐색할 때 O(n)의 시간이면 가능
• 필요한 만큼의 공간만 사용해 공간의 낭비가 적다.

단점

• 특정 두 점의 연결 유무 확인이 인접행렬에 비해 오래 걸린다.
  배열보다 search 속도가 느리다.
• 구현이 비교적 어렵다.

❗️리스트의 순서는 중요하지 않다.
우선 순위를 다뤄야 한다면 더 적합한 자료구조(ex. queue, heap)를 사용해야 한다.

인접 리스트는 언제 사용할까?

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

인접 리스트 구현 (무방향)

class GraphWithAdjacencyList {
	constructor() {
		this.vertices = {}; // {vertices: {}}
	}

	addVertex(vertex) {
		// 정점 추가
		// 인자(정점)은 키, 빈 배열은 값으로 할당.
		// 이미 존재한다면 덮지않고! => 논리연산자 사용
		this.vertices[vertex] = this.vertices[vertex] || []; 
       		// {vertices: {vertex: [], ...}}
    
	}

	contains(vertex) {
		// 정점 너 있니..? -> vertex에 value가 있니?
		return !!this.vertices[vertex];
	}

	addEdge(fromVertex, toVertex) {
		// 간선 추가
		// fromVertex의 인접 리스트에 toVertex를 추가
		// toVertex의 인접 리스트에 fromVertex를 추가 -> 무방향이니까
		
    		// 넘겨받은 두 정점 모두 존재해야 간선을 추가할 수 있겠지!?
		if (!this.contains(fromVertex) || !this.contains(toVertex)) {
			return; // 하나라도 존재하지 않으면 손 놔
		}
        
	// 첫 정점 리스트에 두번째 정점이 없다면 추가해줘
		if (!this.hasEdge(fromVertex, toVertex)) {
      			this.vertices[fromVertex].push(toVertex);
		}	

		if (!this.hasEdge(toVertex, fromVertex)) {
     			 this.vertices[toVertex].push(fromVertex);
		}
	}

	hasEdge(fromVertex, toVertex) {
		// 정점(fromVertex)이 존재하지 않으면 false 반환
		if (!this.contains(fromVertex)) {
			return false;
		}
		// 존재해? 그럼 해당 정점 리스트에 toVertex가 포함되어있니?
		return !!this.vertices[fromVertex].includes(toVertex);
	}

	removeEdge(fromVertex, toVertex) {
		// 간선 삭제 (전제: 넘겨받은 두 정점이 모두 존재한다면)
		// fromVertex의 인접 리스트에 있는 toVertex 삭제
		// toVertex의 인접 리스트에 있는 fromVertex 삭제 -> 무방향이니까

		if (!this.contains(fromVertex) || !this.contains(toVertex)) {
			return;
		}
	// 첫 정점 리스트에 두번째 정점이 존재하면 삭제해줘
   	// 두번째 정점의 인덱스 위치를 찾아서 제거
		if (this.hasEdge(fromVertex, toVertex)) {
			const index = this.vertices[fromVertex].indexOf(toVertex);
			this.vertices[fromVertex].splice(index, 1);
		}
    		if (this.hasEdge(toVertex, fromVertex)) {
			const index = this.vertices[toVertex].indexOf(fromVertex);
			this.vertices[toVertex].splice(index, 1);
		}
	}

	removeVertex(vertex) {
		// 정점 삭제 (전제: 넘겨받은 정점이 존재한다면)
		// 해당 정점을 삭제함은 물론,
		// 타 정점들의 리스트를 모두 순회하며 해당 정점과 이어져 있는 간선을 제거
		if (this.contains(vertex)) {
      			while(this.vertices[vertex].length) {
        			this.removeEdge(this.vertices[vertex][0], vertex)
      			}
      		    delete this.vertices[vertex]
		}
	}
}

TIL Point

• splice()

array.splice(startIndex, deleteCount, item1, item2, ...)

해당 배열 요소를 삭제, 교체 혹은 새 요소를 추가하는 등 기존 배열 변경
제거한 요소를 담은 배열 반환.

• 논리연산자
  ! (ex = !a) Logical NOT operator
  !! (ex = !!b) Double NOT
  확실한 논리결과를 위해, Boolean으로 형 변환 (Type Conversion)을 위해 사용한다.
  가령, 0을 false로, 1을 true로 만들어줄 때 사용할 수 있다.
  && (ex = a && b)
  a가 false값이라면 a, 그 외에는 b 반환. (모두 true값일 때 가장 오른쪽 반환)
  따라서 불리언 값과 함께 사용한 경우, 둘 다 참일 때 true, 그 외 false 반환.
  || (ex = a || b)
  a가 true값이라면 a, 그 외에는 b 반환. (모두 true값일 때 가장 왼쪽 반환)
  따라서 불리언 값과 함께 사용한 경우, 둘 중 하나가 참일 때 true, 그 외 false 반환.

this.vertices[vertex] = this.vertices[vertex] || []; 
// 정점이 존재하면 그 것으로 할당하고 아니라면 빈배열을 할당하라