[그래프] Graph 1: 그래프의 표현과 정의

알고리즘 문제해결전략2

그래프파트 

1. 그래프

 

그래프는 객체들의 상호 관계를 표현하기 위해 고안된 자료 구조이다.

 

그래프는 현실 세계의 사물이나 추상적인 개념 간의 연결 관계를 표현한다.

 

트리와는 다르게 부모 자식 관계에 관한 제약이 없기 때문에 그래프는 트리보다 훨씬 다양한 구조를 표현할 수 있다.

 

 

 

2. 그래프의 정의

그래프 G(V, E)는 어떤 자료나 개념을 표현하는 정점(vertex)들의 집합 V와

이들을 연결하는 간선(edge)들의 집합 E로 구성된 자료 구조이다.

 

그래프는 정점들과 간선들로 정의되며,

정점의 위치 정보나 간선의 순서 등은 그래프의 정의에 포함되지 않는다.

 

 

 

 

3. 그래프의 종류

 

 

간선에 추가적인 속성을 부여

 

존재할 수 있는 간선이나 정점의 형태에 제약 가능

 

여러 속성을 함께 가지는 그래프도 있다(DAG)

 

방향그래프, 유향 그래프(directed graph)

방향 그래프에서는 각 간선이 방향이라는 새로운 속성을 갖는다.

u -> v

v -> u 

u 와 v 사이의 간선은 서로 다른 간선이다.

 

무향 그래프 (undirected graph)

간선에 방향이 없는 그래프이다.

 

가중치 그래프 (weighted graph)

가중치 그래프(weighted graph) 는 weight라고 불리는 실수 속성을 부여한다.

 

이는 다양한 정보를 표현하는데 사용한다.

 

최소 스패닝 트리. 최단 경로 문제에서 자주 볼 수 있는 형태이다.

 

다중 그래프(multigraph)

다중 그래프는 두 정점 사이에 두 개 이상의 간선이 있을 수 있는 그래프를 말한다.

 

단순 그래프(simple graph)

반대로 최대 간선이 한개있는 그래프를 단순 그래프(simple graph)라고 한다.

 

 

루트 없는 트리 (unrooted tree)

부모 자식 관계 없는 트리와 같은 무향 그래프

간선을 통해 두 정점을 잇는 방법이 딱 하나.

 

- 정확히 V-1개의 간선이 있다

- 사이클이 존재하지 않는다

- 두정점 사이를 연결하는 단순 경로가 정확히 하나 있다.

 

이 조건들은 모두 동치로 한조건이라도 성립할 경우 다른 조건들이 모두 성립하게 된다.

 

루트 없는 트리: 지배집합 찾기(dominating set)

 

이분 그래프(bipartite graph)

 

그래프의 정점들을 겹치지 않는 두 개의 그룹으로 나눠서

서로 다른 그룹에 속한 정점들 간에만 간선이 존재하도록

만들 수 있는 그래프를 말한다

 

 

사이클 없는 방향 그래프 (directed acyclic graph, DAG)

한 점에서 출발해 자기 자신으로 돌아오는 경로(사이클)이 존재하지 않는 경우를 말한다.

이 그래프는 여러 작업들 간의 상호 의존 관계등을 그래프로 표현할 때 흔하게 출현한다.

위 그림에서 간선 0->6의 방향을 바꾸면 사이클이 존재하게 된다.

 

그래프의 경로 (path)

그래프에서 사용되는 가장 중요한 개념 중 하나가 바로 '경로'이다 

 

경로란 끝과 끝이 서로 연결된 간선들을 순서대로 나열한 것이다.

 

위 그림에선 0-2-3-6. / 0-2-3-7 등이 있다.

 

방향 그래프의 경우 앞 간선의 끝점이 뒷 간선의 시작점과 만나야한다.

 

경로 중 한 정점을 최대 한 번만 지나는 경로를 단순 경로(simple path)라고 부른다.

(방향그래프일 경우 사이클이 없는)

 

현대 그래프 이론에서는 경로는 대부분 단순 경로를 의미한다.

 

시작한 점에서 끝나는 경로를 사이클(cycle)혹은 회로라고 부른다.

 

 

 

 

4. 그래프의 사용 예

 

그래프는 현실 세계의 수많은 문제를 풀기 위해 이용된다.

 

철도망의 안전 분석

한 역이 폐쇄되어 열차가 지나지 못할 경우 철도망 전체가 두 개 이상으로 쪼개질 가능성이 있는지.

만약 있다면 어느 역이 그런 위험성이 있는지를 파악하는 문제이다.

 

역 = 정점

철로 = 간선

 

절단점 찾기 알고리즘을 이용하여 문제를 해결할 수 있다.

 

 

소셜 네트워크 분석

사람들 = 정점

관계도 = 간선

 

너비 우선 탐색으로 몇명이나 몇단계에서

간접적으로 관계되어있는지 파악할 수 있다.

 

 

인터넷 전송 속도 계산

컴퓨터, 라우터 = 정점

케이블 = 간선

 

최소 스패닝 트리 알고리즘을 응용하여 두 정점 간의 전송 용량을 계산할 수 있다.

 

한 붓 그리기

점 = 정점

연결선 = 간선

 

주어진 그래프의 모든 간선을 한 번씩만 지나는 경로를 찾는 문제가 됨.

오일러 경로(eulerian path)라고 부르며 이는 깊이 우선 탐색을 응용해서 해결할 수 있다.

외환 거래

달러->유로->엔->달러 수익 => 아비트러지(arbitrage)

환율목록 = 그래프

각 통화 = 정점

교환가능한 통화 = 간선

통화 간의 교환 비율 = 간선의 가중치

아비트러지가 있음 => 사이클의 가중치를 곱했을 때 1을 초과하는 값. =>로그=> 합 => -1곱 => 가중치의 합이 음수인 사이클

=> 최단 거리 알고리즘

 

 

 

 

5. 암시적 그래프 구조들 (implicit graph)

현실 세계에서 그래프 같은 형태를 갖는 구조가 아닌데도

그래프로 표현하면 쉽게 해결할 수 있는 문제들.

(알고리즘 문제해결전략에서 정의한것)

 

 

할일 목록 정리

서로 의존 관계에 있는 여러 할 일이 있을 때

순서를 계산하는 문제

=> 위상 정렬 (topological sorting)

=> dp

 

15-퍼즐

4*4 크기의 게임판에 1~15의 숫자의 타일이 15개가 섞여있고,

이들을 순서대로 정렬하는 문제

- 현재 타일의 배치 = 정점

- 한 배치에서 타일을 한 번 움직여 다른 배치를 얻을 수 있을 때 두 정점을 간선으로 연결하는 그래프

=> 그래프 상에서 두 점 사이를 잇는 가장 짧은 경로를 구하는 문제.

 

게임판 덮기

모든 칸에 블록을 덮는 문제.

게임판의 막히지 않은 각칸 = 정점

상하좌우로 인접한 칸들 사이 = 간선

=> 이분 그래프 => 이분 매칭 알고리즘

 

회의실 배정

회의실은 한번에 한팀만 이용가능, 원하는 시간을 두개씩 정할 때

모든 팀이 회의를 하게 해야하는 문제

= 만족성 문제(satisfiability problem)

= 모든 사람이 두 선택지 중 하나를 선택해야 하는 문제 2-SAT

= 강 결합성 문제

 

 

 

6. 그래프의 표현 방법

 

여러 객체들이 서로 연결되어 있다는 점에서 그래프는 트리와 별로 차이점은 없다

 

각 정점들 = 객체

연결된 점점들 = 정보의 목록

 

그러나 트리보다 그래프는 '정적인 용도' 로 사용된다.

 

정적이다 = 삽입 삭제가 드물다.

 

그러므로 대부분 그래프는 구조의 변경이 어렵더라도

좀더 간단하고 메모리를 적게 차지하는 방법으로 구현한다.

 

=> 객체들의 인스턴스로 표현 X

=> 배열에 각 정점의 정보를 저장. 인덱스로 접근

=> 그래프의 표현 방식은 간선의 정보를 어떤 식으로 저장하느냐에 따라 크게 두가지로 나뉜다.

 

 

 

인접 리스트 표현 (adjacency list)

 

인접 리스트 표현은 그래프의 각 정점마다 해당 정점에서 나가는 간선의 목록을 저장해서 그래프로 표현한다.

 

그래프는 각 정점마다 하나의 연결리스트를 갖는 방식으로 구현된다.

 

vector<list<int> > adjacent;

 

adjacent[i] 는 정점 i와 간선을 통해 연결된 정점들의 번호를 저장하는 연결 리스트이다.(동적 배열로 표현가능)

 

 

가중치 그래프 등 간선이 추가적 속성을 갖는 그래프의 표현

=> 간선의 정보를 구조체로 표현 or pair 사용

struct Edge {
    int vertex;
    int weight;
}

 

 

인접 행렬 표현 (adjacency matrix)

인접 리스트 표현의 큰 단점은 두 정점이 주어질 때 이 정점이 연결되어 있는지를 알기 위해서는

연결 리스트를 일일이 뒤져야 한다.

 

이와 같은 연산의 속도를 높인게 인접행렬 표현이다.

 

이러한 표현은 |V| X |V| 크기의 행렬, 즉 2차원 배열을 이용해 그래프의 간선 정보를 저장한다.

 

vector<vector<bool> > adjacent;

 

이때 adjacent[i, j]는 정점 i에서 정점 j로 가는 간선이 있는지를 나타내는 불린 값 변수이다.

 

가중치 그래프로 표현하는 방법은 그냥 정수나 실수변수를 저장하면 된다.

서로 연결되지 않은 점은 -1값을 넣는게 보통이다.

 

 

 

인접 행렬 표현과 인접 리스트 표현의 비교

한 표현의 장점은 한 표현의 단점이 된다. 이런 정반대 특성 때문에 적절한 표현방식을 취해야한다.

(시간복잡도에 영향이간다)

 

인접 행렬 장점:

 

두 정점을 잇는 간선이 있는지를 한번의 배열 접근만으로 확인할 수 잇다는 것이다.

 

인접 행렬 단점:

 

실제 간선의 개수와 관계없이 항상 O(|V|^2) 의 공간 복잡도를 가진다.

 

 

인접 리스트 장점:

 

|V| 개의 연결 리스트에 실제 간선 수만큼 원소가 들어 있으므로 O(|V| + |E|)의 공간 복잡도를 가진다.

보통 |V||V| 보다 적은 그래프가 많이 등장하므로 큰차이가 있는 것이다.

 

인접 리스트 단점:

 

두 정점을 잇는 간선이 있는지를 연결리스트에서 탐색해야한다,

 

 

 

희소 그래프 (sparse graph) => 인접 리스트

 

간선의 수가 |V||V| 에 비해 훨씬 적은 그래프이다.

 

밀집 그래프 (dense graph) => 인접 행렬

 

간선의 수가 |V||V| 에 비례하는 그래프이다.

 

 

 

 

암시적 그래프 표현

 

그래프 구조를 직접 사용하지 않고도 문제를 해결할 수 있다. 아래는 두가지의 예시이다.

 

 

열린 칸, 막힌 칸으로 구성된 미로에서 두 칸 A, B 사이의 최단 경로를 찾는 문제의 경우 열린칸 좌표를 정점으로 표현하고

간선 표현은 생략하고 미로 맵에서 상하좌우로 막혀있는지 열려있는지 판단하면

그래프로 변환하는 과정이 없어도 문제를 해결 할 수 있다.

 

다른 예로 그래프의 크기가 아주 큰데 실제로는 그중 일부만 사용하는 경우가 있다.

위에서 간단히 보았던 15-퍼즐 의 경우 모든 상태를 그래프로 표현하는 것 보다

조각들의 배치 상태를 정점으로 하는 암시적 그래프 표현을 통해 전체를 메모리에 올리지 않고

문제를 해결할 수 있는 것이다.

 

하지만 암시적 그래프 표현을 사용하게 되면, 

그래프를 사용하는 알고리즘과 변환 과정이 합쳐지게 되고, 이 과정에서 코드가 더 복잡해지기 때문이다.

따라서 그래프에 대해 복잡한 연산이나 알고리즘을 수행할거라면

미리 입력을 그래프로 변환해 전체 코드를 간결화 시킬 수 있다.

 

 

- 알고리즘 문제해결전략 811p

그래프 에디터 사이트