algorithm/자료구조

그래프

yongfront 2024. 3. 20. 14:14
반응형
SMALL

그래프는 노드(정점)들과 그 노드들을 연결하는 간선(엣지)들의 집합으로 구성된 자료 구조입니다. 그래프는 네트워크 모델링, 경로 찾기, 소셜 네트워크 분석 등 다양한 분야에서 활용됩니다. 그래프는 크게 두 가지로 분류됩니다:

  1. 무방향 그래프(Undirected Graph): 간선에 방향이 없어, 두 정점이 서로 연결되어 있는 구조입니다.
  2. 방향 그래프(Directed Graph): 간선에 방향이 있어, 한 정점에서 다른 정점으로의 일방향 연결을 나타냅니다.

그래프는 또한 가중치가 있는 그래프와 가중치가 없는 그래프로 나눌 수 있으며, 가중치가 있는 그래프에서는 각 간선에 비용 또는 가중치가 할당됩니다.

JavaScript에서 그래프 구현하기

JavaScript로 그래프를 구현할 수 있는 여러 방법이 있습니다. 아래 예제는 가장 기본적인 형태의 무방향 그래프를 인접 리스트(Adjacency List) 방식으로 구현한 것입니다. 인접 리스트는 각 정점에 인접한 정점 목록을 배열이나 리스트로 표현하는 방식입니다.

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

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

    // 무방향 간선 추가
    addEdge(vertex1, vertex2) {
        this.adjacencyList[vertex1].push(vertex2);
        this.adjacencyList[vertex2].push(vertex1);
    }

    // 무방향 간선 제거
    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];
    }
}

이 구현에서는 그래프를 생성하고, 정점을 추가하며, 두 정점 사이에 간선을 추가하고 제거하는 기본적인 메소드들을 제공합니다. 또한, 특정 정점을 그래프에서 제거할 때, 해당 정점과 연결된 모든 간선도 함께 제거합니다.

그래프 사용 예제

다음은 위에서 구현한 Graph 클래스를 사용하는 간단한 예제입니다.

const graph = new Graph();
graph.addVertex("Tokyo");
graph.addVertex("Dallas");
graph.addVertex("Aspen");

graph.addEdge("Tokyo", "Dallas");
graph.addEdge("Dallas", "Aspen");

console.log(graph);

이 예제에서는 세 개의 도시를 정점으로 하는 그래프를 생성하고, 도시들 사이에 간선을 추가하여 연결합니다. 이렇게 생성된 그래프는 여행 경로, 네트워크 연결 등 다양한 문제를 모델링하는 데 사용될 수 있습니다.

그래프는 매우 유연한 자료 구조이며, 복잡한 문제를 해결하기 위한 다양한 알고리즘(예: 깊이 우선 탐색, 너비 우선 탐색, 최초 경로 찾기)에 기반을 제공합니다. 이어서 그래프와 관련된 몇 가지 중요한 알고리즘과 개념들에 대해 설명하겠습니다.

깊이 우선 탐색 (Depth-First Search, DFS)

깊이 우선 탐색(DFS)는 그래프의 모든 정점을 방문하는 알고리즘 중 하나로, 가능한 한 깊은 곳을 우선적으로 탐색하는 방식입니다. DFS는 스택(명시적이거나 재귀 호출을 통한)을 사용하여 구현할 수 있으며, 미로 탐색이나 퍼즐 게임 같은 문제를 해결하는 데 유용합니다.

너비 우선 탐색 (Breadth-First Search, BFS)

너비 우선 탐색(BFS)은 그래프의 모든 정점을 가까운 순서대로 방문하는 알고리즘입니다. BFS는 큐를 사용하여 구현되며, 최단 경로 문제나 소셜 네트워크에서 두 사람 간의 최소 연결 단계를 찾는 데 쓰입니다.

최단 경로 알고리즘

그래프에서 두 정점 사이의 최단 경로를 찾는 문제는 여러 분야에서 중요한 응용을 가지고 있습니다. 대표적인 최단 경로 알고리즘으로는 다익스트라 알고리즘(Dijkstra's algorithm)과 벨만-포드 알고리즘(Bellman-Ford algorithm)이 있습니다. 다익스트라 알고리즘은 가중치가 모두 양수인 그래프에서 사용할 수 있으며, 벨만-포드 알고리즘은 가중치가 음수인 간선이 있어도 사용할 수 있습니다.

그래프 구현 확장: 깊이 우선 탐색 예제

앞서 정의한 Graph 클래스를 확장하여 깊이 우선 탐색을 구현해 보겠습니다.

class Graph {
    // 이전 구현 유지

    // 깊이 우선 탐색
    dfs(start) {
        const result = [];
        const visited = {};
        const adjacencyList = this.adjacencyList;

        (function dfsHelper(vertex) {
            if (!vertex) return null;
            visited[vertex] = true;
            result.push(vertex);
            adjacencyList[vertex].forEach(neighbor => {
                if (!visited[neighbor]) {
                    return dfsHelper(neighbor);
                }
            });
        })(start);

        return result;
    }
}

// 사용 예제
const graph = new Graph();
graph.addVertex("A");
graph.addVertex("B");
graph.addVertex("C");
graph.addVertex("D");
graph.addVertex("E");
graph.addVertex("F");

graph.addEdge("A", "B");
graph.addEdge("A", "C");
graph.addEdge("B", "D");
graph.addEdge("C", "E");
graph.addEdge("D", "E");
graph.addEdge("D", "F");
graph.addEdge("E", "F");

console.log(graph.dfs("A"));

이 코드에서 dfs 메소드는 시작 정점을 받아, 해당 정점으로부터 깊이 우선 탐색을 수행합니다. 탐색된 정점들은 result 배열에 저장되며, 최종적으로 이 배열이 반환됩니다.

그래프는 데이터의 연결 관계를 모델링하고 분석하는 데 강력한 도구입니다. JavaScript와 같은 프로그래밍 언어를 사용하여 구현하면, 복잡한 네트워크를 시각화하고 탐색하는 다양한 알고리즘을 실험해 볼 수 있습니다.

728x90
반응형
LIST