그래프

∙ 그래프

- 객체 간의 연결 관계를 표현할 수 있는 비선형 자료 구조

- 쾨니히스베르크의 다리 문제(한붓그리기)'가 그래프 이론의 시초로 알려져 있음

- 그래프의 예 : 지도에서 도시들의 연결, 지하철 노선도, SNS 친구 관계도 등

 

∙ 그래프의 구성 요소

- 그래프 G = (V, E)

- 정점 (vertex, node) : V

> 그래프를 구성하는 기본 단위. 노드

> 자료를 저장하거나 상태를 표현

- 에지 (edge, link) : E

> 정점과 정점을 잇는 선, 간선

> 방향을 가질 수 있음

> 가중치를 가질 수 있음

 

 

∙ 인접 행렬(adjacency matrix)

- 정점 개수가 N인 경우, N X N 크기의 2차원 행렬로 정점의 인접 관계를 표현하는 방법

- adj [u][v] : 노드 u에서 노드 v로 가는 간선이 있으면 1, 아니면 0

- 그래프 정점 개수가 적고, 에지가 많을 때 유리 공간 복잡도는 O(N^2)

 

∙ 인접 리스트 (adjacency list)

- 각 정점에 인접한 정점들을 연결리스트로 표현

- 보통 정점 개수에 해당하는 배열의 각 원소에 연결 리스트가 속해 있는 형태로 표현

- 공간 복잡도는 O(N + M) (N : 정점 개수, M : 에지 개수)

 

 

∙ 에지 리스트 (edge list)

- 모든 에지 (u, v)를 리스트 또는 배열로 표현

- 공간 복잡도는 O(M) (M : 에지 개수)

 

∙ 인접 행렬을 인접 리스트로 변환하는 예제 프로그램

#include <iostream>
#include <vector>

using namespace std;

vector<vector<int>> get_adj_list(const vector<vector<int>>& adj_matrix)
{
    // 인접 리스트를 저장할 벡터 생성
    vector<vector<int>> adj_list(adj_matrix.size());
    
    // 행번호에 해당하는 정점과 인접해 있는 정점번호를 푸시
    for (int u = 0; u < adj_matrix.size(); u++){
        for (int v = 0; v < adj_matrix.size(); v++){
            if (adj_matrix[u][v] == 1)
                adj_list[u].push_back(v);
        }
    }
    return adj_list;
}
/*
// 인접 리스트 (adjacency list)
 vector<vector<int>> adj_list = {
    {1, 3, 4},
    {0, 2, 4},
    {1, 5},
    {0, 4},
    {0, 1, 3},
    {2}
 };
 
*/

int main()
{
    // 인접 행렬 (adjacency matrix)
    vector<vector<int>> adj_matrix = {
        {0, 1, 0, 1, 1, 0},
        {1, 0, 1, 0, 1, 0},
        {0, 1, 0, 0, 0, 1},
        {1, 0, 0, 0, 1, 0},
        {1, 1, 0, 1, 0, 0},
        {0, 0, 1, 0, 0, 0}
        
    };
    
    vector<vector<int>> adj_list = get_adj_list(adj_matrix);
    
    for (const auto& l : adj_list){
        for (const auto n : l)
            cout << n << ", ";
        cout << endl;
    }
}