탐색기반 알고리즘 설계_2.비선형구조탐색

2. 비선형 구조 탐색

 - i번째 원소를 탐색한 다음 그 원소와 연결된 다른 원소를 탐색하려고 할 때, 여러 개의 원소가 존재하는 탐색구조
 - 자료가 트리나 그래프로 구성되어 있을 경우 비선형구조, 이를 모두 탐색하는 것을 비선형 탐색이라 함.
 - 선형과 달리 자료가 순차적이지 않아 단순히 반복문을 이용하여 탐색하기에는 어려움
 - 스택이나 큐와 같은 자료구조를 활용하여 탐색하는 것이 일반적.

-일반적으로 깊이우선탐색(depth first search, dfs)과 너비우선탐색(breadth firrth search, bfs)으로 나뉨.

 (1) 비선형구조 : 그래프의 구성

- 트리를 이루는 기본 요소를 정점(vertex)과 간선(edge)라 한다.

- 원은 정점, 선분은 간선
- a-b 보통간선
- b-c 방향간선
- b-d 가중치 15, 양방향 간선
- d-e 가중치 7 일방통행 간선(방향간선)

     - 경로 : s->t로 이동 시 사용한 정점들을 연결하고 있는 간선들의 순서

- 회로 : 그래프에서 임의의 정점 s에서 같은 정점 s로의 경로들

-자기간선(loop)과 다중간선(multi edge)

- 차수(degree) : 한 정점에서 다른 정점으로 연결된 간선의 수, 차수

(2) 그래프의 구현 

  1) 인접행렬(adjacency matrix)

 - 문제에서 일반적으로 정점의 수, 간선의 수, 각 간선들이 연결하고 있는 정점 2개로 이루어진 정보가 주어짐.

 - 그래프의 일반적인 입력데이터의 형식은 다음과 같다

- 인접행렬의 구현, 가중치가 없는 표현

	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
5		124	59				94
6			86	27			40
7				94	21	40

-소스코드

#include<iostream>
 
using namespace std;
 
int n, m, arr[101][101];
 
int main()
{
    cin >> n >> m;
 
    for (int i = 0; i < m; i++)
    {
        int a, b, w;
        cin >> a >> b >> w;
        arr[a][b] = arr[b][a] = w;
    }
 
    for (int y = 1; y <= n; y++)
    {
        for (int x = 1; x <= n; x++)
        {
            cout << arr[y][x]<<" ";
        }
        cout << endl;
    }
 
    return 0;
}
 
/*
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
*/

*인접행렬로 표현하면 연결되지 않았던 부분까지 모두 표현된다. 즉 각 칸에 0은 연결되지 않은 부분을 의미하는데, 일반적인 그래프에서 행렬상에서 0이라고 표현되는 부분이 많을 가능성이 크다.

 -> 알고리즘 구현시에도 0이라고 표시된 부분까지 모두 조사를 해야하므로 효율이 떨어지는 경우가 존재. 이러한 단점을 극복하기 위해 제안된 방법이 인접리스트이고 이 방법은 인접행렬에서 0으로 표시된 부분은 저장하지 않으므로 효율을 높인다.

2) 인접리스트(adjacency list)

 - 인접리스트를 사용하면 인접행렬로 구현하는 것보다 공간을 적게 사용, 따라서 전체탐색법을 구현할 때 당연히 탐색시간도 줄일 수 있다.