[자료구조] 그래프의 간선 리스트

인접 행렬

• V^2개의 원소를 가진 2차원배열.

 

인접 리스트

• V개의 연결리스트( 동적 배열 )
• vector기반이라 느리다.
• 간선 번호 붙일 때 불편하다 ( 순회하기 힘들다. )

 

간선 배열

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

typedef pair<int, int> pint;
#define x first
#define y second

const int maxv = 100000, maxe = 200000;
pint edge[maxe]; // 배열의 각 주소는 (x, y) 튜플 페어를 가짐.
int st[maxv]; // 간선을 정렬한 후, 각 점에서 시작하는 간선의 첫 인덱스
int v, e;

int main() {
    // Input
    cin >> v >> e;
    for (int i=1; i<=e; i++)
        cin >> edge[i].x >> edge[i].y;

    // Processing
    sort(edge+1, edge+e+1);
    st[v+1] = e+1;
    for (int i=1, k=1; i<=e; i++)
        while (edge[i].x >= k) st[k++] = i;

    // Output
    for (int i=1; i<=v; i++)
        for (int j=st[i]; j<st[i+1]; j++)
            cout << i << " and " << edge[j].y << " are connected.\n";
}

• 간선을 시작점, 끝점 순서로 정렬.
• 그리고 각 정점에서 시작하는 간선을 찾기위해 st배열에 시작간선, 끝간선을 저장.
  • (st[i] ~ st[i+1] - 1 번 간선은 i에서 시작)
• 이걸 쓰면 인접리스트의 단점인 간선을 순회하기 불편하다는 단점을 보완할 수 있다.
• O(ElogE)

 

간선 리스트

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

const int maxv = 100000, maxe = 200000;
int a[maxe], b[maxe], nxt[maxe], st[maxv], p = 2;
void add(int x, int y) {
    a[np] = x; b[np] = y; nxt[np] = st[x]; st[x] = p++;
}
int v, e;

int main() {
    cin >> v >> e;
    for (int i=1; i<=e; i++) {
        int x, y;
        cin >> x >> y;
        add(x, y);
    }

    for (int i=1; i<=v; i++)
        for (int j=st[i]; j; j=nxt[j])
            cout << a[j] << " and " << b[j] << " are connected.\n";
}

• 인접배열에서 배열을 연결 리스트로 바꾼 방법.
• 각 정점은 자신과 연결된 간선들을 저장하는 ㅇ녀결 리스트를 하나씩 가지고 있고 연결리스트들은 하나의 배열안에 모두 들어있다. 연결리스트는 다음 원소의 포인터가 아닌 다음 원소의 배열에서의 인덱스를 가지고 있다.
• 즉 1. 간선을 저장한느 배열, 2. 각 정점에서 연결되는 간선들을 저장하는 연결리스트 로 이루어져있다.
• 그래프를 정점, 간선 두가지 요소로 분리해 사용.
• O(E)

#include <iostream>
using namespace std;

const int maxv = 100000, maxe = 200000;
int a[maxe], b[maxe], w[maxe], nxt[maxe], st[maxv], p = 2;
void add(int x, int y, int wt) {
    a[np] = x; b[np] = y; w[np] = wt; nxt[np] = st[x]; st[x] = p++;
}
int v, e;

int main() {
    cin >> v >> e;
    for (int i=1; i<=e; i++) {
        int x, y, w;
        cin >> x >> y >> w;
        add(x, y, w);
    }

    for (int i=1; i<=v; i++)
        for (int j=st[i]; j; j=nxt[j])
            cout << a[j] << " and " << b[j] << " are connected in weight " << w[j] << ".\n";
}

• 유량 알고리즘은 역간선을 쉽게 구해야 하는데 간선과 역간선을 리스트의 인접한 인덱스에 넣어두면 쉽게 역간선에 접근 할 수 있다. 위에서 i번 간선의 역간선은 i^1번 간선이다(xor)
• 무방향 그래프에서 홀짝을 맞추기위해 초기 p=2
• 간선 순서를 섞어주어야 하는 상황에서는 쓰면 안된다(크루스칼)

 

Reference

https://blog.junie.land/11 [프로그래밍 연습장]