챕터6-2. 그래프 | 그래프의 표현 및 저장하는 방법

그래프의 표현

정점 : {1, 2, 3, 4, 5, 6}

간선 : {(1, 2), (1, 5),  (2, 5), (2, 3), (3, 4), (2, 4), (4, 5), (4, 6)}

- '정점'이 V개 일 때 보통 정점에 1~V 혹은 0~V-1로 번호를 매기기 때문에 개수만 저장해둬도 된다.

- '간선'은 무엇과 무엇을 연결하는지에 대한 중요한 관계를 나타내므로 간선을 저장하는 것이 그래프를 저장하는 것이 된다.

- 그래서 보통 문제에서 그래프에 관해 입력데이터를 줄 때는 정점의 개수, 간선의 개수, 간선의 관계를 아래와 같이 준다.
   (양방향 그래프인지 단방향 그래프인지는 문제의 본문을 읽어야지만 알 수 있다)

예시 1) 가중치가 없는 경우
6 8                      // n : 정점의 개수, m : 간선의 개수
1 2                       // 1->2 의 간선

1 5

2 3

2 4

2 5

5 4

4 3

4 6

 

예시 2) 가중치가 있는 경우

6 8                      // n : 정점의 개수, m : 간선의 개수
1 2 2                    // 1->2 의 간선, 가중치가 2

1 5 7

2 3 2

2 4 3

2 5 1

5 4 7

4 3 1

4 6 7

그래프를 저장하는 방법 2가지

* 아래에서 사용되는 '간선의 개수 E'는 양방향 그래프의 경우에 A-B를 A->B, B->A로 풀어서 계산한 것을 의미한다.

 

# 인접 행렬(Adjacency-matrix)

- 정점의 개수를 V개라고 했을 때, V x V 크기의 이차원 배열(행렬모양)에 저장한다.

- A[i][j] = 1 or 0  (i->j 간선이 있을 때는 1, 없을 떄는 0)
- 양방향 그래프의 경우 이차원 배열에 저장했을 때 대각선을 기준으로 대칭을 이룬다는 특징이 있음.
- 인접행렬은 자주 사용하지 않는 방식인데, 그 이유는 존재하지 않는 간선에 대한 정보까지도 저장하기 때문이다.
   정점의 개수가 V개이면 간선의 개수 E는 보통 V^2 >= E 이기 때문에 최대크기인 V x V를 사용하는 이 방식은 비효율적임.
   따라서, 이 방식은 주로 쉬운 문제를 풀 때만 사용한다.
- 간선에 가중치가 존재한다면 A[i][j]에 0 또는 1 대신 가중치 값을 넣어주면 된다.
   <이때의 예외상황>
   1) 가중치의 값이 w >=0 이라면, 간선이 없는 곳은 0대신 -1을 넣어 구별해줄 수 있다.
   2) 가중치의 값이 모든 범위의 정수라면, 인정행렬 2개를 만들어 해결해야하는데,
       인접하면 1 아니면 0을 저장한 행렬 1개, 인접한 곳의 가중치를 저장한 행렬 1개 즉, 총 2개의 인접행렬을 만들어 해결할 수 있다.

- 아래는 글의 맨 위의 예시와 같은 입력이 주어졌을 때 인접행렬로 저장하는 코드이다.

/*가중치가 없을 때, 방향이 없는 그래프 (양방향 그래프)인 경우*/
# include <iostream>

using namespace std;

int a[10][10];

int main()
{
    int n, m;
    cin >> n >> m;
    
    for (int i = 0; i < m; i++){
        int u, v;
        cin >> u >> v;
        a[u][v] = a[v][u] = 1;    // 그래프가 방향이 있을 때와 없을 때의 차이는 여기만.
    }
}

/*가중치가 없을 때, 방향 그래프인 경우*/
# include <iostream>

using namespace std;

int a[10][10];

int main()
{
    int n, m;
    cin >> n >> m;
    
    for (int i = 0; i < m; i++){
        int u, v;
        cin >> u >> v;
        a[u][v] = 1             // 그래프가 방향이 있을 때와 없을 때의 차이는 여기만.
    }
}

/*가중치가 있을 때, 방향이 없는 그래프 (양방향 그래프)인 경우*/
# include <iostream>

using namespace std;

int a[10][10];

int main()
{
    int n, m;
    cin >> n >> m;
    
    for (int i = 0; i < m; i++){
        int u, v, w;
        cin >> u >> v >> w;
        a[u][v] = a[v][u] = w;        // 그래프가 방향이 있을 때와 없을 때의 차이는 여기만.
    }
}

/*가중치가 있을 때, 방향 그래프인 경우*/
# include <iostream>

using namespace std;

int a[10][10];

int main()
{
    int n, m;
    cin >> n >> m;
    
    for (int i = 0; i < m; i++){
        int u, v, w;
        cin >> u >> v >> w;
        a[u][v] = w;              // 그래프가 방향이 있을 때와 없을 때의 차이는 여기만.
    }
}

 

# 인접 리스트(Adjacency-list)

- A[i] = i와 연결된 정점들을 링크드 리스트로 저장함(연결된 정점이 저장되어 있지만 이들은 정점 i와 각 정점 간의 간선을 의미한다)

- 정점에 따라서 연결된 정점의 개수가 다르기 때문에 각기 다른 저장공간의 크기를 효율적으로 관리하기 위해 링크드 리스트를 사용.
- 링크드 리스트를 사용하는 이유는 단지 공간효율때문에 그런 것이므로 아래의 것들로 대체하여 인접리스트를 구현할 수 있다.
   C++ : Vector

   Java : ArrayList

- 두 노드간의 간선이 여러개인 경우 인접행렬 보다 인접리스트를 사용하는 것이 좋다.
   그 복잡한 관계는 인접행렬 1개 만으로 나타낼 수 없기 때문이다. 인접리스트는 이것이 가능하다.
- 또 유리한 점은 인접행렬의 경우 공간이 V^2 만큼 필요한데, 인접리스트는 모든 간선을 1번씩 저장하기 때문에 E개 만큼 필요함.

 

A[1] 2 5
A[2] 1 3 4 5
A[3] 2 4

A[4] 3 5 2 6

A[5] 1 2 4

A[6] 4

 

A[1] (2,2) (5, 7)
A[2] (1,2) (3,2) (4,3) (5,1)
A[3] (2,2) (4,1)

A[4] (3,1) (5,7) (2,3) (6,7)

A[5] (1,7) (2,1) (4,7)

A[6] (4,7)

 

- 가중치가 있는 경우 pair<int, int> 형을 가지는 2차원 벡터로 해결

- 아래는 글의 맨 위의 예시와 같은 입력이 주어졌을 때 인접리스트로 저장하는 코드이다.

/*가중치가 없을 때, 방향이 없는 그래프 (양방향 그래프)인 경우*/
# include <iostream>
# include <vector>

using namespace std;

vector<int> a[10]; // 2차원 벡터 생성

int main()
{
    int n, m;
    cin >> n >> m;
    
    for (int i = 0; i < m; i++){
        int u, v;
        cin >> u >> v;
        a[u].push_back(v);        // 그래프가 방향이 있을 때와 없을 때의 차이는 여기만.
        a[v].push_back(u);        // 그래프가 방향이 있을 때와 없을 때의 차이는 여기만.
    }
}

/*가중치가 없을 때, 방향 그래프인 경우*/
# include <iostream>
# include <vector>

using namespace std;

vector<vector<int>> a(10); // 2차원 벡터 생성

int main()
{
    int n, m;
    cin >> n >> m;
    
    for (int i = 0; i < m; i++){
        int u, v;
        cin >> u >> v;
        a[u].push_back(v);        // 그래프가 방향이 있을 때와 없을 때의 차이는 여기만.
    }
}

/*가중치가 있을 때, 방향이 없는 그래프 (양방향 그래프)인 경우*/
# include <iostream>
# include <vector>
# include <utility>

using namespace std;

vector<pair<int, int>> a[10]; // 2차원 벡터 생성

int main()
{
    int n, m;
    cin >> n >> m;
    
    for (int i = 0; i < m; i++){
        int u, v, w;
        cin >> u >> v >> w;
        a[u].push_back(make_pair(v, w));        // 그래프가 방향이 있을 때와 없을 때의 차이는 여기만.
        a[v].push_back(make_pair(u, w));        // 그래프가 방향이 있을 때와 없을 때의 차이는 여기만.
    }
}

/*가중치가 있을 때, 방향 그래프인 경우*/
# include <iostream>
# include <vector>
# include <utility>

using namespace std;

vector<vector<pair<int, int>>> a(10); // 2차원 벡터 생성

int main()
{
    int n, m;
    cin >> n >> m;
    
    for (int i = 0; i < m; i++){
        int u, v, w;
        cin >> u >> v >> w;
        a[u].push_back(make_pair(v, w));        // 그래프가 방향이 있을 때와 없을 때의 차이는 여기만.
    }
}

두 방법의 공간 복잡도 비교

인접 행렬 : O(V^2)      -> 존재하지 않는 간선에 대한 정보도 저장하기 때문에 상대적으로 속도도 느림.

인접 리스트 : O(E)

간선 리스트 : O(E)

 

결론 : 보통 우리가 다루는 문제들은 정점의 개수보다 간선의 개수가 상대적으로 적기 때문에
            인접 행렬보다는 인접 리스트를 사용하여 저장하는 것이 올바른 방법이다.

기타 추가적인 그래프 저장방법

* 아래의 방법은 STL 등의 내장 클래스를 사용할 수 없는 상황에서 사용한다.
* 아래의 방법의 공간복잡도는 인접 리스트와 같은 O(E) 이다.

 

# 간선 리스트(Edge-list)

- 2차원 배열을 사용하여 간선을 모두 저장하는 방식이다.(양방향 그래프인 경우 단방향 간선으로 모두 풀어서 저장)

1. 아래의 경우 간선의 총 개수는 16개이므로 int E[16][2] 크기의 2차원 배열을 선언하여 저장한다.
- ex) E[15][0] = 6, E[15][1] = 4          // 6->4 의 간선을 의미함

2. 그 다음 간선의 시작점을 기준으로 정렬하여 순서를 바꾼다. (즉, E[i][0] 값을 기준으로 정렬)

 

3. 간선의 시작점을 기준으로 개수를 세어준다.

int cnt[7];

for(int i = 0; i < e*2; i++)
    cnt[e[i][0]] += 1;

 

4. cnt의 누적값을 구한다.

for(int i = 1; i <= v; i++)
    cnt[i] = cnt[i-1] + cnt[i];

 

5. 이제 i 정점과 연결된 간선은 E배열에서 E[ cnt[i-1] ] ~ E[ cnt[i] -1 ] 까지 이다.