[Algorithm] 그래프(Graph)

[Algorithm] 그래프(Graph)

 

용어

 

 

그래프(Graph) : 정점(Node / Vertex)과 간선(Edge)으로 이루어진 자료구조

차수(degree) : 각 정점에 연결된 간선의 개수

루프(loop) : 한 정점에서 시작해 같은 정점으로 들어오는 간선

가중치 그래프(Weighted Graph) : 간선에 가중치가 표기된 그래프

무방향 그래프(Undirected Graph) : 그래프의 간선에 방향성이 없을 경우

방향 그래프(Directed Graph) : 그래프의 간선에 방향성이 있을 경우. 이때 자신에게서 나가는 간선을 outdegree, 들어오는 간선을 indegree라고 부름.

사이클(Cycle) : 임의의 한 점에서 출발해 자기 자신으로 돌아올 수 있는 경로를 사이클이라고 부름.

Cyclic Graph : 그래프 내에 사이클이 존재하는 그래프

Acyclic Graph : 그래프 내에 사이클이 존재하지 않는 그래프

완전 그래프(Complete Graph) : 모든 서로 다른 두 정점 쌍이 간선으로 연결된 그래프

연결 요소(Connected Component) : 그래프 G에서 정점과 간선이 서로 겹치지 않는(independent) 부그래프를 G의 요소(component)라고 하는데 이들 요소 가운데 요소내 모든 노드쌍에 대해 경로가 존재하는 부그래프 S를 G의 연결요소라고 함.

연결 그래프(Connected Graph) : 임의의 두 정점 사이에 경로가 존재하는 그래프. 하나의 연결요소만 가짐.

단순 그래프(Simple Graph) : 두 정점 사이의 간선이 1개 이하이고 루프가 존재하지 않는 그래프

 

 

그래프의 표현법

 

1. 인접 행렬(Adjacency Matrix)

 

- 각 정점에 번호가 붙어있다고 할 때, 연결된 두 정점에는 1을, 연결되지 않은 두 정점에는 0을 준 행렬.

- 그래프가 Undirected graph이면 대각선에 대해 대칭인 행렬이 나옴.

- 엄밀히 말해서 두 점을 잇는 간선이 여러 개일 경우 문제가 생길 수 있지만 일반적으로는 대부분의 문제에서 주어지는 그래프는 단순 그래프.

- 정점이 V개이고 간선이 E개일 때 어떤 두 점이 연결되어 있는지는 O(1)에 알수 있음.

- 가로와 세로가 각각 V인 2차원 배열이 필요하니 O(V2)(제곱)의 공간이 필요함.

- 어떤 점에 연결되어있는 모든 정점의 목록을 알아내고 싶을 때 시간 복잡도는 O(v).

- (EX) (2,3)이 1이라는 의미는 2에서 3으로 가는 간선이 있다는 의미.

 

 

2. 인접 리스트(Adjacency List)

 

 

- V개의 리스트를 만들어 각 리스트에 연결된 정점을 넣은 리스트.

- 인접 행렬과 비교했을 대 V가 크고 E가 상대적으로 작은 상황에서 공간을 절약할 수 있는 방식.

- O(V + E)의 공간이 필요 (리스트 V개 + 간선이 1개 있을 때마다 directed graph일 때는 특정 리스트 1개에 원소가 1개 추가되고 undirected graph일 때는 특정 리스트 2개에 원소가 1개씩 추가됨을 생각하면 모든 리스트에서 원소의 갯수의 총합은 directed graph일 때 E개, undirected graph일 때 2E개 이기 때문)

- 어떤 점에 연결되어있는 모든 정점의 목록을 알아내고 싶을 때 시간 복잡도는 O(V)대신 딱 갯수만큼 필요.

- STL vector를 사용해서 구현.

- STL을 쓸 수 없는 환경일 경우 일단 간선의 목록을 입력받으며 차수를 미리 세놓고, 이후 차수에 맞게 동적 배여을 할당하여 구현.

 

 

3. 비교( 인접 행렬 vs 인접 리스트)

 

	인접 행렬	인접 리스트
공간 복잡도	O(V2) (제곱)	O(V+E)
정점 u, v가 연결되어 있는지 확인하는 시간 복잡도	O(1)	O(min(deg(u),deg(v))
정점 v와 연결된 모든 정점을 확인하는 시간 복잡도	O(V)	O(deg(v))
효율적인 상황	두 점의 연결여부를 자주 확인할때 E가 V제곱에 가까울때	특정 정점에 연결된 모든 정점을 자주 확인할 때 E가 V제곱보다 훨씬 작을 때

 

 

 

BFS & DFS에 적용 (BFS, DFS)

1. BFS

- 2차원 배열에서 BFS를 할 때와 다른점은 그래프에서는 연결된 모든 정점을 살펴본다는 점.

- 만약 그래프가 Directed Graph일 때는 자신으로부터 나가는 간선으로 연결된 점들만 살펴보면 됨.

- 인접 행렬의 경우 한정점을 체크할때 나머지 모든 정점 V개를 보는데 그 정점이 V개 있으므로 O(V제곱).

- 인접 리스트의 경우 각 정점들이 큐에 정확히 1번 들어가므로 V, 각 정점에 연결된 정점을 살펴봐야하므로 간선의 개수 E, 즉 O(V+E)이다.

 

 

2. DFS

- BFS와 크게 다르지 않음. stack을 사용.

- 재귀로 구현하는 경우 재귀적으로 함수를 호출하는 것 자체가 자연스럽게 스택을 이용하는 모양새가 되기 때문에 별도로 스택을 선언할 필요가 없음.

- 단 STL로 stack을 구현하는 대신 재귀적으로 구현을 한다면 스택 메모리의 제한이 작은 경우에는 문제가 있음. 스택 영역의 메모리가 256MB나 512MB일 경우에는 제한에 걸리지 않지만 1MB로 제한이 될 경우 런타임에러가 발생함.

- 비재귀 DFS는 순회를 잘 수행하지만 우리가 관념적으로 생각하는 DFS와 세부동작이 다름.

 

참고

https://blog.encrypted.gg/908?category=773649