그래프(Graph)의 정의와 표현

그래프(Graph)의 정의와 표현

알고리즘에 대해 공부할 때 가장 장벽이 높다고 생각하는 부분이 바로 그래프이다.

이번 글에서는 기나긴 그래프 알고리즘에 들어가기에 앞서,

간단하게 그래프가 무엇인지, 어디에 사용하는지, 어떻게 사용하는지에 대해 알아보도록 하자.

그래프(Graph)란?

그래프는 실제 세계의 현상이나 사물을 정점(Vertex)와 간선(Edge)으로 표현을 하기 위해 사용한다.

실제 예를 들어보도록 하자.

위의 그림은 일상 생활에서 돈관계를 그래프 구조로 표현을 한 것이다.

민희는 철수에게 5000원을 갚아야 하고,

철수는 영희에게 6000원,

영희는 민수에게 100원,

민수는 영희에게 500원 을 갚아야 하는 관계이다.

이렇게 실제 세계의 현상, 즉 여기에서는 사물들 간의 관계를 그래프로 표현 할 수 있다.

두 번째 예는 집에서 학교 도서관, 또는 강의실로 가는 경로를 그래프로 표현을 해본 것이다.

집에서는 버스정류장이나, 지하철을 이용해서 학교를 갈 수 있고,

학교에서는 또 도서관이나 강의실로 이동을 할 수 있다.

이것은 그래프로 사물들 간의 순서를 그래프로 표현 한 것이다.

이런 예의 경우들 말고도 그래프는 모델링 하는 방법이 매우 다양하게 사용되며,

주로 복잡한 실제세계의 현상을 컴퓨터로 옮길 때 능력껏 사용하게 된다.

용어

V : 정점(Vertex,Node) - Ex) 집, 학교, 정류장, 철수, 민희...

E : 간선(Edge)  - Ex) 지하철과 학교를 잇는 선, 민희와 철수를 잇는 선

W : 가중치(Weight) - Ex) 민희와 철수 사이의 5000원

G=(V,E) : 그래프 G는 집합 V와 이들간의 간선 E로 구성

G=(V,E,W)

간단한 종류

유향 그래프(Directed Graph) - 정점 간의 간선이 방향이 존재할 경우

무향 그래프(Undirected Graph) - 정점 간의 간선이 방향이 없을 경우

가중치 - 정점 간의 간성이 특정한 값을 가지는 경우

그래프를 어디에?

실생활에서 가장 가깝게 느껴지는 예를 들면, 지하철을 예로 들수 있다.

우리가 지하철을 타고 학교를 가고 싶을 때 어떻게 하면 A역에서 B역으로 빨리 갈 수 있을 까라고 생각하면

아마도 핸드폰의 앱에서 어디로 가는 것이 가장 빠르다고 알려줄 것이다.

이 때 역 하나하나를 정점(V)로 설정하고 역간의 관계를 간선(E)로 표현을 한 그래프로, 최단거리 알고리즘으로

우리가 가는 목적지의 최단거리를 찾아 주는 프로그램일 확률이 매우 높다.(실제로는 아닐수도 있다)

위에서는 간단히 실생활 예를 들었지만 그 이외에도 그래프로는 정말로~~~~~많은 알고리즘에 이용될 수 있다. 

앞으로 학습을 하겠지만,  최단거리 알고리즘(다익스트라,벨만포드), 네트워크 플로우, 최소 스패닝 트리, DFS, BFS....등등 그래프를 이용하여서 정말 상상이상으로 많은 곳에 활용 할 수가 있다.

직접 적인 활용은 실제 알고리즘을 공부하면서 몸소 체감하는 것이 가장 좋은 것 같다.

그래프의 구현

그래프의 구현은 크게 두가지로 나뉘어 진다.

1. 인접행렬(Adjacency Matrix)

2. 인접리스트(Adjacency List)

아래 그림으로 보면서 살펴보자.

우리가 표현하고 싶은 무방향, 가중치가 있는 그래프이다.

[인접 행렬로 표현]

1. 행과 열에 각각 정점의 번호를 순서대로 쓴다.

2. i행 j열에 i행에서 j열로 가는 간선(E)의 가중치를 쓴다.(가중치가 없다면 주로 1로 둔다.)

[인접 리스트로 표현]

1. 각 정점의 중심점들을 순서대로 쓴다.

2. 각 정점에서 연결되는 정점이 있다면, 그 정점과 가중치를 가르키는 구조를 만들고 적어준다.

2가지 표현법에 대해서 장단점이 존재를 하는데 알아두는 것이 좋다.

인접 행렬의 경우 인접 리스트에 비해서, 

접근이 빠른 대신, 메모리의 낭비가 심하다.

인접 리스트의 경우 인접 행렬에 비해서,

접근이 느린 대신, 메모리의 낭비가 적다.

즉, 사용하는 목적에 맞춰서 어떤 구조를 이용해 그래프를 사용해야 하는지 적절하게 고르는 것이 중요하다.

개인적으로는 그래프의 간선이 많은경우 인접행렬을 이용하고, 간선이 적은 경우 인접리스트를 사용한다.

C++ 코드

이 코드들은 알고리즘 문제를 풀 때 주로 사용하는 방식이므로 완벽한 구현은 다른 자료구조 책을 참고하기 바란다.

#include <iostream>
#include <vector>
#include <tuple>
#define VSIZE 500
using namespace std;
 
int main() {
 
    int VertexN; //정점의 갯수
    int EdgeN;  //간선의 갯수
    cin >> VertexN >> EdgeN;
    vector<tuple<int, int, int>> Edge(EdgeN);
 
    //간선의 정보를 저장
    for (int i = 0; i < EdgeN; i++) {
        int A, B, W; //A에서 B로 W의 가중치를 가진다.
        scanf("%d %d",&A,&B,&W);
        Edge.push_back(make_tuple(A, B, W));
    }
    //인접행렬
    int graphMatrix[VSIZE + 1][VSIZE + 1]; //최대 갯수만큼미리 선언
    for (auto i : Edge) {
        int V1 = get<0>(i); //A
        int V2 = get<1>(i); //B
        int W = get<2>(i); //Weight
        //양방향 기록
        graphMatrix[V1][V2] = W;
        graphMatrix[V2][V1] = W;
    }
    
    //인접리스트
    vector<pair<int, int>> graphList[VSIZE + 1];
    for (auto i : Edge) {
        int V1 = get<0>(i); //A
        int V2 = get<1>(i); //B
        int W = get<2>(i); //Weight
                           //양방향 기록
        graphList[V1].push_back(make_pair(V2, W));
        graphList[V2].push_back(make_pair(V1, W));
    }
 
 
}
 

<깃허브 링크>

<위의 예제와 똑같은 Input>

3 3

1 2 10

1 3 20

2 3 30

위의 Input을 넣으면 예제와 똑같은 모양의 그래프를 만들 수 있다.