[그래프] 그래프의 표현

kjh107704·2020년 4월 5일
0

알고리즘

목록 보기
3/9
post-thumbnail

그래프의 표현 방법은 총 세가지가 존재한다.

  1. 인접 행렬
  2. 인접 리스트
  3. 간선 리스트

대부분의 경우에는 인접 리스트를 사용하고, 부득이한 경우에는 간선 리스트를 사용한다. 인접행렬은 필요없는 공간의 소모가 많기 때문에 잘 사용하지 않는다.

그래프를 저장할 때는 두 가지 정보를 저장하게 된다.
1. 정점 (V)
개수만 저장하면 된다. 보통 1 ~ V로 주어지며, index로 이용하게 된다.
2. 간선 (E)
어떤 간선이 있었는지를 저장하면 된다. E개의 간선을 그냥 배열에 때려넣어도 되지만, 간선을 저장한다는 것의 의미는 어떤 정점과 연결된 간선을 찾을 수 있다는 의미이다.

인접 행렬

정점의 개수를 V개라고 했을 때, V*V 크기의 이차원 배열을 이용한다.

간선의 가중치가 존재하지 않을 때

 A[i][j] = 1 (i -> j 간선이 존재할 때)
 A[i][j] = 0 (i -> j 간선이 존재하지 않을 때)
 ```

 ```cpp
 #include <iostream>
 using namespace std;

 int main()
 {
     int v, e;
     int g[v + 1][v + 1];

     for (int i = 0; i < e; i++)
     {
         int x, y;
         cin >> x >> y;
         // 양방향 그래프일 때
         g[x][y] = g[y][x] = 1;
         // 방향 그래프일 때
         g[x][y] = 1;
     }
 }

간선의 가중치가 존재할 때

w >= 0 인 경우

    A[i][j] = w (i -> j 간선이 존재할 때)
    A[i][j] = 0 (i -> j 간선이 존재하지 않을 때)

w가 정수 범위인 경우

인접행렬 2개를 사용해야 한다.

  1. 간선이 존재하는지 여부를 알려주는 인접행렬
    // A : 간선이 존재하는지를 알려주는 인접행렬
    A[i][j] = 1 (i -> j 간선이 존재할 때)
    A[i][j] = 0 (i -> j 간선이 존재하지 않을 때)
  2. 간선의 가중치를 알려주는 인접행렬
    // B : 간선의 가중치를 알려주는 인접행렬
    B[i][j] = w

인접 리스트

linked-list를 이용하여 구현한다. 굳이 linked-list를 사용하는 이유는 어떤 노드와 연결된 정점이 정확하게 몇 개인지 모르기 때문 이다.

인접 행렬은 i -> j 의 경로에서 서로 다른 가중치를 가진 여러 간선을 구분하여 저장할 수 없다.

linked-list를 직접 구현하려면 시간이 오래 걸리기 때문에, 주로 vector와 같이 길이를 변경할 수 있는 배열을 이용하여 구현한다.

간선의 가중치가 존재하지 않을 때

graph[i] -> i에 연결된 edge의 집합
ex) graph[1] = 5edge (1,5)를 의미한다

#include <iostream>
#include <vector>
using namespace std;

int main()
{
	int n, m;
    cin >> n >> m;
    
    vector<int> graph[n+1]; // node 번호가 1 ~ n 일 경우
    
    for(int i = 0; i < m; i++)
    {
    	int u, v;
        cin >> u >> v;
        graph[u].push_back(v);
        // 양방향 그래프일 경우 양쪽에 저장
        // graph[v].push_back(u);
    }
}

간선의 가중치가 존재할 때

graph[i] -> i에 연결된 edge의 집합
graph[1] = pair(5, 3)1 -> 5 의 edge가 존재하고, w = 3임을 의미

#include <iostream>
#include <vector>
using namespace std;

int main()
{
	int n, m;
    cin >> n >> m;
    
    vector<pair<int,int>> graph[n+1];
    
    for(int i = 0; i < m; i++)
    {
    	int u, v, w;
        cin >> u >> v >> w;
        
        graph[u].push_back(make_pair(v, w));
        // 양방향 그래프일 경우 양쪽에 저장
        // graph[v].push_back(make_pair(u, w));
    }
}

인접 행렬과 인접 리스트의 공간 복잡도

구분공간복잡도
인접 행렬O(V^2)
인접 리스트O(E)

우리가 주로 다룰 그래프는 E < V 이므로, 인접리스트를 사용하여 그래프를 표현하는 것이 효과적이다.

간선 리스트

인접 리스트와 인접 행렬을 모두 사용할 수 없는 경우 간선 리스트를 사용한다. STL, Array collection 등을 사용할 수 없는 경우가 여기에 해당된다.

하나의 배열을 이용하여 모든 간선을 저장하고, 누적합을 저장한 다른 배열로 한 정점의 간선이 저장된 index의 범위를 알려주도록 한다.

아래와 같이 구현할 경우, i번 정점과 연결된 간선은 E배열에서 index가 cnt[i-1]번 부터 cnt[i]-1 인 것에 해당한다.

#include <iostream>
using namespace std;

int main()
{
	int n, m;
    cin >> n >> m;
    
    // E[i][0] = i번째 간선의 시작 정점
    // E[i][1] = i번째 간선의 도착 정점
    int E[m][2]; 
    int cnt[n];
    
    for(int i = 0; i < m; i++)
    {
    	int u, v;
        cin >> u >> v;
        E[i][0] = u;
        E[i][1] = v;
    }
    
    // E 배열을 E[i][0] (시작 정점)을 기준으로 정렬
    
    // 각 정점에 연결되어 있는 edge의 개수 세기
    for(int i = 0; i < m; i++)
    	cnt[e[i][0]] += 1;
   	// cnt의 누적합 구하기
    for(int i = 1; i <= n; i++)
    	cnt[i] = cnt[i-1] + cnt[i];
}

출처
백준 알고리즘 인강

profile
뻘짓을 많이 하는 꼬부기

0개의 댓글