[자료구조] 211103 인접행렬(adjacency matrix)구현 이해하기

📌 adjacency matrix

자료구조는 다시 백지에서 풀려고 하니 하얘져서 다시 처음부터 진행해야겠다는 생각이 들었다. 그래서 다시 한번 시작해보자라는 생각이 들었다.

Vertex : 하나의 정점
Edge : 정점과 정점을 잇는 하나의 선

여기서는 메서드를 직접 하나씩 작성해보고자 한다.

• addVertex(): 그래프에 버텍스를 추가해야 합니다.
• contains(vertex): 그래프에 해당 버텍스가 존재하는지 여부를 Boolean으로 반환해야 합니다.
• addEdge(from, to): fromVertex와 toVertex 사이의 간선을 추가합니다.
• hasEdge(from, to): fromVertex와 toVertex 사이의 간선이 존재하는지 여부를 Boolean으로 반환해야 합니다.
• removeEdge(from, to): fromVertex와 toVertex 사이의 간선을 삭제해야 합니다.

1) addVertex()

우선 버텍스(정점)를 추가하기 전에 빈 배열을 생성한다. constructor()를 이용해서.

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

this.matrix에 정점 0,1,2가 있다고 가정해볼 때 여기에 정점을 추가해본다고 생각해보자 그럼 this.matrix의 현재 this.matrix의 길이를 가지고 활용할 수 있다.

let currentLength = this.matix.length

동시에 여기에서 각각의 정점에 접근하기 위해선 반복문을 통해 각각의 값에 접근이 가능하다.

for(let i=0; i < currentLength; i++) {
  this.matrix[i].push(0) //처음엔 초기값인 0을 삽입한다
}
this.matrix.push(new Array(currentLength + 1).fill(0))

여기까지 작성하고 나면 this.matrix = [ [0,0,0],[0,0,0],[0,0,0] ] 요런 모양이다. 배열 내에 배열이 생성이 된것이다. (배열내 배열의 길이는 예시일 뿐이다)

2) contains()

해당 메서드를 통해 this.matrix에 해당 정점이 있는지 확인해야 한다.
true인지 false인지 확인하는 것이니까 !!를 이용한다.

contains(vertex) { //vertex라는 정점을 인자로 받을때
  return !!this.matrix[vertex]//vertex가 있는가 있으면 true, 없으면 false 
}

3) addEdge( , )

from이라는 버텍스 그리고 to라는 버텍스를 인자로 받는다는 가정. from 과 to 에 값이 없을 때는 undefined 일것이다.

☑ from과 to가 undefined일 땐 "2개의 인자가 있어야 합니다"를 출력
☑ from과 to가 this.matrix의 길이를 뛰어넘는다면 "범위가 매트리스 밖"출력
☑ 이 두가지 경우에 속하지 않는다면, 간선을 추가해준다.

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+1 < 0 || to+1 < 0) {
			console.log("범위가 매트릭스 밖에 있습니다.");
			return;
		}
    return this.matrix[from][to] = 1 //간선추가는 1 
	}

4) hasEdge( , )

from 이랑 to 라는 두 버텍스 사이에 간선이 있는지 확인. (this.matrix라는 배열의 from번째 배열의 to번째 확인.

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

5) hasEdge( , )

from 이랑 to 라는 두 버텍스 사이에 간선이 있는지 확인. (this.matrix라는 배열의 from번째 배열의 to번째 확인. 있으면 true 없으면 false.

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

6) removeEdge( , )

addEdge와 수도코드가 거의 똑같으나 끝 부분만 다르다.

☑ from과 to가 undefined일 땐 "2개의 인자가 있어야 합니다"를 출력
☑ from과 to가 this.matrix의 길이를 뛰어넘는다면 "범위가 매트리스 밖"출력
☑ 이 두가지 경우에 속하지 않는다면, 간선을 지워야한다.

return this.matrix[from][to] = 0 

---