13. 그래프

그래프

빠른 설명

그래프는 정점(vertex)과 간선(edge)으로 이루어진 자료구조다. 사람 관계, 길, 이동 가능 상태, 선후 관계를 표현할 때 사용한다.

표현 방법

• 인접 리스트: 연결된 정점만 저장한다. 보통 가장 많이 쓴다.
• 인접 행렬: $N\times N$ 배열로 연결 여부를 저장한다. 정점 수가 작을 때 편하다.

시간복잡도 감각

• 인접 리스트 전체 순회: $O(V+E)$
• 인접 행렬 전체 확인: $O(V^2)$

참고자료

• Wikipedia - Graph
• CP-Algorithms - Graph algorithms
• GeeksforGeeks - Graph Data Structure
• 나무위키 - 그래프

C++ 코드

#include <algorithm>
#include <deque>
#include <functional>
#include <iostream>
#include <queue>
#include <stack>
#include <string>
#include <utility>
#include <vector>
using namespace std;
 
int main() {
    int n = 4;
    vector<vector<int>> graph(n);
 
    auto add_edge = [&](int a, int b) {
        graph[a].push_back(b);
        graph[b].push_back(a);
    };
 
    add_edge(0, 1);
    add_edge(0, 2);
    add_edge(1, 3);
 
    for (int v = 0; v < n; v++) {
        cout << v << ": ";
        for (int next : graph[v]) cout << next << ' ';
        cout << '\n';
    }
}

Python 코드

n = 4
graph = [[] for _ in range(n)]
 
def add_edge(a, b):
    graph[a].append(b)
    graph[b].append(a)
 
add_edge(0, 1)
add_edge(0, 2)
add_edge(1, 3)
 
for v in range(n):
    print(v, ":", graph[v])