Graph Basic

그래프는 다음과 같은 요소로 이루어져 있다.

• 노드(Node): 정점(Vertex)라고도 함
• 간선(Edge)

그리고 다음과 같은 용어를 정의하자.

• 경로(Path): 한 노드에서 그래프의 간선을 지나 다른 노드까지 가는 길
• 사이클(Cycle): 처음 노드와 마지막 노드가 같은 경로
• 연결 그래프(Connected Graph): 모든 노드에 연결 경로가 있을 경우
• 컴포넌트(Component): 그래프의 연결된 부분 부분을 의미
• 트리(Tree): 사이클이 없는 연결 그래프
• 방향 그래프(Directed Graph): 간선이 이동방향을 가짐
• 가중 그래프(Weighted Graph): 간선이 가중치를 가짐 - 길이로 해석 가능
• 이웃 노드(Neighbor / Adjacent Node)
• 차수(Degree): 이웃 노드의 개수
  • 간선의 개수가 m일 때, 차수의 합은 항상 2m이 된다.
  • 각 간선은 그 간선이 잇는 두 노드의 차수를 1씩 증가시키기 때문. 따라서 항상 짝수
• 정규 그래프(Regular Graph): 모든 노드의 차수가 상수 d로 같을 경우
• 완전 그래프(Complete Graph): 모든 노드의 차수가 n-1인 경우. 즉, 서로 다른 모든 두 노드 사이에 간선이 있는 경우
• 진입차수(Indegree): 그 노드로 향하는 간선의 개수
• 진출차수(Outdegree): 그 노드에서 시작하는 간선의 개수

그래프의 표현

1. 인접 리스트
   • vector<int> adj[N]
   • vector<pii> adj[N]: 가중 그래프의 경우
2. 인접 행렬
   • int adj[N][N]
3. 간선 리스트(Edge List)
   • vector<pii> edges
     • 1과 유사해보이지만 다르다. Edge만 저장한 것
   • vector<piii> edges: 가중 그래프의 경우

그래프의 순회

1. DFS

vector<int> adj[N];
bool visited[N];
void dfs(int s) {
    if (visited[s]) return;
    visited[s] = true;
    for(auto u: adj[s]) {
        dfs(u);
    }
}

2. BFS

   노드 x로부터 각 노드까지 걸리는 거리를 구한다고 해보자. 잘 안쓰이는 방식이긴 하지만(구현이 dfs보다 복잡해서) 아래처럼도 가능하다.

queue<int> q;
bool visited[N];
int distance[N];

void BFS(int x) {
    visited[x] = true;
    distance[x] = 0;
    q.push(x);
    while(q.size()) {
        int s = q.front(); q.pop();
        for (auto u: adj[s]) {
            if (visited[u]) continue;
            visited[u] = true;
            distance[u] = distance[s] + 1;
            q.push(u);
        }
    }
}