티스토리 뷰

알고리즘/그래프

그래프

로또_ 2019. 12. 18. 17:21

그래프란?

그래프란, 객체(사물 또는 추상적 개념)들과 객체들 사이의 연결관계를 표현합니다. 예를 들면 지하철에서 다른 역으로 가는 최단 경로를 찾아주는 서비스도 그래프 알고리즘을 사용합니다(무향 그래프).또한, 정점(Vertex)들의 집합과 정점을 연결하는 간선(Edge)들의 집합으로 구성된 자료구조입니다. 다음과 같이 그래프를 표현할 수 있습니다. G = (V, E), V = 정점들의 집합, E = 간선들의 집합. V개의 정점을 가지는 그래프는 최대 V(V -1)/2 개의 간선이 가능합니다.

선형 자료구조나 트리 자료구조로 표현하기 어려운 N:N 관계를 가지는 원소들을 표현하기에 용이합니다.

그래프와 트리의 차이

무향 그래프, 유향 그래프

무향그래프는 친구관계와 같이 상호 대칭적인 관계를 나타내고, 유향 그래프는 상호 대칭적이지 않고 작업 순서와 같이 선후 관계나 의존 관계등을 표현하기에 적합합니다(기업간의 공급관계).

무향 그래프에서 모든 정점쌍에 대해 항상 경로가 존재하면 연결 그래프(Connected Graph), 적어도 하나의 정점쌍에서 경로가 존재하지 않는다면 비연결 그래프(Disconnected Graph)라고 부릅니다. 만약 그래프에 속해 있는 모든 정점이 서로 연결되어 있다면, 그 그래프는 완전 그래프(Complete Graph)라고 부릅니다.

번외로 경로중에서 반복되는 정점이 없는 경우는 단순 경로(simple path)라고 하는데, 이 때 단순 경로의 시작 정점과 종료 정점이 동일한 경우를 사이클(cycle)이라고 부릅니다. 두 정점에 최대 한 개의 간선만 있는 그래프는 단순 그래프(simple graph)라고 부릅니다.

인접

무향 그래프에서 두 정점 u, v 사이에 간선이 존재하면 두 정점은 서로 인접해있다고 합니다. 유향 그래프에서는 정점 u에서 정점 v로 나가는 간선이 존재하면, u는 v에 인접하지만 v는 u에 인접해 있지 않습니다.

가중치 그래프(네트워크)

간선에 가중치를 가질 수 있습니다. 가중치 그래프는 어떤 성질을 가지고 있냐에 따라서 유향 및 무향 그래프가 될 수 있습니다.

그래프 표현

그래프 문제를 계산하기 위해서는 데이터로 저장해야 합니다. 그래프 표현 방법은 다음과 같습니다.

1. 인접행렬(Adjacent Matrix)

2. 인접 리스트(Adjacent List)

3. 간선 리스트(Edge List)

1. 인접행렬

V x V 만큼의 메모리가 필요하므로 V가 너무 커지면 메모리 효율성이 떨어집니다. 만약 탐색하게 된다면 필요 하지 않는

구간을 탐색하는 현상을 볼 수 있습니다.

간선이 많이 존재하는 밀집 그래프(Dense Graphe)를 표현하는 데에는 적합하나 희소 그래프(Sparse Graph)에는 메모리 낭비가 크므로 적합하지 않습니다. 인접 행렬을 이용하면 두 정점을 연결하는 간선의 존재 여부를 O(1)으로 즉시 알 수 있다는 장점이 있습니다. 그러나 그래프에 존재하는 모든 간선의 수를 알아내려면 인접행렬 전체를 조사해야 하므로 N^2번의 조사가 필요하게 되어O(N^2)의 시간이 요구됩니다.

다중 그래프에서는 인접 행렬이 가능하지 않습니다.

관련문제 : 미로탐색(해결) : https://www.acmicpc.net/problem/2178

섬의갯수(해결) : https://www.acmicpc.net/problem/4963

단지번호 붙이기(해결) : https://www.acmicpc.net/problem/2667

무향 그래프

정점 i, j에 간선이 있으면 (i행, j열)과 (j행, i열)에 1을 저장합니다.
두 정점 사이에 간선이 없으면 0을 저장합니다.
그림에서 5번 정점의 인접 정점들은 2, 6, 7입니다.
5번 행의 2, 6, 7열과 5 열의 2, 6, 7행에도 1이 저장됩니다.
무향 그래프를 인접 행렬로 저장하면 2E 만큼 1이 저장됩니다.( 해당 메모리에 2E번 접근하게 됩니다.)

유향 그래프

정점에서 나가는 간선의 수를 그 정점의 진출 차수(out degree)라 하고 들어오는 간선의 수를 진입 차수(in degree)라고 합니다.
정점 v의 진입차수는 v열에 저장된 1의 개수이고, 진출 차수는 v행에 저장된 1의 개수입니다.

2.인접 리스트

그래프를 인접 리스트로 저장하기 위해 연결 리스트(Linked List)를 사용합니다. 각 정점의 인접 정점들을 연결 리스트로 저장합니다. 따라서 정점의 수 만큼만 연결 리스트가 필요합니다.

인접 정점은 하나의 노드로 저장됩니다.
가중치 그래프일 경우 가중치 정보도 노드에 포함합니다.

c++로 코딩할땐 도착 노드와 가중치를 pair<vertex, weight>에 담아 사용할 수 있습니다. 전체 구조로 본다면

vector<vector<pair<vertex, weight>>>으로 설정할 수 있습니다.

3.간선 리스트

임의의 두 정점 u, v의 간선은(u, v)쌍으로 표현 할 수 있습니다. 간선 리스트는 간선에 대응하는 두 정점쌍을 저장하는 방법입니다. 이는 정점의 수에 비해 간선의 수가 매우 작을 때 사용하기도 합니다.

그래프 탐색

1. 깊이 우선 탐색(DFS : Depth First Search)

루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법
넓게(wide) 탐색하기 전에 깊게(Deep) 탐색하는 것입니다.
모든 노드를 방문하고자 하는 경우 이 방법을 선택합니다.
깊이 우선 탐색은 그래프의 모든 간선을 조사하므로 정점의 수가 n이고 간선의 수가 e인 그래프가 인접 리스트로 표현되어 있다면 O(n + e)이고, 인접 행렬로 표시되어 있다면 O(n^2)입니다.
순환 호출 또는 스택을 사용합니다.

관련문제 : DFS와BFS(해결) : https://www.acmicpc.net/problem/1260