그래프(Graph)

그래프 Graph 는 정점 Vertex 과 간선 Edge 의 집합으로 이루어진 자료구조다.
즉, 여러 개의 점이 선으로 연결된 형태를 말하며, 사물 간의 관계를 표현할 때 매우 유용한 구조다.

---

그래프의 기본 개념

그래프는 정점 Vertex 과 간선 Edge 로 구성된다.

• 정점 Vertex 는 데이터나 객체를 의미한다.
• 간선 Edge 는 두 정점을 연결하는 관계를 의미한다.

예를 들어, 사람을 정점으로 두고 친구 관계를 간선으로 표현하면 소셜 네트워크를 그래프로 나타낼 수 있다.

---

그래프의 종류

그래프는 연결 방식과 간선의 방향 여부에 따라 여러 형태로 나뉜다.

1. 무방향 그래프 Undirected Graph
   간선에 방향이 없다. A와 B가 연결되어 있으면 B와 A도 연결되어 있다.
2. 방향 그래프 Directed Graph
   간선에 방향이 있다. A에서 B로 가는 간선이 있다고 해서 B에서 A로 갈 수 있는 것은 아니다.
3. 가중치 그래프 Weighted Graph
   간선에 비용이나 거리 등 값을 부여한 그래프다. 예를 들어 지도에서 각 도시 간의 거리 정보를 나타낼 때 사용한다.
4. 부분 그래프 Subgraph
   원래 그래프에서 일부 정점이나 간선을 선택하여 만든 그래프다.

---

그래프의 표현 방법

그래프는 인접 행렬 Adjacency Matrix 과 인접 리스트 Adjacency List 두 가지 방식으로 표현할 수 있다.

인접 행렬

정점을 행과 열로 나열하고, 연결되어 있으면 1, 아니면 0으로 표시하는 방식이다.
메모리를 많이 차지하지만 구현이 간단하다.

#include <iostream>
using namespace std;

int main() {
    int n = 4; // 정점 개수
    int graph[4][4] = {0};

    // 간선 추가
    graph[0][1] = 1;
    graph[1][2] = 1;
    graph[2][3] = 1;
    graph[3][0] = 1;

    cout << "인접 행렬 방식 그래프" << endl;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++)
            cout << graph[i][j] << " ";
        cout << endl;
    }
}

---

인접 리스트

각 정점에 연결된 정점들을 리스트로 저장하는 방식이다.
메모리 효율이 좋고, 많은 그래프 알고리즘에서 널리 사용된다.

 

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n = 4;
    vector<int> graph[4];

    // 간선 추가
    graph[0].push_back(1);
    graph[1].push_back(2);
    graph[2].push_back(3);
    graph[3].push_back(0);

    cout << "인접 리스트 방식 그래프" << endl;
    for (int i = 0; i < n; i++) {
        cout << i << " -> ";
        for (int v : graph[i])
            cout << v << " ";
        cout << endl;
    }
}

---

그래프 탐색 알고리즘

그래프의 핵심은 탐색이다.
대표적인 탐색 알고리즘에는 깊이 우선 탐색 DFS 과 너비 우선 탐색 BFS 이 있다.

깊이 우선 탐색 DFS

한 방향으로 끝까지 탐색한 뒤, 더 이상 진행할 수 없을 때 되돌아오는 방식이다.
재귀 호출로 구현하기 쉽다.

 

#include <iostream>
#include <vector>
using namespace std;

void dfs(int node, vector<int> graph[], vector<bool> &visited) {
    visited[node] = true;
    cout << node << " ";
    for (int next : graph[node]) {
        if (!visited[next])
            dfs(next, graph, visited);
    }
}

int main() {
    int n = 4;
    vector<int> graph[4];
    graph[0] = {1, 2};
    graph[1] = {2};
    graph[2] = {0, 3};
    graph[3] = {};

    vector<bool> visited(n, false);
    cout << "DFS 탐색 결과: ";
    dfs(0, graph, visited);
}

너비 우선 탐색 BFS

가까운 정점부터 차례로 탐색하는 방식이다.
큐 Queue 자료구조를 이용해 구현한다.

 

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

void bfs(int start, vector<int> graph[], int n) {
    vector<bool> visited(n, false);
    queue<int> q;

    visited[start] = true;
    q.push(start);

    while (!q.empty()) {
        int node = q.front();
        q.pop();
        cout << node << " ";

        for (int next : graph[node]) {
            if (!visited[next]) {
                visited[next] = true;
                q.push(next);
            }
        }
    }
}

int main() {
    int n = 4;
    vector<int> graph[4];
    graph[0] = {1, 2};
    graph[1] = {2};
    graph[2] = {0, 3};
    graph[3] = {};

    cout << "BFS 탐색 결과: ";
    bfs(0, graph, n);
}

---

정리

그래프는 객체 간의 관계를 표현하는 자료구조로, 네트워크, 길찾기, 소셜미디어, 회로 설계 등 다양한 분야에서 활용된다.
그래프 탐색 알고리즘을 이해하는 것은 효율적인 문제 해결의 핵심이다.
DFS와 BFS를 기반으로 한 최단 경로 탐색 다익스트라 알고리즘, 최소 신장 트리 프림 크루스칼 알고리즘 등은 모두 그래프 개념을 바탕으로 발전한 알고리즘이다.