비선형 구조의 탐색

비선형 구조

이번 글은 비선형 구조란 무엇이고 탐색하는 대표적인 방법, 그래프 구현 방법을 설명한다.

Reference> 트리, 그래프

비선형 구조란?

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

비선형 구조에서 탐색 방법

주로 트리나 그래프가 비선형 구조의 대표적인 형태이다.

비선형 구조는 데이터가 순차적으로 있지 않기 때문에 스택이나 큐를 이용해서 탐색을 한다.

비선형 구조에서 키워드

• 데이터가 있는 곳: 노드(node)/정점(vertex)
• 데이터를 잇는 선: 간선(edge)/링크(link)

간선은 화살표 유무에 따라 양/단방향으로 표현 가능하고, 간선에는 가중치가 있을 수 있다.

• 정점 b에서 정점 e까지 이동하는데 사용된 간선들의 순서대로 만들어지는 집합을 경로라고 한다.
• 회로(cycle): 경로에 순환이 생기는 것
• 자기간선(loop): 자기자신을 연결하는 간선
• 다중간선(multi edge): 동일한 다른 정점과 여러 간선이 연결되는 경우
• 차수(degree): 한 정점에서 다른 정점으로 가는 모든 간선의 수

그래프 구현 방법

그래프 구현 방법에는 각 정점들의 관계들을 나타내기 위해서 데이터 구조를 쓰는데, 인접행렬과 인접리스트 방식이 있다.

인접행렬은 2차원 배열에 정점들의 관계를 적어주면 된다.
인접리스트는 리스트에 관계를 적어주면 된다.

1. 인접행렬(adjacency matrix)

• 특징
  • 양방향 그래프 일 때, 행렬에 대칭성이 나타난다.
• 장점
  • 구현이 쉽다.
• 단점
  • 메모리 낭비가 심하다.
  • 인접리스트에 비해 속도가 느리다.

구현 방법

#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; // 양방향 그래프 일때
    }
}

2. 인접리스트(adjacency list)

• 장점
  • 속도가 인접행렬보다 빠르다.
• 단점
  • 구현이 STL 안 쓰면 인접행렬보다 어렵다. - 하지만 Vector를 쓰면 쉽다.

구현 방법(양방향 그래프 기준으로 작성됨)

#include <vector>
struct V
{
    int w; // weight
    int next;
};
std::vector<V> G[101];
int n, m;
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].push_back({w, b});
        G[b].push_back({w, a});
    }
}

시간 복잡도 비교
인접 행렬: O(V*E) < 인접 리스트: O(V+E)

 

 

더 읽어 볼만한 주제

• BFS
• DFS