개념 - 그래프

하아아아아 시작해보자!

그래프

그래프는 항목간의 관계를 표현하는 자료구조다.

SNS상의 관계도, 전자회로의 연결구조 등 다양한 객체들이 서로 연결되어 있는 구조에서 사용된다. 

선형자료구조나 트리 등도 그래프의 한 종류로 볼 수도 있다.

그래프는 유명한 다리문제를 풀기 위해 오일러가 창안하였다.

그래프는 정점(vertex)와 간선(edge)의 집합이다. G = (V, E)처럼 표시할 수 있다. 

V(G)는 그래프 G의 정점 집합, E(G)는 간선 집합을 의미한다. 

정점은 노드node, 간선은 link라 불리기도 한다. 

그래프는 시각적으로 표현하기도 하지만, 이는 사람의 편의를 위함일 뿐이다. 

그래프의 종류

무방향 그래프 undirected graph: 

간선에 방향이 표시되지 않는다. 모든 간선이 양방향. (A, B)는 (B, A)와 같다. 

ex : V(G1) = {0,1,2,3}, E(G1) = {(0,1), (0,2), (0.3), (1.2), (2.3)}

방향 그래프 directed graph: 

간선에 방향성 존재. 화살표로 표시됨

A에서 B로만 갈 수 있는 간선은 <A, B>로 표시된다. <A, B>와 <B, A>는 서로 다른 간선이다.

ex : V(G3) = {0,1,2}, E(G3) = {<0,1>, <1,0>, <1,2>}

가중치 그래프 weighted graph

간선에 비용이나 가중치가 할당된 그래프. 네트워크라고도 불린다.

두 정점간의 연결 유무뿐만 아니라 연결의 강도까지 나타낼 수 있어 더 복잡해진다. ex : 지도

부분 그래프 subgraph

그래프 G를 구성하는 V(G)와 E(G)의 부분 집합으로 이루어진 그래프.

그래프의 용어

인접 정점 adjacent vertex

어떤 한 점에 대하여 간선에 의해 직접 연결된 다른 정점들

정점의 차수 degree

연결된 간선의 수를 말한다. 무방향 그래프에선 간선의 수가 곧 인접 정점의 수. 모든 정점의 차수를 합치면 간선 수의 2배.

방향 그래프에서 

외부에서 들어오는 간선의 수 : 진입 차수in-degree 

나가는 간선의 수 : 진출 차수out-degree

경로 path

간선을 따라 갈 수 있는 길. 정점의 나열. 

무방향 그래프에서 정점 s로부터 정점 e까지의 경로 : s, v1, v2, ... vk, e

나열된 정점들 간에는 간선 (s, v1), (v1, v2), ... (vk, e)가 존재해야 한다.

방향그래프라면 <v1, v2>, <v2, v3>, ... <vk, e>가 존재해야 한다.

경로의 길이 

경로를 구성하는데 사용된 간선의 수

단순경로 (simple path)와 사이클(cycle) 

단순 경로 : 경로 중에서 반복되는 간선이 없는 경로

사이클 : 시작 정점과 종료 정점이 같은 단순 경로

연결 그래프 connected graph

모든 정점에 경로가 존재하면 연결그래프. 아니면 비연결 그래프.

트리 tree

사이클을 가지지 않는 연결 그래프

완전 그래프 complete graph 

모든 정점 간에 간선이 존재하는 그래프.

무방향 완전 그래프의 정점 수를 n이라고 할 때, 하나의 정점은 자기를 제외한 n-1개의 정점과 연결된다.

따라서 총 간선의 수는 n * (n-1)/2

그래프의 ADT

객체 : 정점의 집합과 간선의 집합

연산 : create()

isEmpty()

insertVertex(v) : 정점 v 삽입

insertEdge(u, v) : 간선 (u,v) 삽입

deleteVertex(v)

deleteEdge(u, v)

adjacent(v) : 정점 v에 인접한 모든 정점의 집합 반환

그래프의 표현

배열을 사용하는 인접 행렬 (adjacency matrix)

연결 리스트를 사용하는 인접 리스트 (adjacency lift)

-> 각각의 장단점이 존재하므로, 문제의 특성에 따라 선택

인접 행렬

정점의 개수가 n일 때 n x n의 2차원 배열로 표현.

간선 (i, j) 가 존재하면  M[i][j] = 1, 없으면 M[i][j] = 0;

무방향 그래프 : 대칭 행렬이 된다. 상위 삼각이나 하위 삼각만 써서 메모리 절약 가능.

방향 그래프 : 일반적으로 대칭이 아니다.

가중치 그래프 : 각 항목의 의미가 달라짐. 간선이 없는 경우 0으로 처리시 문제 발생 가능

특징

n개의 정점을 가진 그래프의 표현에는 n^2의 메모리 공간이 필요함. 

두 정점을 연결하는 간선의 존재를 O(1)만에 알 수 있음. ex : M[i][j]

정점의 차수를 행이나 열을 조사하여 o(n)만에 알 수 있음. 즉 정점i의 차수는 i행의 합

인접 리스트

인접 리스트에서는 각 정점의 인접 정점에 대한 연결리스트를 배열로 갖는다. 정점의 번호를 통해 해당 정점의 인접 정점 연결 리스트을 얻을 수 있다.

특징

n개의 정점을 가지고 e개의 간선을 가진 그래프의 표현에 n개의 연결 리스트, n개의 헤드포인터, 2e개의 노드가 필요하다.

정점의 수에 비해 간선의 개수가 매우 적은 희소 그래프(sparse graph)의 표현에 적합하다.

간선 (i, j)가 있는지 알아보거나 정점 i의 차수를 알아보려면 해당 i의 연결리스트를 모두 살펴보아야 한다.

그래프에서 전체 간선의 수를 알아내려면 O(n + e) 연산이 필요하다.

그래프의 탐색

그래프의 탐색은 기본적으로 한 정점에서 시작해서 모든 정점을 한 번 씩 방문하는 것. 

깊이 우선 탐색과 너비 우선 탐색이 있다. 

깊이 우선 탐색 (depth first search, DFS)

스택을 통한 미로탐색과 비슷하다. 정해진 순서의 방향대로 우선 진행하다가 막히면 다음 순서의 방향으로 탐색하는 것이다.

그래프에서 탐색을 할 때는 방문한 정점에 표시를 해놔야 다음번에 방문하지 않는다. 

스택 또는 순환으로 구현할 수 있다.

정점의 수가 n이고 간선의 수가 e인 그래프를 깊이 우선 탐색할 때 인접 리스트라면 O(n+e), 인접 행렬이라면 O(n^2) 이다.

따라서 간선의 수가 적은 경우엔 인접 리스트를 사용하는 게 좋다.

너비 우선 탐색 (breadth first search, BFS)

큐를 활용한 미로탐색과 비슷하다. 우선 해당 노드에서 갈 수있는 노드부터 다 가보고 다음 노드를 탐색하는 것이다. 

DFS와 마찬가지로 인접 리스트의 경우 O(n+2), 인접 행렬의 경우 O(n^2)이 걸린다.

연결성분 connect component

연결 성분이란 한 그래프 안에서 최대로 연결된 부분 그래프를 말한다. 깊이 우선 탐색, 너비 우선 탐색 아무거나 써도 된다.

신장 트리 spanning tree

신장 트리란 그래프 내의 모든 정점을 포함하는 트리다. 사이클이 없어야 한다. 하나의 그래프에서는 많은 신장 트리가 있을 수 있다. DFS, BFS에 따라 결과가 달라진다. 

위상 정렬 topological sort

방향 그래프에서 존재하는 각 정점들의 선행 순서를 위반하지 않으면서 정점을 나열하는 것을 위상 정렬이라고 한다.