[알고리즘] 비선형구조의 탐색, 그래프의 구현

비선형구조의 탐색

---

비선형 구조란, i번째 원소를 탐색한 다음 그 원소와 연결된 다른 원소를 탐색하려고 할 때, 다음에 탐색할 수 있는 원소가 여러 개 존재하는 구조. 일반적으로 트리나 그래프 형태로 자료를 구성할 수 있을 때 해당됩니다.

이러한 트리나 그래프 형태의 모든 정점(값/데이터)을 탐색하는 것을 비선형구조의 탐색이라고 생각할 수 있습니다.

비선형구조는 탐색해야할 데이터가 순차적으로 구성되어있지 않습니다. 단순한 반복으로 탐색할 수가 없기 때문에 스택(stack)이나 큐(queue)와 같은 자료구조를 활용해 탐색할 방법과 순서를 만들어 탐색하는 것이 일반적입니다.

비선형구조의 대표적인 예 : 트리, 그래프

데이터가 저장되어있는 곳: 정점(vertex) / 노드(node)

데이터들을 연결시키는 사이의 선: 간선(edge) / 링크(link)

데이터들을 연결시키는 간선들은 화살표의 유무에 따라 양/단방향으로 표현되고, 간선들에는 어떤 가중치(weight)가 있을수도 있습니다.

어떤 임의의 정점 s에서 다른 정점 t까지 이동한다고 가정할 때, s에서 t로 이동하는데 사용한 간선들의 순서로 만들어지는 집합을 경로(path)라고 하며, 회로(cycle)는 그 경로에 순환이 생기는 경우를 의미합니다.

자기자신을 연결하는 간선: 자기간선(loop)

동일한 다른 정점과 여러 간선이 연결되는 경우: 다중간선(multi edge)

한 정점에서 다른 정점으로 연결되는 모든 간선의 수: 차수(degree)

그래프의 표현은 실제 세상에서의 많은 문제들을 간단하면서도 효과적으로 표현할 수 있는 방법으로, 프로그래밍을 활용한 문제해결에서 매우 자주 활용됩니다.

그래프 형태로 표현되는 문제 상황 또는 데이터 구조

각 정점들의 연결관계를 표현하기 위해 배열 구조를 사용하는 인접행렬(adjacency matrix)이나 리ㅏ스트 구조를 사용하는 인접리스트(adjacency list)로 구현할 수 있습니다.

입력 형식	입력 데이터의 예
첫번째 줄에 정점의 수 n과 간선의 수 m이 공백으로 구분되어 입력된다. 두번째 줄부터 m개의 줄에 걸쳐서 간선으로 연결된 두 정점의 번호와 가중치가 공백으로 구분되어 입력된다.	7 11  1 2 47  1 3 69  2 4 57  2 5 124  3 4 37  3 5 59  3 6 86  4 6 27  4 7 94  5 7 21  6 7 40

1. 인접행렬: 배열 구조의 정점의 데이터와 연결관계를 저장하는 가장 간단한 그래프 구현 방법

   <일반 연결 관계>

	1	2	3	4	5	6	7
1		1	1
2	1			1	1
3	1			1	1	1
4		1	1			1	1
5		1	1				1
6			1	1			1
7				1	1	1

   <가중치 연결 관계>

	1	2	3	4	5	6	7
1		47	69
2	47			57	124
3	69			37	59	86
4		57	37			27	94
5		124	59				21
6			86	27			40
7				94	21	40

2차원 배열을 이용해 그래프를 인접행렬의 형태로 저장하는 코드의 예

#include <stdio.h>

int n, m, G[101][101];

int main()
{
    scanf("%d %d", &n, &m);
    for(int i=0; i<m; i++)
    {
        int a, b, w;
        scanf("%d %d %d", &a, &b, &w);
        G[a][b] = G[b][a] = w;
    }
}

3: 그래프를 저장하기 위한 G[][]준비

12: 양방향 그래프인 경우의 저장, 가중치 w를 양방향으로 기록

2. 인접리스트: 어떤 정점에 연결된 다른 정점만, 리스트로 연결하는 그래프 구현 방법.

STL 라이브러리의 <vector>에 정의되어있는 std::vector 구조를 활용하는 것이 매우 편리

#include <vector>
std::vector<int> G[101];
int main()
{
    ...
    G[i].push_back(x);
    ...
}

1	2	47	3	69
2	1	47	4	57	5	124
3	1	69	4	37	5	59	6	86
4	2	57	3	37	6	27	7	94
5	2	124	3	59	7	21
6	3	86	4	27	7	40
7	4	94	5	21	6	40

인접리스트로 구현하면 인접행렬보다 탐색 시간을 줄일 수 있습니다. 인접행렬은 실제로 연결되지 않은 부분까지 저장해둬야하고 전체 할당된 행렬전체 범위를 탐색해야만 합니다. 하지만 인접리스트의 경우에는 연결된 부분밖에 없기때문에 이부분만 연결되 순서대로 따라가면서 탐색하면 됩니다.

인접행렬의 경우 : O(v*e)

인접리스트의 경우 : O(v+e)

비선형 구조는 어떤 데이터에 연결되어 이동할 수 있는 경우가 2개 이상으로 만들어질 수 있는 구조를 말하며 대표적으로 트리, 그래프가 있습니다. 그래프 구조를 저장하기 위해서는 배열을 이용한 인접행렬 방법이나 리스트(벡터 등)을 이용한 인접리스트 방법을 사용할 수 있습니다.

참고로 트리구조는 1차원배열에 순차적으로 저장하는 방법을 사용할 수 있습니다. 너비우선 탐색 저장 큐방식 처럼 저장하면 됩니다. 어떠한 트리에서 노드가 n번일때, 왼쪽 자식노드는 2*n 오른쪽 자식노드는 2*n + 1의 관계를 가지게 되기 때문입니다.