🌌 graph - 그래프의 표현, DFS와 BFS

안녕하세요 :) 오늘은 그래프라는 자료구조를 표현하는 방법에 대해 알아보고, 그래프 탐색 알고리즘인 DFS, BFS의 구현 방법에 대해 알아보겠습니다. 그럼 오늘도 화이팅 입니다🌿

그래프란 ?

• 그래프란 정점과 간선으로 정보를 표현하는 자료구조입니다.
• 보통 알고리즘 문제에서 다루는 그래프의 종류는 크게 방향의 유무, 가중치의 유무, 사이클의 유무로 분류 됩니다.
• 그래프의 차수란 정점과 연결되어있는 간선의 개수를 의미합니다.
• (코드상으로) 그래프를 저장하는 방법엔 크게 3가지가 있습니다.
  • 인접 행렬
  • 인접 리스트
  • 간선 리스트
• 그래프를 저장한다는 것은 어떤 정점 x와 연결된 간선을 효율적으로 찾을 수 있게, 저장하는 방법을 의미합니다.
  • 정점의 개수 → V
  • 그래프 → A[][]
  • 특정 간선의 각 정점 → i, j ( i, j < V)

그래프 표현방식 - 인접 행렬

그래프를 인접 행렬 방식으로 표현한다는 것은, A[i][j]라는 V*V 크기의 이차원 배열을 활용하여, A[i][j] = w의 형태로 값을 저장하는 방법을 의미합니다. w에는 가중치/ 무가중치 그래프인지에 따라 가중치 값/ true, false 가 들어가게 됩니다.

• 공간복잡도 : O(V*V)
• 시간복잡도
  • 두 정점을 알 때, 특정 간선의 존재, 가중치 확인 → O(1)
  • 특정 간선의 반대 방향 간선도 존재하는지 확인 → O(1)
  • 특정 정점과 연결된 모든 간선 확인 → O(V)

그래프 표현방식 - 인접 리스트

그래프를 인접 리스트 방식으로 표현한다는 것은, A[i]라는 특정 정점 (i)에 대한 리스트에, 해당 정점과 연결된 정점을 저장하는 방법을 의미합니다. 따라서, 해당 A는 특정 정점의 간선의 개수에 따라 동적인 크기를 갖게 됩니다. cpp의 경우엔 vector를 활용하는 편이 쉽습니다.

• 공간복잡도 : O(E)
• 시간복잡도
  • 두 정점을 알 때, 특정 간선의 존재, 가중치 확인 → O(해당 정점의 차수)
  • 특정 간선의 반대 방향 간선도 존재하는지 확인 → O(해당 정점의 차수)
  • 특정 정점과 연결된 모든 간선 확인 → O(해당 정점의 차수)

그래프 탐색

그래프 탐색이란 임의의 시작점에서 탐색을 시작하여 모든 정점을 1번씩 방문하는 것을 의미합니다. 이는 그래프의 표현 방식에 따라서, 코드와 시간 복잡도가 조금 다를 수 있습니다. 상황에 따라 적절한 그래프 표현방식을 선택하는 것이 좋지만, 보통의 경우에는 인접 리스트의 그래프 표현 방식이 시간 복잡도면에서 효율적입니다.

그래프 탐색 - DFS

인접행렬

시간복잡도 : O(V * V)

void dfs(int x) {
    check[x] = true;
    printf("%d ",x);
    for (int i=1; i<=n; i++) {
        if (a[x][i] == 1 && check[i] == false) {
            dfs(i);
        }
    }
}

인접리스트

시간복잡도 : O(V+E)

void dfs(int x) {
    check[x] = true;
    printf("%d ",x);
    for (int i = 0; i<a[x].size(); i++) {
        int y = a[x][i];
        if (check[y] == false) {
            dfs(y);
        }
    }
}

그래프 탐색 - BFS

인접행렬

시간복잡도 : O(V * V)

queue<int> q;
check[1] = true; q.push(1);
while (!q.empty()) {
    int x = q.front(); q.pop();
    printf("%d ",x);
    for (int i=1; i<=n; i++) {
        if (a[x][i] == 1 && check[i] == false) {
            check[i] = true;
            q.push(i);
        }
    }
}

인접리스트

시간복잡도 : O(V+E)

queue<int> q;
check[1] = true; q.push(1);
while (!q.empty()) {
    int x = q.front(); q.pop();
    printf("%d ",x);
    for (int i = 0; i<a[x].size(); i++) {
        int y = a[x][i];
        if (check[y] == false) {
            check[y] = true; q.push(y);
        }
    }
}