인접행렬, 인접리스트

그래프 문제를 풀때 인접행렬, 인접리스트를 다룰일이 워낙 많아서 별도 글로 하나 정리해 둔다.

인접행렬보다는 인접리스트로 구현하는게 일반적으로 더 나은데, 간선수가 최대일 경우 정점의 개수 제곱정도 되는데 인접행렬로 구현하게 되면 항상 이정도 복잡도를 가지는 반면 인접리스트로 구현하면 간선이 드물수록 속도 업이 된다. (예를 들어 그래프가 트리인 경우 최대 간선수는 정점의 제곱이 아닌 정점의 개수-1개 정도로 줄어든다.)

그래서 인접리스트 구현을 먼저 실어두고 나중에 PS할때 이용하려고 한다.

인접리스트 간선가중치 없는 경우

#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<(int)(n);i++)
int N, M, u, v;
int32_t main()
{
    cin >> N >> M;
    vector<vector<int>> adj_list(N + 1);
    REP(i,M){
        cin >> u >> v;
        adj_list[u].push_back(v);
        adj_list[v].push_back(u);
    }
    return 0;
}

인접리스트 간선가중치 있는 경우

w=1로 놓으면 간선가중치 없는 경우에도 범용적으로 쓸수 있기는 한데.. 무거울듯?

#include <bits/stdc++.h>
using namespace std;
 
struct node { int v, w; };
int main()
{
    //V:정점개수, E:간선개수
    int V, E; scanf("%d%d%d", &V, &E);
    vector<vector<node>> adj_list(V + 1);
    for (int i = 0; i < E; i++) {
        int u, v, w; scanf("%d%d%d", &u, &v, &w);
        adj_list[u].push_back({ v, w });
        //adj_list[v].push_back({ u, w });  //undirected면 주석 풀 것
    }
    return 0;
}
 
 

인접행렬 간선가중치 있는 경우

간선가중치 없는 경우는 단순하게 w대신 1을 넣어주면 되기 때문에 트리비얼하다.

#include <bits/stdc++.h>
using namespace std;
const int INF = INT_MAX / 4;
int n, m, u, v, w;
int main()
{
    scanf("%d%d", &n, &m);
    vector<vector<int>> in(n+1, vector<int>(n+1, INF));  // 없는간선은 INF
    // 위에가 좀 문법적으로 헤비하면 int in[1001][1001]; 이런식으로 써도 된다.초기화 별도
    for (int i = 0; i < n; i++) in[i][i] = 0;  // 자기자신은 0
    for (int i = 0; i < m; i++) {
        scanf("%d%d%d", &u, &v, &w);
        // 간선이 여러개일경우, 최단거리 단선만 기억(인접리스트와 다르게 이처리 필수)
        // 이문제의 경우 1-base index라 1빼줌(문제에 따라 다르게 처리)
        in[u - 1][v - 1] = min(in[u - 1][v - 1], w);
    }
    return 0;
}