[알고리즘] 그래프란?

그래프란?

그래프는 여러 개의 점(정점)과 선(간선)으로 이루어진 자료구조이다. 현실 세계에서 사람과 사람의 관계, 도로 지도, 지하철 노선도 등을 그래프로 표현할 수 있다.

간단히 말하면, “노드끼리 연결된 관계를 표현하는 자료구조”이다.

그래프 구성 요소

정점(Vertex) : 데이터를 표현하는 점. 노드(Node)라고도 부른다.
간선(Edge) : 정점과 정점을 연결하는 선. 관계 또는 경로.
방향 그래프(Directed Graph) : 간선에 방향이 있는 그래프. A → B처럼 단방향.
무방향 그래프(Undirected Graph) : 간선에 방향이 없는 그래프. A와 B가 서로 연결됨.
가중치 그래프(Weighted Graph) : 간선마다 비용, 거리 등이 있는 그래프. 예: 지하철 노선 거리.

그래프를 표현하는 방법

방법	설명	사용 경우
인접 행렬(Adjacency Matrix)	2차원 배열로 노드 연결 여부를 표시 (1 또는 0).	연결 확인은 빠르지만 메모리 사용 많음.
인접 리스트(Adjacency List)	배열 안에 연결된 노드들을 리스트로 저장.	메모리 효율적. 보통 실무에서 많이 사용.

그래프에서 자주 사용하는 용어

정점(Vertex) : 데이터가 저장된 점
간선(Edge) : 정점끼리 연결된 선
인접(Adjacent) : 서로 연결된 상태
경로(Path) : 한 정점에서 다른 정점으로 이동하는 길
사이클(Cycle) : 시작한 정점으로 다시 돌아오는 경로
연결 요소(Connected Component) : 서로 연결된 정점들의 묶음
트리(Tree) : 사이클이 없는 그래프
탐색(Traversal) : 그래프의 노드를 한 번씩 방문하는 과정

DFS란?

DFS(Depth-First Search, 깊이 우선 탐색)는 가능한 한 깊게 들어가서 탐색하는 방식이다. 하나의 경로를 끝까지 따라가면서 탐색한 뒤, 더 이상 갈 곳이 없으면 되돌아와서 다른 경로를 탐색한다.

-> 간단히 말하면, “한 경로를 끝까지 파고드는 방식”

1) 특징

한 경로를 끝까지 탐색
모든 경로 확인, 경우의 수 찾기에 유리
백트래킹, 경로 찾기 문제에서 자주 사용됨
보통 재귀 함수 또는 스택으로 구현

2) DFS 예시 코드 (JavaScript)

JavaScript

// DFS 재귀 함수

function dfs(node) {
    visited[node] = true;

    graph[node].forEach(next => {
        if (!visited[next]) {
            dfs(next);
        }
    });
}

BFS란?

BFS(Breadth-First Search, 너비 우선 탐색)는 가까운 노드부터 넓게 탐색하는 방식이다. 시작 노드에서 인접한 노드를 모두 탐색한 후, 그다음 단계의 노드를 탐색한다.

-> 간단히 말하면, “가까운 노드부터 하나씩 넓게 퍼지는 방식”

1) 특징

최단 경로 문제에서 많이 사용됨
모든 노드를 골고루 탐색
큐(Queue)를 사용하여 구현

2) BFS 예시 코드 (JavaScript)

JavaScript

// BFS 함수

function bfs(start) {

const queue = [start];

visited[start] = true;

while (queue.length) {
    const current = queue.shift();

    graph[current].forEach(next => {
        if (!visited[next]) {
            visited[next] = true;
            queue.push(next);
        }
    });
}
}

DFS와 BFS의 차이

DFS는 한 경로를 끝까지 들어가면서 탐색하는 방식이다.
BFS는 가까운 노드부터 하나씩 넓게 탐색하는 방식이다.

-> 경로의 깊이를 따라가야 할 때는 DFS를 사용하고, 최단 경로를 찾거나 골고루 탐색해야 할 때는 BFS를 사용하면 된다.
-> 그래프 탐색을 이해하고 있으면 경로 찾기, 최단 거리, 네트워크 구성 등 다양한 문제를 효율적으로 해결할 수 있다.

최근 글