그래프

728x90

그래프(Graphs)

그래프는 유한하고 변할 수 있는 꼭지점이나 노드나 점들의 집합으로 구성된 데이터 구조다

이 점들의 집합이 순서가 있는 경우는 유방향 그래프/ 없으면 무방향 그래프

노드 + 연결(connections) => 그래프

실생활 예시

- SNS

- 위치 / 지도

- 추천 시스템

용어

Vertex - 노드(정점)

Edge - 간선(노드사이 연결)

Weight / Unweighted - 간선에 값을 부여하면 가중 그래프 / 간선에 값이 없으면 비가중

https://ko.m.wikipedia.org/wiki/%ED%8C%8C%EC%9D%BC:Weighted_Graph.svg

Directed / Undirected -> Instagram에서 팔로우 여부에 따라 게시물을 볼 수 있는지 없는지 (방향)

Facebook에서는 모든 사람의 게시물을 볼 수 있음 (무방향)

\https://sites.google.com/a/cs.christuniversity.in/discrete-mathematics-lectures/graphs/directed-and-undirected-graph

인접 행렬(adjacency matrix)

http://www.btechsmartclass.com/data_structures/graph-representations.html

간선이 연결되어 있어 공유하는 부분은 1 아닌 부분은 0으로 표현

인접 리스트(adjacency list)

https://www.oreilly.com/library/view/c-data-structures/9781788833738/538c7cd0-0d98-49d9-8373-2c47583da90c.xhtml

BIG O

https://medium.com/@trejonstallsworth/graphs-in-javascript-831db916de10

인접 행렬 vs 인접 리스트

- 간선이 많지 않고 퍼져있는 그래프에서는 인접 리스트가 더 적은 공간을 차지한다.

(위 그래프의 Storage : 행렬은 하나의 노드가 추가되면 표 가로,세로에 노드가 각각 하나씩 추가되 새로운 라인을 만들어내기에 V^2)

- 모든 간선을 순회하는 것은 인접 리스트가 더 빠르다

- 특정 간선을 확인하는 것은 인접 행렬이 더 빠르다 (위 표에 Query 부분)

간단한 구현

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();
vertex 추가후 edge로 이어주면 된다

-> 그래프 순회로 이어짐