그래프(Graphs)

📌 Graphs

그래프는 노드나 노드들의 연결을 모은 것이다.
Nodes + Connections

• 기본적으로 모든 SNS에서 사용된다.
  사용자 추천 엔진등을 만들때 사용.
• 트리는 그래프의 일종이다.

📌 활용 분야

• 소셜 네트워킹
• 지도/위치
  
• 파일 시스템 최적화 (위키피디아 문서 구조)
  
• 등등

📌 용어

• vertex : 노드
• edge : 노드 사이의 연결(간선)
  
• Weighted / unweighted graph
  가중 그래프 : edge에 값이 부여되어 있음
  
  비가중 그래프 : edge에 값이 부여되어 있지 않음
  
• Directed/undirected graph
  무방향 그래프 : 방향이나 양극 음극이 없다(양방향 관계)
  Ex. 페이스북 : 한쪽만 팔로우 불가능, 양쪽으로만 가능.
  방향 그래프 : 방향을 나타내는 화살표가 있다.(단방향 관계)
  Ex. 인스타그램 : 한쪽 혹은 양쪽으로 팔로우 가능.
  

📌 vertex 사이의 관계를 나타내는 방법

1. 인접 행렬

: 1/0 또는 T/F로 노드 간의 연결 표시. 중첩 배열로 나타냄

2. 인접 리스트

: 특정 노드와 연결된 모든 노드들을 중첩 배열에 담음(노드가 숫자일 때는 배열을 사용하고 숫자가 아닐 때는 해시 테이블 사용)

📌 인접 행렬과 인접 리스트의 Big O

• Edge가 많지 않고 퍼져있는 그래프에 대해서는 인접 리스트가 인접 행렬보다 적은 공간을 차지한다.
  인접 행렬은 새로운 요소를 추가할 때마다 크기가 많이 늘어나기 때문.
• 모든 edge를 순회하는 것에서 인접 리스트가 더 빠르다.
• 특정 edge가 존재하는 것을 확인하는 것은 인접 행렬이 더 빠르다.
  인접 행렬은 특정 행,열만 확인하면 되는데, 인접 리스트는 배열을 쭉 순회해야 하기 때문.

⭐️ 실제 데이터들은 퍼져있는 경우가 많기 때문에 인접 행렬보다 인접 리스트를 더 많이 사용한다.

📌 인접 리스트 구현 (무방향 그래프로)

1. Vertex 추가 메소드

key가 존재하지 않을 경우 { key : [ ] } 세팅

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

2. Edge 추가 메소드

양방향으로 edge 추가

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

let g = new Graph();
g.addVertex("Dallas");
g.addVertex("Tokyo");
g.addVertex("Aspen");

3. Edge 제거 메소드

filter를 이용해 양방향으로 edge 제거

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

let g = new Graph();
g.addVertex("Dallas");
g.addVertex("Tokyo");
g.addVertex("Aspen");
g.addEdge("Dallas", "Tokyo");
g.addEdge("Dallas", "Aspen");

4. vertex 제거 메소드

마지막 요소를 계속 제거하면서 해당 노드의 edge 삭제.
키 전체를 제거할 때는 자바스크립트 메소드인 delete를 사용

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();
            this.removeEdge(vertex, adjacentVertex);
        }
        delete this.adjacencyList[vertex]
    }
}

let g = new Graph();
g.addVertex("Dallas");
g.addVertex("Tokyo");
g.addVertex("Aspen");
g.addVertex("Los Angeles");
g.addVertex("Hong Kong")
g.addEdge("Dallas", "Tokyo");
g.addEdge("Dallas", "Aspen");
g.addEdge("Hong Kong", "Tokyo");
g.addEdge("Hong Kong", "Dallas");
g.addEdge("Los Angeles", "Hong Kong");
g.addEdge("Los Angeles", "Aspen");