[자료구조] 그래프(Graph) - javascript

들어가기 전에...

해당 글은 유데미 JavaScript 알고리즘 & 자료구조 마스터클래스 강의를 바탕으로 더 효율적이고 간결하게 수정된 코드이다.

✅ 그래프란?

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

💡 구성 요소

• 정점(vertax): 각 노드
• 간선(edge): 정점을 잇는 선

💡 그래프의 종류

• 트리: 두 개의 정점이 하나의 경로로 이어져 있는 그래프
• 유방향/무방향 그래프: 간선의 방향 유무로 구별되는 그래프
• 가중/비가중 그래프: 간선에 값 부여 여부로 구별되는 그래프
• 밀집 그래프: 노드 ↓, 간선 ↑ / 희소 그래프: 노드 ↑, 간선 ↓

ex) 구글 맵을 만든다면 => 가중 & 유방향 그래프
(가중 - 위치 사이에 거리가 값으로 부여 / 유방향 - 일방통행, 쌍방통행 거리로 나눠짐)

📌 구현 방법 - 인접 리스트 vs 인접 행렬

인접 행렬

인접 리스트

출처: 제로초 블로그

💡 시간복잡도

• V : 정점 개수
• E : 간선 개수

	인접 리스트	인접 행렬
정점 추가	O(1)	O(V^2)
간선 추가	O(1)	O(1)
정점 삭제	O(V+E)	O(V^2)
간선 삭제	O(E)	O(1)
검색	O(V+E)	O(1)
저장	O(V+E)	O(V^2)

💡 장단점

	인접 리스트	인접 행렬
메모리 차지 (in 희소 그래프)	비교적 작음 (실제 연결된 간선만 저장)	비교적 큼 (간선이 아니어도 0으로 저장됨)
간선 순회	비교적 빠름	비교적 느림
특정 간선 검색 (연결 확인)	비교적 느림	비교적 빠름 (행렬의 값만 확인하면 됨)

📌 구현 (인접 리스트)

메모리를 덜 차지해서 효율적인 인접 리스트를 이용함

=> 인접 리스트는 해시 테이블로 구현

// 완성된 그래프 예시
const graph = {
    "A": ["B", "C"],
    "B": ["A", "D"],
    "C": ["A", "E"],
    "D": ["B", "E", "F"],
    "E": ["C", "D", "F"],
    "F": ["D", "E"]
}

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

    // 정점 추가
    addVertax(vertex) {
        if(!this.adjacencyList[vertex]) this.adjacencyList[vertex] = [];
    }

    // 간선 추가
    addEdge(v1, v2) {
        this.adjacencyList[v1].push(v2)
        this.adjacencyList[v2].push(v1)
    }
    
    // (가중그래프라면) 간선 추가
    addEdge(v1, v2, weight) {
       this.adjacencyList[v1].push({node: v2, weight});
       this.adjacencyList[v2].push({node: v1, weight});
    }

    // 간선 제거
    removeEdge(v1, v2) {
        this.adjacencyList[v1] = this.adjacencyList[v1].filter(v => v !== v2);
        this.adjacencyList[v2] = this.adjacencyList[v2].filter(v => v !== v1);
    }

    // 정점 제거
    removeVertex(vertex) {
        // 정점과 연결된 곳의 리스트에서 정점 삭제
        this.adjacencyList[vertex].forEach(connectedV => {
            this.adjacencyList[connectedV] 
                = this.adjacencyList[connectedV].filter(v => v !== vertex)
        })

        this.adjacencyList[vertex] = null; // 정점의 리스트 비움
        delete this.adjacencyList[vertex]; // 완전히 삭제
    }

}

📌 순회

BFS (넓이 우선 순회)

function bfs(graph, startNode) {
    let result = [];
    let queue = [startNode];
    let visited = {[startNode]: true};
    let curVertex;

    while(queue.length) {
        curVertex = queue.shift();
        result.push(curVertex);
        graph[curVertex].forEach(neighbor => {
            if(!visited[neighbor]) {
                visited[neighbor] = true;
                queue.push(neighbor);
            }
        })
    }

    return result;
}

DFS (깊이 우선 순회)

// 1️⃣재귀적 용법
function depthFirstSearch(graph, startNode) {
    let result = [];
    let visited = {}; // 방문시 "A": true 같이 기록

    (function dfs(vertex) {
        if(!vertex) return; // 노드값이 올바르지 않을시 처리
        result.push(vertex); // 결과값에 추가
        visited[vertex] = true; // 방문 처리
        graph[vertex].forEach(neighbor => { // 방문하지 않은 이웃 순회
            if(!visited[neighbor]) dfs(neighbor);
        })
    })(startNode);

    return result;
}

// 2️⃣반복적 용법
function dfs(graph, startNode) {
    let result = [];
    let stack = [startNode];
    let visited = {[startNode]: true};
    let curVertex;

    while(stack.length) {
        curVertex = stack.pop();
        result.push(curVertex);
        graph[curVertex].forEach(neighbor => {
                if(!visited[neighbor]) {
                    visited[neighbor] = true; // 여기서 방문처리 했으니 이후 스택에 추가x
                    stack.push(neighbor);
            }
        })
    }

    return result;
}