20 그래프

20.1 그래프 

  그래프란 유한하고 변할 수 있는 꼭지점(노드)의 집합으로 구성된 데이터 구조이다. 이 꼭지점들의 집합에 순서가 없는 경우에는 무방향 그래프, 순서가 있는 경우에는 유방향 그래프라고 한다. 즉, 그래프는 노드와 노드들의 연결을 모은 것이다. 그러므로 트리도 그래프의 일종이다. 다만 트리는 몇 가지 규칙이 추가되어 부모와 자식노드로 구성되고 시작점인 루트가 존재하는 것이다. 하지만 그래프에는 부모 노드라는 것이 없고, 시작점도 없다. 다 동일한 노드일 뿐이다. 또한 그래프는 트리나 연결 리스트 같은 수준의 패턴이 없다. 자유로운 형식의 노드가 있고 그 사이에 연결만 있을 뿐이다. 또한 트리는 한 노드에서 다른 노드로 가는 경로가 딱 한 가지만 존재해야 하지만 그래프는 수 개의 경로가 존재할 수 있다.

 

※용어 정리

1) 정점(Vertex) : 노드를 의미함

2) 간선(Edge) : 노드와 노드 사이의 연결을 의미함

3) 가중(Weighted) : 간선에 값을 부여한 것(연결 그 자체에 정보가 담겨있는 것이다.)

4) 비가중(Unweighted) : 간선에 값을 부여하지 않은 것

5) 방향(Directed) : 간선이 단방향으로 연결되어 있는 것

6) 무방향(Undirected) : 간선에 존재하는 방향성이 없음

 

20.2 그래프 정렬 : 인접 행렬 vs 인접 리스트

  그래프에 정보를 저장하고 연결하는 방법에는 여러가지가 있는데 대표적인 방법으로 인접 행렬(Adjacency Matrix)와 인접 리스트(Adjacency Lists)가 있다.

 

1) 인접 행렬(Adjacency Matrix)

  행렬이란 이차원 구조로 항상은 아니지만 보통 중첩 행렬로 표현한다. 기본적으로 행과 열에 맞춰서 정보를 저장하는 방법이다.

장점 : 특정 간선을 확인하는 경우에 빠르다.

단점 : 인접 리스트에 비해 공간을 더 많이 차지하고, 모든 간선을 순환해야 하는 경우 느리다.(데이터가 넓게 퍼져있는 경우 좋지 않다.)

 

2) 인접 리스트(Adjacency Lists)

  정점이 숫자로 이뤄진 경우에는 배열을 통해서 간선들을 저장할 수 있고, 특정 문자열이나 숫자가 아닌 경우 해시테이블 자료구조를 통해 간선들을 저장할 수 있다.(키와 값을 쌍으로 저장하는 데이터 구조)

장점 : 인접 행렬에 비해 공간을 적게 차지하고 모든 간선을 순환하는 경우 빠르다.

단점 : 특정 간선이 존재하는지 확인하는 것은 느리다.

//노드가 숫자로 이뤄진 경우 인덱스를 정점으로 표현하고 해당 정점의 간선들을 배열로 표시
[[1,5],[0,2],[1,3],[2,4],[3,5],[4,0]]

//노드가 숫자로 이뤄지지 않은 경우
{
    A: ["B", "F"],
    B: ["A", "C"],
    C: ["B", "D"],
    D: ["C", "E"],
    E: ["D", "F"],
    F: ["E", "A"]
}

20.3 정점 추가

  인수를 받아서 인접 리스트에 프로퍼티로 추가한다. 정점의 이름을 인접 리스트의 키로 만들고 값에 간선들을 넣어주면 된다.(값의 초기 설정은 빈 배열로 만들어주면 된다.)

// 인접 리스트를 활용
class Graph{
    constructor(){
        this.adjacencyList = {};
    }
    addVertex(vertex){
        if(!this.adjacencyList[vertex]) this.adjacencyList[vertex] = []; 
    }
}

20.4 간선 추가

  간선을 추가할 때는 두 개의 정점에 모두 명시하여야 한다.(무방향 그래프의 경우)

class Graph{
    constructor(){
        this.adjacencyList = {};
    }
    addVertex(vertex){
        if(!this.adjacencyList[vertex]) this.adjacencyList[vertex] = [];
    }
    
    addEdge(v1,v2){
        this.adjacencyList[v1].push(v2);
        this.adjacencyList[v2].push(v1);
	}
}

20.5 간선 제거

  정점을 제거하기 위해서는 정점 두 개를 인수로 받아야 하고, 하나의 정점이 가리키는 배열에 다른 하나의 정점을 제거한 배열을 재할당 해준다. 그리고 나머지 정점에도 동일한 방법으로 재할당 해준다.

class Graph{
    constructor(){
        this.adjacencyList = {};
    }
    addVertex(vertex){
        if(!this.adjacencyList[vertex]) this.adjacencyList[vertex] = [];
    }
    addEdge(v1,v2){
        this.adjacencyList[v1].push(v2);
        this.adjacencyList[v2].push(v1);
    }
   
    removeEdge(vertex1,vertex2){
        this.adjacencyList[vertex1] = this.adjacencyList[vertex1].filter(
            v => v !== vertex2
        );
        this.adjacencyList[vertex2] = this.adjacencyList[vertex2].filter(
            v => v !== vertex1
        );
    }
}

//filter() 콜백 함수의 조건에 맞는 요소들만 취하여 새로운 배열을 만들어 반환해줌

20.6 정점 제거

  정점을 제거하기 위해서는 단순히 정점만을 제거해서는 안되고 해당 정점과 연결되어 있는 다른 정점들의 배열 내에서도 지워주어야 한다. 그러므로 루프를 돌며 먼저 간선 제거 함수를 이용하여 삭제하려는 정점이 가지고 있는 간선들을 먼저 다 제거해주고 정점을 마지막에 제거해야 한다.

class Graph{
    constructor(){
        this.adjacencyList = {};
    }
    addVertex(vertex){
        if(!this.adjacencyList[vertex]) this.adjacencyList[vertex] = [];
    }
    addEdge(v1,v2){
        this.adjacencyList[v1].push(v2);
        this.adjacencyList[v2].push(v1);
    }
   
    removeEdge(vertex1,vertex2){
        this.adjacencyList[vertex1] = this.adjacencyList[vertex1].filter(
            v => v !== vertex2
        );
        this.adjacencyList[vertex2] = this.adjacencyList[vertex2].filter(
            v => v !== vertex1
        ); // 필터메서드는 원본 배열 변경 안됨 복사해서 새롭게 배열을 만들어냄
    }

    removeVertex(vertex){
        while(this.adjacencyList[vertex].length){
            const adjacentVertex = this.adjacencyList[vertex].pop(); 
            console.log(adjacentVertex);
            console.log(this.adjacencyList[vertex]);
            //원본 배열 변경됨, pop메서드는 배열의 맨 뒤 요소를 지우고 지운 요소를 반환함
            this.removeEdge(vertex, adjacentVertex);
        }
        delete this.adjacencyList[vertex]
    }
}