[1][그래프 이론] - 그래프 표현 및 정의

 

그래프(Graph) 란?

 

그래프는 어떤 자료나 개념을 각각의 정점들(vertex)의 집합 V와 그 정점들을 이어주는 간선들(edge)의 집합 E로 구성된 자료 구조이다.

 

이러한 그래프는 크게 두가지로 표현이 가능하다.

 

1. 인접 리스트 표현

2. 인접 행렬 표현

 

---

 

1. 인접 리스트 표현

첫번째로 그래프를 표현할 수 있는 방법은 인접 리스트 이다.

 

#include <iostream>
#include <vector>

using namespace std;

int main(){
    vector<vector<int>> v;

    for(int i=0;i<4;i++){
        v.push_back(vector<int>());
    }
    v[0].push_back(1);
    v[0].push_back(2);

    v[1].push_back(0);
    v[1].push_back(2);
    v[1].push_back(3);

    v[2].push_back(0);
    v[2].push_back(1);
    v[2].push_back(3);

    v[3].push_back(1);
    v[3].push_back(2);
}

 

상단에 주어진 그래프를 표현하는 코드이다.

 

vector내에 int형을 가지는 vector를 포함하는 타입을 활용해서 각 정점마다 간선이 존재하는 정점들을 추가하여 구성하였다.

 

예를들어

v[2].push_back(1) 의 경우는 2번 정점에서 1번 정점으로 가는 간선이 존재하므로 추가해준것이고 결국 

v[2] 는 0,1,3 을 가지는 벡터가 될것이고 이것은 2번 정점에서 0,1,3 정점으로 갈수 있다는 의미이다.

 

 

---

2. 인접 행렬 표현

두번째로 그래프를 표현할 수 있는 방법은 인접 행렬이다.

 

#include <iostream>
#include <vector>

using namespace std;

int main(){
    int graph[4][4];

    for(int i=0;i<4;i++){
        for(int j=0;j<4;j++){
            graph[i][j] = 0;
        }
    }
    graph[0][1] = 1;
    graph[0][2] = 1;
    graph[1][0] = 1;
    graph[1][2] = 1;
    graph[1][3] = 1;
    graph[2][0] = 1;
    graph[2][1] = 1;
    graph[2][3] = 1;
    graph[3][1] = 1;
    graph[3][2] = 1;
}

 

graph[i][j] 가 0이면 i 정점에서 j 정점으로 갈수있는 간선이 없다는 의미이고, 반대로 1이라면 간선이 존재한다는 의미이다.