학습(알고리즘)

1.인접리스트는 행렬보다 더 적은 공간을 차지하며 모든 간선 순환은 더 빠르지만 특정 간선 존재여부를 확인하는 것은 행렬보다 느리다.

2.그래프의 정점, 간선 추가 및 제거는 다음과 같이 구현할 수 있다.

class Graph{ // 그래프 생성
    constructor(){
        this.list = {};
    }
    addVertex(vertex){
        if(!this.list[vertex]) this.list[vertex] = []; // 정점이 없는 경우 정점에 빈 배열 추가
    }
    addEdge(v1,v2){ //간선이 추가될 경우 양쪽에 각자 추가
        this.list[v1].push(v2);
        this.list[v2].push(v1);
    }
    removeEdge(vertex1,vertex2){ // 간선을 제거할 경우 양쪽에서 filter로 해당 간선 제거
        this.list[vertex1] = this.list[vertex1].filter(
            el => el !== vertex2
        );
        this.list[vertex2] = this.list[vertex2].filter(
            el => el !== vertex1
        );
    }
    removeVertex(vertex){ //정점을 제거할 경우 
        while(this.list[vertex].length){ // 정점 내부가 비어있는지 확인(0이면 중단)
            const adjacentVertex = this.list[vertex].pop(); //정점에 연결된 다른 정점들 조회 (pop으로 하나씩 뽑아서 아래에서 제거)
            this.removeEdge(vertex, adjacentVertex); //위에서 찾은 점점에서 제거할 정점으로 연결된 간선 제거
        }
        delete this.list[vertex] //이 정점으로 연결해오는 간선들을 모두 제거했으면 현재 정점 제거
    }
}