[중급-3]비선형구조의 탐색, 그래프의 구현

비선형 구조의 탐색:

비선형 구조 : i번째 원소를 탐색한다음 그 원소와 연결된 다른 원소를 탐색하려고 할 때, 다음에 탐색할 수 있는 원소가 여러개 존재하는 구조.

일반적으로 트리나 그래프 형태로 자료를 구성할 수 있을 때에 해당

비선형 구조는 단순한 반복으로 탐색할 수 없어서 스택이나 큐같은 자료구조를 통해 탐색방법과 순서를 만들어 탐색한다.

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

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

자기자신을 연결 : 자기간선

동일한 정점과 연결 : 다중간선

모든 간선의 수 : 차수

그래프의 구현 : 

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

인접 행렬 : 

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

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

#include <stdio.h>
 
int n, m, G[101][101];
 
int main(){
    int a, b, w, i;
    scanf("%d %d", &n, &m);
    for(i=0; i<m; ++i){
        scanf("%d %d %d", &a, &b, &w);
        G[a][b]=G[b][a]=w;
    }
}

인접 리스트 : 

std::vector구조 활용

장점 : 인접행렬보다 탐색시간을 줄일 수 있다.