[알고리즘👽] 20. 그래프

해당 포스팅은 알고리즘 그래프에 대해 다룹니다. 그래프의 용어, 정렬, 행렬, 리스트, 점과 선에 대한 내용입니다.

그래프 소개

목표

• 그래프가 무엇인지 설명한다.
• 여러 종류의 그래프를 비교하고 사용 예시를 확인한다.
• 인접 리스트를 활용해서 그래프를 코딩한다.
• BFS와 DFS를 사용해 그래프를 순회한다.
• 빅오애 대해 다룬다.

그래프란?

그래프는 유한하고 변할 수 있는 꼭지점이나 노드나 점들의 집합으로 구성된 데이터 구조이다. 이 꼭지점들의 집합에 순서가 없는 경우에는 무방향 그래프, 순서가 있는 경우에는 유방향 그래프라고 합니다.

그래프는 노드나 노드들의 연결을 모은 것입니다 (Node + Connections)

그래프 이용

그래프 사용처

• Social Network
• Location / Mapping
• Routing Algorithms
• Routing Algorithms
• Visual Hierarchy
• File System Optimizations
• EVERYWHERE!

그래프 유형

용어 설명

• 정점(Vertex) - 노드
• 간선(Edge) - 노드 사이의 연결
• 가중/비가중(Weighted/Unweighted)
• 방향/무방향(Directed/Undirected)

무방향 그래프

방향 그래프

비가중 그래프

가중 그래프

그래프 정렬

인접 행렬(Adjacency Matrix)

실제로 그래프를 저장할 때 중요한 정보는 노드, 즉 실제 정점들과 연결을 저장하는 방식이다.

0과 1을 저장하는 것이 가장 흔한 방식이다. true false나 예 아니오를 사용할 수도 있다. 하지만 모두 행렬에 저장하는 것은 저장한 것이 간선이라는 점에서 똑같다.

인접 리스트(Adjacency List)

만약 1과 5사이에 간선이 있는지 알고 싶다면 인덱스 1로 가서 5가 있는지 확인한다 이곳에 없다면 인덱스 5에가서 1이 있는지 확인한다. 둘 다 없는 경우 연결되있지 않다.

만약 인덱스가 아닌 문자로 됐다면 해시 테이블을 사용하면 된다.

인접 행렬 vs. 리스트의 빅오 (BIG O)

|V| - number of verices

|E| - number of edges

Operation	인접 리스트	인접 행렬
Add Vertex	O(1)	O(
Add Edge	O(1)	O(1)
Remove Vertex	O(	V
Remove Edge	O(	E
Query	O(	V
Storage	O(	V
- 인접 리스트
- 간섭이 많지 않고 퍼져있는 그래프 경우 인접 행렬보다 더 적은 공간 차지
- 특전 간선이 존재하는 것을 확인하려면 느리다
- 모든 간선을 순환하는 것은 빠르지만 특정 간선이 있는지 여부를 확인하는 것은 더 느리다.
- 인접 행렬
- 간선을 확인하고 싶으면 모든 간선에 대해 루프를 돌아서 찾아야 한다.(존재하지 않는 빈공간까지 저장)
- 모든 간선을 순회하는 것이 더 느리다.

인접리스트가 대부분 유용하다. 더 적은 공간을 차지하고 간선이 많지 않아서. 행렬을 사용할 수도 있지만 느리껄

점(vertex) 추가

소개

class Graph {
    constructor() {
        this.adjacencyList = {};
    }
}

• vertex의 이름을 받는 addVertex라는 메서드를 작성한다.
• 이 메소드는 정점의 이름을 인접 리스트의 키로 입력하게 된다. 값은 빈 배열로 하면 된다.
• g.addVertex(”Tokyo”) → { “Tokyo” : [ ]}

솔루션

class Graph {
    constructor() {
        this.adjacencyList = {};
    }
    addVertex(vertex){
        if(!this.adjacencyList[vertex]) this.adjacencyList[vertex] = [];
    }
}

선(edge) 추가

소개

• 이 함수는 필수적으로 두 개의 정점을 명시해야한다.
• vertex1의 키를 찾아서 vertx2를 그 배열에 넣어줘야한다.
• vertex2의 키를 찾아서 vertex1를 그 배열에 넣어줘야한다.

솔루션

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);
    }
}

선(edge) 제거

소개

• 두 개의 인수를 제공한다.
• 정점 1에 있는 키를 제거하고 정점 2의 있는 키를 제거한다.

솔루션

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);
    }
    remove(v1,v2){
        this.adjacencyList[vertex1] = this.adjacencyList[vertex1].filter(
            v => v !== vertex2
        );
        this.adjacencyList[vertex2] = this.adjacencyList[vertex2].filter(
            v => v !== vertex1
        );
    }
}

점(vertex) 제거

소개

• 한 개의 인수를 받는다
• adjacencyList에 다른 정점이 있다면 해당 정점인지 확인하기 위해 모두 루프를 돌아야한다.
• 루프 안에 미리 정의한 removeEdge 함수 사용, 해당 정점에 있는 모든 간선에 대해 모두 removeEdge를 호출해야 한다.
• 마지막으로 adjacenyList에서 키를 삭제한다.

솔루션

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);
    }
    remove(v1,v2){
        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();
            this.removeEdge(vertex, adjacentVertex);
        } 
    }
}