그래프에 대해 설명하세요
Keyword
정점(Vertex), 간선(edge), 방향성, 무방향성, 가중치, degree, cycle, 네트워크
Script
그래프는 vertex와 이를 연결하는 간선(edge)로 이루어져있는 자료구조입니다. 연결관계에 있어서 방향성이 있는 그래프와 방향성이 없는 그래프로 나눌 수 있습니다. 또, 간선의 가중치에 따라 가중치 그래프도 존재하고 모든 간선의 가중치가 동일한 그래프도 존재합니다. 그리고 각 vertex에 연결된 간선의 개수를 Degree라고 하며, 방향성 그래프에서는 각 vertex에서 나가는 간선의 개수를 OutDegree, 들어오는 간선의 개수를 InDegree라고 칭합니다. 그리고 cycle은 특정 vertex에서 시작해서 해당 vertex로 돌아오는 경우를 의미합니다.
그래프는 네트워크 연결 상태를 나타내기 위해 쓰이며, DFS나 BFS와 같은 탐색 알고리즘을 통해 탐색하기도 합니다.
Additional
추가 용어 정리
adjacent/incident
임의의 두 vertex가 하나의 Edge로 연결되어 있을 때, 각 vertex들은 서로 인접(adjacent)한다고 말한다. 이때 Edge는 두 vertex에 부속(incident)한다고 말한다.
loop/isolated
한 vertex에 같은 Edge가 부속(incident)할때를 loop라고 말한다.
반면 어떤 vertex에 부속(incident)한 Edge가 전혀 없을 때는 isolated vertex라고 한다.
isomorphic
두 그래프가 vertex 사이에 같은 mapping 구조를 가질 때, isomorphic이라고 말한다.
부분 그래프(subgraph)
특정 그래프의 vertex의 부분집합과 Edge의 부분집합으로 이루어진 그래프를 부분 그래프(subgraph)라고 말한다.
이러한 부분 그래프 중에서, 원 그래프의 모든 vertex를 가지며, 이를 사이클 형성 없이 모든 vertex를 연결한 것을 신장 트리(spanning tree)라고 한다. 신장 트리는 각 vertex간의 불필요한 관계 정보를 생략할 수 있다는 효율성을 가진다.
complete graph/multigraph
모든 vertex가 edge로 연결되어있어, edge의 수가 최대인 그래프를 완전 그래프(complete graph)라고 한다.
그리고 vertex 사이를 잇는 edge가 2개 이상일 경우, 해당 edge를 전이적(transitive)이라고 하며, 이러한 그래프를 multigraph라고 한다.
path
그래프에서 경로(path)는 인접한 vertex들로 구성된 sequence(1개 이상, 하나의 vertex도 시작과 끝이 같은 vertex로 path가 될 수 있음)이다. 경로의 길이는 경로 내에 존재하는 edge의 수를 의미한다.
simple path는 edge가 겹치지 않는 경로를 의미하고, vertex가 겹치지 않는 경로는 elementary하다고 말한다.
connected
임의의 두 vertex 사이에 경로가 존재한다면, 두 vertex는 connected이다.
- 모든 vertex쌍 사이에 경로가 존재하는 무방향그래프는 connected 그래프이다.
- 임의의 방향 그래프에서 방향을 무시하고 모든 vertex쌍 사이에 경로가 존재한다면, connected 그래프이다.
- 방향 그래프에서 임의의 모든 vertex쌍 a,b 사이에 a에서 b로 가는 경로와 b에서 a로 가는 경로가 존재한다면 강연결(strongly connected)이다.
연결 요소(connected component)
원 그래프의 sub 그래프 중에서 모든 vertex쌍에 대해 connected되어있는 sub 그래프를 connected component라고 한다. 그리고 이러한 부분 그래프들이 합집합을 이루어 원 그래프를 만들 수 있다면, 각 connected component를 파티션(partition)이라고 한다. 그리고 이 중 가장 vertex의 수가 많은 connected component를 최대연결요소(maximal connected component)라고 부른다.
[TODO] 강한 연결 요소
그래프 구현 방법
인접 행렬(adjacent matrix)
Node의 수보다 Edge의 수가 많은 dense graph를 나타낼 때 주로 사용하며, 정방 행렬을 통해 구현된다. 각 연결 관계를 index를 통해 접근할 수 있기 때문에, O(1)의 시간복잡도로 연결관계를 찾을 수 있다. 하지만 간선의 개수와는 무관하게 Node의 개수의 제곱에 해당하는 공간복잡도를 가지기 때문에, 간선이 많은 dense graph에서 적절한 그래프 구현 방법이다.
인접 리스트(adjacent list)
Node의 수가 Edge의 수보다 많은 sparse graph를 나타낼 때 주로 사용하며, linked list로 구현된다.
각 Node 간의 연결 정보는 linked list를 따라가며 확인해야해서 상대적으로 인접 행렬보다는 탐색에 더 많은 시간이 소요된다. 하지만 공간 복잡도는 O(Node의 개수+Edge의 개수)이기 때문에, 필요한 만큼의 메모리 공간을 사용한다.
