그래프(graph)

목차

1. 그래프의 정의
2. 그래프의 분류
3. 그래프의 표현
4. 그래프와 BFS
5. 그래프와 DFS

1. 그래프의 정의

자료구조에서 의미하는 그래프는 다음과 같은 형태이다.

점을 정점(vertex/node)라고 부르고 점을 이어주는 선을 간선(edge)라고 부른다. 그리고, 각 정점에 연결되어있는 간선의 갯수를 차수(degree)라고 한다.

2. 그래프의 분류

- 무방향그래프와 방향그래프

위의 그림과 같이 그래프를 분류할 수 있다. 그래프의 간선에 방향이 없을 경우 무방향 그래프(undirected graph)라고 부르고, 아래와 같이 방향이 있을 경우에는 방향 그래프(directed graph)라고 한다. 이때, 방향 그래프에서 정점에서 나가는 간선의 수를 outdegree, 들어오는 간선의 수를 indegree라고 한다.

- 순환그래프와 비순환그래프

한 점에서 출발하여 출발한 자기 자신으로 되돌아올 수 있는 경로를 사이클이라고 하는데, 이 사이클이 있는 그래프를 순환 그래프(cyclic graph)라고 하고, 사이클이 없는 그래프를 비순환 그래프(acyclic graph)라고 한다.

- 완전그래프

위 그림과 같이 모든 정점이 서로 연결되어 있는 그래프를 완전그래프라고 한다.

- 연결그래프

위와 같이 임의의 두 정점 사이를 지날 수 있는 경로가 존재하는 그래프를 연결그래프라고 한다.

- 단순그래프

두 정점 사이의 간선이 1개 이하이고, 루프가 존재하지 않는 그래프를 단순그래프라고 한다. 이때, 루프는 한 정점에서 출발하여 다시 출발한 정점으로 들어오는 간선을 뜻한다.

3. 그래프의 표현

- 인접행렬(Adjacency matrix)을 이용

먼저 무방향 그래프를 인접행렬로 표현해보자. 연결된 두 정점 사이에는 1, 연결되지 않았을 경우 0으로 표현한다. 무방향 그래프이므로 대각선을 기준으로 대칭적인 행렬의 모습이 나온다.

방향그래프의 경우 다음과 같이 표현할 수 있다. 만약 그래프가 예시로 주어진 아래와 같이 단순그래프가 아니라 두 정점 사이를 있는 간선이 여러개일 경우 0과 1로만 표현하는 이 방식은 문제가 있을 수 있지만, 표현 방식을 알고자하는 목적이므로 고려하지 않겠다.

인접행렬로 그래프를 표현할 경우 정점이 A개이고, 간선이 B개일 때, 두 정점이 연결되어 있는지를 O(1)에 알 수 있다. 공간복잡도는 O(A^2)이고, 한 정점에 연결되어 있는 정점을 알고 싶은 경우의 시간복잡도는 O(A)이다.

인접행렬 표현 방식으로 방향 그래프 구현한 코드를 보자. 무방향 그래프는 방향 그래프를 알면 쉽게 할 수 있으므로 앞으로의 과정에서 설명을 생략한다.

#include <iostream>
using namespace std;
 
int matrix[10][10] = {};
int a, b;
 
int main(void)
{
    cin >> a >> b;
 
    for (int i = 0; i < b; i++)
    {
        int c, d;
        cin >> c >> d;
        matrix[c][d] = 1;
    }
}

- 인접리스트(Adjacency list)를 이용

정점의 갯수가 A, 간선의 갯수가 B라고 하자. A개의 리스트를 만들어 각 정점에 연결된 정점을 리스트에 넣어주면 된다.

인접리스트의 경우 A개의 정점이 필요하고, 방향리스트에서는 간선 1개당 리스트 1개에 원소가 1개씩 추가되고, 무방향리스트에서는 간선 1개당 리스트 2개에 원소가 1개씩 추가된다. 그러므로 방향리스트에서의 원소 갯수의 합은 B개, 무방향리스트에서 원소 갯수의 합은 2B개이다. 그러므로 공간복잡도는 방향리스트에서 O(A+B), 무방향리스트에서 O(A+2B)이다.
인접행렬에서 특정 정점에 연결된 정점들을 살펴보는데 O(V)의 시간이 필요했다면, 인접리스트에서는 연결된 정점의 갯수만큼만 살펴보면 된다.
인접행렬의 공간복잡도가 O(A^2)인 것을 떠올려보자. B가 A에 비해 월등하게 크지 않는 경우에서는 대부분 인접리스트가 공간적으로 효율적이다.

인접리스트를 이용하여 그래프를 구현해보자. 방향리스트의 경우만 구현해보겠다. vector STL을 쓸 수 있는 경우와, 쓰지 못하는 경우로 나눠서 구현하겠다.

• STL 사용 가능 시

#include <iostream>
#include <vector>
using namespace std;
 
vector<int> lis[10];
 
int main(void)
{
    int a, b;
    cin >> a >> b;
 
    for (int i = 0; i < b; i++)
    {
        int u, v;
        cin >> u >> v;
 
        lis[u].push_back(v);
    }
}

• STL 사용 불가능 시

#include <iostream>
using namespace std;
 
int edge[10][2];
int deg[10]; // 각 정점의 outdegree
int* lis[10]; // 정점
int idx[10]; // lis[i]에서 새로운 정점을 추가할 때의 위치
 
int main(void)
{
    int a, b;
    cin >> a >> b;
 
    for (int i = 0; i < b; i++)
    {
        cin >> edge[i][0] >> edge[i][1];
        deg[edge[i][0]]++;
    }
 
    for (int i = 1; i <= a; i++)
        lis[i] = new int[deg[i]];
 
    for (int i = 0; i < b; i++)
    {
        int u = edge[i][0], v = edge[i][1];
        lis[u][idx[u]] = v;
        idx[u]++;
    }
}

4. 그래프와 BFS

BFS 알고리즘은 너비를 우선으로 탐색하는 알고리즘이다. 백준 문제를 풀다 보면 다차원 배열에서 BFS를 이용해야하는 문제들을 많이 볼 수 있다. 원래는 그래프의 각 정점을 탐색하기 위한 것이고, 다차원 배열이 그래프를 표현하는 방법 중 하니이기 때문에 다차원 배열에서도 BFS를 사용하는 것이다. BFS의 기본 알고리즘 순서를 알아보자.

1. 임의의 시작하는 정점을 큐에 넣고 방문했다는 기록을 남긴다.
2. 큐에서 정점을 꺼내어 그와 연결된 모든 정점들에 3과정을 거친다.
3. 해당 정점들을 이전에 방문하였다면 아무 것도 하지 않고, 방문하지 않았다면 해당 정점을 방문했다는 기록을 남기고 큐에 넣는다.
4. 큐의 원소가 빌 때까지 2과정을 반복한다.

기본적으로 알고있는 2차원 배열에서의 BFS와 동작이 비슷하다. 인접리스트로 연결리스트인 그래프가 저장되어 있고 정점은 1번부터 시작한다고 가정하고 BFS 코드를 구현해보았다.

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
 
vector<int> lis[10];
bool vis[10];
 
void BFS()
{
    queue <int> q;
    q.push(1);
    vis[1] = true;
 
    while (!q.empty())
    {
        int cur = q.front();
        q.pop();
        cout << cur << ' ';
 
        for (int i = 0; i < lis[cur].size(); i++)
        {
            int n = lis[cur][i];
            if (vis[n]) continue;
            q.push(n);
            vis[n] = true;
        }
    }
}

그래프의 BFS도 2차원 배열에서와 마찬가지로 시작 정점에서 어떤 정점으로의 최단 거리를 알 수 있다. 모든 간선의 길이가 동일하다는 가정하에 최단 거리를 구하는 코드를 구현해보았다.

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
 
vector<int> lis[10];
int dis[10];
 
void BFSdistance()
{
    for (int i = 1; i < 10; i++) dis[i] = -1;
    queue <int> q;
    q.push(1);
    dis[1] = 0;
 
    while (!q.empty())
    {
        int cur = q.front();
        q.pop();
 
        for (int i = 0; i < lis[cur].size(); i++)
        {
            int n = lis[cur][i];
            if (dis[n] != -1) continue;
            q.push(n);
            dis[n] = dis[cur] + 1;
        }
    }
}

리스트가 연결리스트가 아닌 경우도 있다. 그런 경우의 BFS 코드를 구현해보았다.

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
 
vector<int> lis[10];
bool vis[10];
int a = 9; //정점 수
 
void BFS()
{
    queue <int> q;
 
    for (int i = 1; i <= a; i++)
    {
        if (vis[i]) continue;
        q.push(i);
        vis[i] = true;
 
        while (!q.empty())
        {
            int cur = q.front();
            q.pop();
            cout << cur << ' ';
 
            for (int i = 0; i < lis[cur].size(); i++)
            {
                int n = lis[cur][i];
                if (vis[n]) continue;
                q.push(n);
                vis[n] = true;
            }
        }
    }
}

그래프의 BFS의 경우 시간복잡도가 어떻게 될까? 정점의 수가 A, 간선의 수가 B라고 하자. 모든 정점들의 자기 자신과 연결된 정점을 다 돌아보는데 필요한 탐색 수는 방향그래프의 경우 B번이고, 무방향그래프의 경우 2B번이다. 그러므로 시간복잡도는 O(A+B) 혹은 O(A+2B)이다.

5. 그래프와 DFS

DFS는 깊이를 우선으로 탐색하는 알고리즘이다. BFS에서 정점을 큐에 담던 것을 스택에 담아주는 것을 제외하고는 비슷하다. DFS 알고리즘의 순서를 한번 살펴보자.

1. 임의의 시작하는 정점을 스택에 넣고 방문했다는 기록을 남긴다.
2. 스택에서 정점을 꺼내어 그와 연결된 모든 정점들에 3과정을 거친다.
3. 해당 정점들을 이전에 방문하였다면 아무 것도 하지 않고, 방문하지 않았다면 해당 정점을 방문했다는 기록을 남기고 스택에 넣는다.
4. 스택의 원소가 빌 때까지 2과정을 반복한다.

BFS에서 그랬던 것처럼 인접리스트로 연결리스트인 그래프가 저장되어 있고 정점은 1번부터 시작한다고 가정하고 DFS 코드를 구현해보았다. DFS는 재귀적인 방식과 비재귀적인 방식 2가지로 구현을 할 수 있는데 일단 먼저 비재귀적인 방식의 코드를 보겠다.

#include <iostream>
#include <vector>
#include <stack>
using namespace std;
 
vector <int> lis[10];
bool vis[10];
 
void DFS()
{
    stack <int> s;
    s.push(1);
    vis[1] = true;
 
    while (!s.empty())
    {
        int cur = s.top();
        s.pop();
        cout << cur << ' ';
 
        for (int i = 0; i < lis[cur].size(); i++)
        {
            int n = lis[cur][i];
            if (vis[n]) continue;
            s.push(n);
            vis[n] = true;
        }
    }
}

재귀적인 방식의 코드를 보자. 재귀로 함수를 호출하는 것이 스택의 모양새가 되기 때문에 따로 스택을 이용할 필요가 없다.

#include <iostream>
#include <vector>
#include <stack>
using namespace std;
 
vector <int> lis[10];
bool vis[10];
 
void DFS(int cur)
{
    cout << cur << ' ';
    for (int i = 0; i < lis[cur].size(); i++)
    {
        int n = lis[cur][i];
        if (vis[n]) continue;
        vis[n] = true;
        DFS(n);
    }
}
 
int main(void)
{
    vis[1] = true;
    DFS(1);
}

그런데, 지금 본 비재귀 DFS코드와 재귀 DFS코드는 동작 방식에 약간의 차이가 있다. 둘 모두 깊이 우선으로 모든 정점을 순회하는 것에는 문제가 없지만, 방문하는 순서에 차이가 있다.

이런 그래프에서 기본적으로 갈 수 있는 곳이 여러 개이면 번호가 작은 곳부터 방문한다고 해보자.
비재귀 DFS에서는 1 정점을 스택에서 제거하고 난 뒤, 연결된 2, 3, 4 정점에 방문했다는 기록을 남기고 다음 정점으로 이동하기 때문에 1-2-3-4 순서로 방문한다. 재귀 DFS에서는 1-2-4-3 순으로 방문을 한다. 두 코드에서 방문했다는 기록을 해주는 시기가 다르기 때문에 생기는 일이다.

우리가 정석적으로 생각하는 DFS의 방식은 재귀 DFS이다. 갈 수 있는 곳까지 계속 들어갔다가 막히면 되돌아나와 다른 곳으로 가는 것이 정석적인 DFS이기 때문이다. 비재귀 DFS도 방문을 기록하는 시점을 바꿔주면 재귀 DFS와 동일하게 동작하도록 코드를 만들어 줄 수 있다. 코드를 살펴보자.

#include <iostream>
#include <vector>
#include <stack>
using namespace std;
 
vector <int> lis[10];
bool vis[10];
 
void DFS()
{
    stack <int> s;
    s.push(1);
 
    while (!s.empty())
    {
        int cur = s.top();
        s.pop();
        if (vis[cur]) continue;
        vis[cur] = true;
        cout << cur << ' ';
 
        for (int i = 0; i < lis[cur].size(); i++)
        {
            int n = lis[cur][i];
            if (vis[n]) continue;
            s.push(n);
        }
    }
}

연결그래프가 아닌 경우도 있다. 그때의 DFS도 구현해보았다.

#include <iostream>
#include <vector>
#include <stack>
using namespace std;
 
vector <int> lis[10];
bool vis[10];
int a = 9; //정점 수
 
void DFS()
{
    stack <int> s;
 
    for (int i = 1; i <= a; i++)
    {
        if (vis[i]) continue;
        s.push(i);
        vis[i] = true;
 
        while (!s.empty())
        {
            int cur = s.top();
            s.pop();
            cout << cur << ' ';
 
            for (int i = 0; i < lis[cur].size(); i++)
            {
                int n = lis[cur][i];
                if (vis[n]) continue;
                s.push(n);
                vis[n] = true;
            }
        }
    }
}

마지막으로, BFS와는 다르게 DFS는 시작 정점부터의 거리를 구할 수 없다.