Graph에 대해 정리해보자.

Graph란 자료구조의 일종으로서 

정점(Node,vertex)과 간선(Edge)으로 이루어져 있다. G = (V,E) 이렇게 표현을 한다.

이러한 그래프들은 방향이 있는 그래프(유향 그래프)와 방향이 없는 그래프(무향 그래프)로 나눌 수 있다.

때때로 간선에 가중치가 주어질 수 있는데 A에서 B 로 이동하는 거리, 이동하는데 걸리는 시간등을 표현할 수 있다.

그래프를 표현할 수 있는 방법은 두가지 정도로 나누어 볼 수있다.

1) 인접 행렬을 이용한 표현

2) 인접 리스트를 이용한 표현

인접 행렬을 이용한 표현의 경우에는 

위의 사진처럼 2차원 배열에 각각의 연결성을 따지는 것이다.

코드로 표현하자면 

for (int i=0; i<m; i++) {

        int u,v;

        scanf("%d %d",&u,&v);

        a[u][v] = a[v][u] = 1;

    }

이런식으로 표현을 할 수 있게 된다.  위의 코드는 무향그래프의 경우에 대한 코드이고 유향그래프의 경우에는 a[v][u]가 빠져야 할 것이다.

지금은 각각의 가중치를 1로 두었지만 각각의 간선에 가중치가 생기게 되면 2차원배열의 값에 그 가중치를 넣어주는 방식으로 코딩을 하면 된다.

이번에는 인접 리스트에 대해 설명을 해보자.

인접리스트의 경우 Linked list를 통해 구현을 하며 A[i] 는 i와 연결된 정점을 list로 구현한 것이다. 그러니 list의 경우 구현하는데 오랜 시간이 걸리기 때문에 

보통 vector와 같이 길이를 변경할 수 있는 배열을 이용해 구현하는 경우가 대부분이다.

이러한것처럼 각각의 배열백터에 각각의 연결성을 표현하게된다. 코드로 표현을 하게되면 

for (int i=0; i<m; i++) {

        int u,v;

        scanf("%d %d",&u,&v);

        a[u].push_back(v); a[v].push_back(u);

}

이러한 코드가 될 것이다. 그런데 위의 코드는 간선의 가중치가 1인 경우의 코드이다. 그렇다면 가중치가 달라지는 경우 어떻게 표현을 해야할까??

생각을 해보도록 하자 ......

해보았는가?? (물론 안해보았겠지만....ㅋㅋ) 바로 pair형 vector를 통해 표현할 수 있을것이다.

 vector<pair<int,int>> a;

    for (int i=0; i<m; i++) {

        int u,v,w;

        scanf("%d %d %d",&u,&v,&w);

        a[u].push_back(make_pair(v,w)); a[v].push_back(make_pair(u,w));

    }

코드로 표현하면 이렇게 될것이다.

인접 행렬과 인접 리스트의 각각의 공간 복잡도는 

1) 인접 행렬의 경우 정점의 개수^2 만큼 필요하므로 O(V^2)

2) 인접 리스트의 경우 있는 간선의 개수만큼 필요하게 되므로 O(E)가 될 것이다.

Graph에서 가장 중요하다고 볼수 있는 탐색의 경우 (BFS,DFS)는 알고리즘 항목에 따로 정리하도록 하겠다.

+) 추가적으로 연결요소에 대해 설명하도록 하겠다. 

연결요소란 위의 그래프처럼 그래프가 전부다 이어지지 않은 경우가 있을 수 있다. 그때 나누어짐 그래프들을 연결요소라고 한다.

연결요소를 구하는 방법은 ... 다 체크가 될때까지 DFS나 BFS를 해보면 될 것이다.