🤔 목적
컴퓨터공학의 기초가 되는 cs지식을 되새기면서 이 후 있을 기술면접을 대비 하고자한다.
그래프(Graph)란?
단순히 노드(node,N)와 그래프를 연결하는 간선(edge, E)을 하나로 모아놓은 자료구조
즉, 연결되어 있는 객체 간의 관계를 표현할 수 있는 자료구조이다.
그래프(Graph)의 용어 정리
- 정점(vertex): 위치라는 개념. (node 라고도 부름)
- 간선(edge): 위치 간의 관계. 즉, 노드를 연결하는 선 (link, branch 라고도 부름)
- 인접 정점(adjacent vertex): 간선에 의 해 직접 연결된 정점
- 정점의 차수(degree): 무방향 그래프에서 하나의 정점에 인접한 정점의 수
- 무방향 그래프에 존재하는 정점의 모든 차수의 합 = 그래프의 간선 수의 2배
- 진입 차수(in-degree): 방향 그래프에서 외부에서 오는 간선의 수 (내차수 라고도 부름)
- 진출 차수(out-degree): 방향 그래픙에서 외부로 향하는 간선의 수 (외차수 라고도 부름)
- 방향 그래프에 있는 정점의 진입 차수 또는 진출 차수의 합 = 방향 그래프의 간선의 수(내차수 + 외차수)
- 경로 길이(path length): 경로를 구성하는 데 사용된 간선의 수
- 단순 경로(simple path): 경로 중에서 반복되는 정점이 없는 경우
- 사이클(cycle): 단순 경로의 시작 정점과 종료 정점이 동일한 경우
그래프(Graph)의 특징
- 그래프는 네트워크 모델 이다.
- 2개 이상의 경로가 가능하다.
- 즉, 노드들 사이에 무방향/방향에서 양방향 경로를 가질 수 있다.
- self-loop 뿐 아니라 loop/circuit 모두 가능하다.
- 루트 노드라는 개념이 없다.
- 부모-자식 관계라는 개념이 없다.
- 순회는 DFS나 BFS로 이루어진다.
- 그래프는 순환(Cyclic) 혹은 비순환(Acyclic)이다.
- 그래프는 크게 방향 그래프와 무방향 그래프가 있다.
- 간선의 유무는 그래프에 따라 다르다.
그래프(Graph)의 종류
무방향 그래프 VS 방향 그래프
무방향 그래프(Undirected Graph)
- 무방향 그래프의 간선은 간선을 통해서 양 방향으로 갈 수 있다.
- 정점 A와 정점 B를 연결하는 간선은 (A, B)와 같이 정점의 쌍으로 표현한다.
- (A, B)는 (B, A) 동일
- Ex) 양방향 통행 도로
방향 그래프(Directed Graph)
- 간선에 방향성이 존재하는 그래프
- A -> B로만 갈 수 있는 간선은 <A, B>로 표시한다.
- <A, B>는 <B, A>는 다름
- Ex) 일방 통행
가중치 그래프(Weighted Graph)
간선에 비용이나 가중치가 할당된 그래프
‘네트워크(Network)’ 라고도 한다.
Ex) 도시-도시의 연결, 도로의 길이, 회로 소자의 용량, 통신망의 사용료 등
연결 그래프 VS 비연결 그래프
연결 그래프(Connected Graph)
- 무방향 그래프에 있는 모든 정점쌍에 대해서 항상 경로가 존재하는 경우
- Ex) 트리(Tree): 사이클을 가지지 않는 연결 그래프
비연결 그래프(Disconnected Graph)
- 무방향 그래프에서 특정 정점쌍 사이에 경로가 존재하지 않는 경우
사이클 VS 비순환 그래프
사이클(Cycle)
- 단순 경로의 시작 정점과 종료 정점이 동일한 경우
- 단순 경로(Simple Path): 경로 중에서 반복되는 정점이 없는 경우
비순환 그래프(Acyclic Graph)
- 사이클이 없는 그래프
완전 그래프(Complete Graph)
- 그래프에 속해 있는 모든 정점이 서로 연결되어 있는 그래프
- 무방향 완전 그래프
- 정점 수: n이면 간선의 수: n * (n-1) / 2
그래프(Graph)를 구현하는 두 방법
인접 행렬 (adjacent matrix) : 정방 행렬을 사용하는 방법
해당하는 위치의 value 값을 통해서 vertex 간의 연결 관계를 O(1) 으로 파악할 수 있다. Edge 개수와는 무관하게 V^2 의 Space Complexity 를 갖는다. Dense graph 를 표현할 때 적절할 방법이다.
인접 리스트 (adjacent list) : 연결 리스트를 사용하는 방법
vertex 의 adjacent list 를 확인해봐야 하므로 vertex 간 연결되어있는지 확인하는데 오래 걸린다. Space Complexity 는 O(E + V)이다. Sparse graph 를 표현하는데 적당한 방법이다.
그래프(Graph) 탐색
그래프는 정점의 구성 뿐만 아니라 간선의 연결에도 규칙이 존재하지 않기 때문에 탐색이 복잡하다. 따라서 그래프의 모든 정점을 탐색하기 위한 방법은 다음의 두 가지 알고리즘을 기반으로 한다.
깊이 우선 탐색 (Depth First Search: DFS)
그래프 상에 존재하는 임의의 한 정점으로부터 연결되어 있는 한 정점으로만 나아간다라는 방법을 우선으로 탐색한다. 일단 연결된 정점으로 탐색하는 것이다. 연결할 수 있는 정점이 있을 때까지 계속 연결하다가 더이상 연결되지 않은 정점이 없으면 바로 그 전 단계의 정점으로 돌아가서 연결할 수 있는 정점이 있는지 살펴봐야 할 것이다. 갔던 길을 되돌아 오는 상황이 존재하는 미로찾기처럼 구성하면 되는 것이다. 어떤 자료구조를 사용해야할까? 바로 Stack 이다. Time Complexity : O(V+E) … vertex 개수 + edge 개수
너비 우선 탐색 (Breadth First Search: BFS)
그래프 상에 존재하는 임의의 한 정점으로부터 연결되어 있는 모든 정점으로 나아간다. Tree 에서의 Level Order Traversal 형식으로 진행되는 것이다. BFS 에서는 자료구조로 Queue 를 사용한다. 연락을 취할 정점의 순서를 기록하기 위한 것이다. 우선, 탐색을 시작하는 정점을 Queue 에 넣는다.(enqueue) 그리고 dequeue 를 하면서 dequeue 하는 정점과 간선으로 연결되어 있는 정점들을 enqueue 한다. 즉 vertex 들을 방문한 순서대로 queue 에 저장하는 방법을 사용하는 것이다. Time Complexity : O(V+E) … vertex 개수 + edge 개수 ! BFS 로 구한 경로는 최단 경로이다.
References (참고 자료)
