Goal
- 그래프가 무엇인지 설명할 수 있다
- 그래프 기본 용어에 대한 이해
- 특징에 따라 그래프를 구분지어 말할 수 있다
- 인접행렬, 인접 리스트에 대한 이해 (그래프 표현 방법에 대한 이해)
- 그래프 탐색에 대한 기본 이해 (DFS, BFS)
그래프(Graph)
정점(vertex/node)과 간선(edge/link)으로 구성된 자료구조
그래프(G) = 정점 집합(V) + 간선 집합(E)
수학적으로 그래프를 G = (V,E)와 같이 표현
- 정점(vertex / node) : 여러 가지 특성을 가질 수 있는 객체
- 간선(edge / link) : 정점들간의 관계
ex) 그래프 G1, G2가 있을 때 각각의 그래프의 정점과 간선은 다음과 같이 표시할 수 있다.
- V(G1), E(G1)
- V(G2), E(G2)
설명
정점과 간선은 집합이기 때문에 중복된 값을 가지지 않는다.
그래프는 꼭 연결되어 있을 필요도 없고, 간선이 반드시 서로 다른 두 정점을 연결해야 할 필요도 없다.
비선형 자료구조이다. 즉, 선형 자료구조와 다르게 하나의 원소 다음에 여러개의 원소가 올 수 있다. (1:M , 0 <= M)
참고) 그래프와 관련된 주제를 다루는 이론을 그래프 이론(Graph Theory)라고 한다. 그래프는 이산수학이나 조합론 등의 수학 분야에서도 다뤄지는 주제이다.
그래프 기본 용어
인접(adjacent) : 간선에 의해 두 정점이 연결되어 있을 경우 인접한다고 한다.
인접 정점(adjacent vertex) : 한 정점에 인접한 정점
차수(degree) : 정점에 연결된 간선의 수(정점이 부속하는 간선 수)
진입 차수(in-degree) : 해당 정점을 끝으로 하는 간선의 수(=내차수) => 외부에서 오는 간선 수
진출 차수(out-degree) : 해당 정점을 시작으로 하는 간선의 수 (=외차수) => 외부로 나가는 간선 수
루프(loop) : 간선 하나에 동일 노드가 연결(부속)되어 있는 경우
경로(path) : 간선을 따라 갈 수 있는 길. 정점의 나열로 표시
ex) <s,v1>, <v1, v2>, ... , <vk, e> 또는 (s, v1, v2, ... , vk, e) 와 같이 표시 (나열된 정점의 수 = 간선수 + 1)
나열된 정점 사이에는 반드시 간선이 존재해야한다. 즉, 나열된 정점 사이에 간선이 없을 경우 경로가 아니다
경로의 길이(path length) : 경로를 구성하는 간선의 수
단순 경로(simple path) : 중복 간선이 없는 경로
사이클(cycle) : 단순 경로의 시작과 종료 정점이 같은 경로 => 중복 간선이 없고 시작 노드와 마지막 노드가 같음
최단 경로(shortest path) : 두 정점 사이의 경로 중 가중치 또는 비용이 최소인 경로
두 정점 사이의 거리(distance) : 두 정점의 최단 경로의 경로의 길이 : d(u,v)
연결(Connected) : 두 정점 사이에 경로가 존재하면 연결 되었다고 한다.
용어에 대한 추가 설명
Order, Size
- Order : 그래프의 정점 개수
- Size : 그래프의 간선 개수
Maximum Size : n개의 정점을 갖는 그래프에서 가질 수 있는 최대 간선의 수
=> 𝑛(𝑛−1)/2 , n개의 정점이 각각 n-1개의 간선으로 이루어진 경우
차수의 표기
- 차수 표기 : deg(v)
- 진입차수 표기 : deg-(v)
- 진출차수 표기 : deg+(v)
isolated vertex / pendent vertex
- isolated vertex : 차수가 0인 정점
- pendent vertex : 차수가 1인 정점
인접(adjacent)과 부속(incident)
- 간선에 의해 두 정점이 연결되어 있을 경우 인접(adjacent)한다고 한다.
- 이때 두 정점은 간선에 부속(incident)한다고 표현한다.
- 인접은 두 정점사이의 관계를 표현한 것이고 부속은 간선과 정점 사이의 관계를 표현한 것이다.
Parallel Edges 와 Multi Graph
- Parallel Edges : e1 = e2 일 때, e1, e2를 각각을 Parallel Edge라 한다. (간선을 이루는 정점이 같은 간선)
- Multi Graph : Parallel Edge를 포함하는 그래프
Walk, Trace, Path
https://en.wikipedia.org/wiki/Path_(graph_theory)
시작노드와 끝 노드가 동일한지, 정점이 중복 가능한지, 간선이 중복 가능한지에 따라 여러가지 특징을 갖는다.
| 용어 | v1 = vn (시작노드=끝노드) |
정점 중복 가능 | 간선 중복 가능 |
| 보행(Walk) | -(상관없음) | O | O |
| 트레일(Trail) | - | O | X |
| 경로(Path) | - | X | X |
| 닫힌 보행(Closed Walk) | O | O | O |
| 닫힌 트레일 (Closed Trail =Circuit) |
O | O | X |
| 닫힌 경로 (Closed Path = Cycle) |
O | X | X |
위 내용을 정리하면 다음과 같다.
1. Walk : 인접 정점들의 나열
2. Trail : 중복되는 간선이 없는 Walk. (e1 ≠ e2) (단, 마지막 노드는 중복 가능)
3. Path : 중복되는 정점이 없는 Trail. (v1 ≠ v2) (단, 마지막 노드는 중복 가능)
집합으로 표현한 Walk, Trail, Path 간의 관계
- Walk ⊃ Trail ⊃ Path
Walk와 Path를 엄밀하게 구분해서 말하는 것이 아닌 경우, 일반적으로 경로는 Walk를 의미한다.
Open vs Closed
- Open : 시작 노드 ≠ 마지막 노드인 경우
- Closed : 시작 노드 = 마지막 노드인 경우
=> Walk, Trail, Path 각각 Oepn, Closed 상태가 존재
Circuit, Cycle
- Circuit : Closed Trail => 간선 중복을 허용하지 않는 닫힌 보행
- Cycle : Closed Path => 정점과 간선의 중복을 모두 허용하지 않는 닫힌 보행
=> Circuit ⊃ Cycle
Cycle 또는 Circuit이기 위해서는 Closed Walk여야 한다. (시작과 끝 정점이 같음)
또한, 간선의 중복을 모두 허용하지 않으므로 Trail이다.
Cycle은 정점의 중복도 허용하지 않으므로 Path이다.
단순 경로(Simple Path) 에서의 Path는 그래프 이론에서 말하는 Path가 아닌 Walk의 의미에서의 Path로 사용된다.
그래프 이론에서 봤을 때 Simple Path는 Trail과 같다.
Simple Path => Simple + Walk => Trail
Simple : 경로에서 중복 간선이 없는 경우 Simple 하다고 한다. => ex) Simple Path
Elementary : 경로에서 중복 노드가 없는 경우 elementary 하다고 한다
ex)
경로1 = [v1,v2,v3,v4,v3,v4]
경로2 = [v1,v2,v3,v4,v5,v6,v4,v7]
- 경로1은 <v3, v4>라는 중복 간선이 존재하고 노드가 중복 되므로 simple하지도 않고 elementary하지도 않다.
- 경로2는 v4노드가 중복되지만 중복 간선이 존재하지 않으므로 simple하지만 elementary하지는 않다.
참고)
정점이 중복되지 않을 경우 간선은 무조건 중복이 안된다. (역은 반드시 성립하지는 않음)
그렇기 때문에 정점이 중복되지 않으면 단순경로라 할 수 있다.
그래프 분류
무방향 vs 방향 그래프
무방향 그래프(Undirected Graph) : 간선에 방향이 표시되지 않은 그래프
- 하나의 간선은 양방향으로 갈 수 있는 길이다
- 정점 u,v를 잇는 간선을 (u,v)와 같이 표시한다. => 괄호 안에 정점의 쌍으로 표시
- 간선 (u,v)와 (v,u)는 동일한 간선이다. 즉, (u,v) = (v,u)
방향 그래프(Directed Graph) : 간선에 방향이 존재하는 그래프
- 하나의 간선은 한쪽 방향으로만 갈 수 있다
- 정점 u, v가 있을 때, u -> v로 가는 간선은 <u,v> 와 같이 표시한다. => 꺽세 안에 정점의 쌍으로 표시
- 간선 <u,v>와 <v,u>는 서로 다른 간선이다. 즉, <u,v> ≠ <v,u>
무방향 그래프
V(G) = { 1, 2, 3 } , E(G) = { (1,2), (2,3), (1,3) }
방향 그래프
V(G) = { 1, 2, 3 } , E(G) = { <1,2>, <3,1>, <3,2> }
가중치 그래프(Weighted Graph)
- 간선에 비용이나 가중치가 할당된 그래프
- 네트워크(network)라고도 한다
- ex) 도시간 연결, 통신망 사용료 등
희소 그래프(Sparse Graph) / 밀집 그래프(Dense Graph)
희소 그래프(Sparse Graph) : 간선의 개수가 적은 그래프. 노드 개수보다 간선 개수가 적으면 희소 그래프라 한다.
밀집 그래프(Dense Graph) : 간선의 개수가 많은 그래프. 노드 개수보다 간선 개수가 많으면 희소 그래프라 한다.
연결 그래프 vs 비연결 그래프
연결 그래프(Connected Graph) : 임의의 두 정점간의 경로가 존재하는 그래프
=> 그래프를 구성한느 모든 정점들 사이에서 경로가 존재하는 그래프
비연결 그래프(Disconnected Graph) : 연결 그래프가 아닌 그래프
부분 그래프(Sub Graph)
그래프 G를 구성하는 정점 V(G)와 간선 E(G)의 부분 집합으로 이루어진 그래프
=> G' ⊂ G , V' ⊂ V, E' ⊂ E
신장 그래프(Spanning Graph) : 그래프의 모든 정점을 포함하는 부분 그래프 (G' ⊂ G , V' ⊂ V)
연결 요소(Connected) Component)
부분 그래프의 일종으로 다음과 같은 조건을 만족하면 연결 요소라 한다
- 부분 그래프이다. (그래프 G의 부분 그래프 S)
- 연결 그래프이다. (정점간에는 경로가 존재)
- 외부로 향하는 간선이 없다. 즉, <u,v> ∈ E(S) 이면 u ∈ V(S) , v ∈ V(S) 이다.
- 그래프의 다른 정점이나 간선을 추가하면 연결 그래프가 되지 않는다. (연결성을 잃는다)
연결 요소(Componenet)는 연결(connected)속성에 최대 부분 그래프라 한다. => maximal connected subgraph
최대 부분 그래프는 다음과 같은 의미를 지닌다.
(어떤 속성에 대한) 최대 부분 그래프 (maximal subgraph)
- 어떤 속성을 유지하는 부분 그래프이다. ( ex) 연결요소에서는 연결성(connectivity)을 유지하는 것 )
- 다른 꼭짓점이나 변이 그 부분 그래프에 첨가되면 그 속성을 유지하지 못하는 부분 그래프이다. => 최대
강연결 요소(Strongly Component) : 방향그래프(Directed Graph)의 연결요소(connected component) 내 노드 u에서 v로 향하는 경로와 v에서 u로의 경로가 존재한다면 해당 연결요소를 강연결요소라고 한다.
=> 강연결요소끼리는 어떤 방향에서든 서로 도달가능하기 때문에 다음과 같이 그래프 정보를 압축하는 데 요긴하게 쓰일 수 있다.
참고) 강연결요소
클리크(Clique) : 모든 노드들이 서로 연결 되어 있는 부분 그래프
- 클리크 그 자체는 완전 그래프가 된다.
- 그래프에 여러개의 클리크가 존재할 수 있는데, 그 중 가장 많은 노드로 구성된 클리크를 maximum clique라 한다.
순환 그래프(Cyclic Graph) / 비순환 그래프(Acyclic Graph)
Cycle 존재 여부에 따라 순환 / 비순환 그래프로 나뉜다.
트리(Tree) : 싸이클을 갖지 않는 연결 그래프이다. (connected acyclic graph)
포레스트(forest) : 싸이클을 갖지 않는 비연결 그래프 (acyclic graph) => 트리의 모음집이다.
- 포레스트의 각각의 연결 요소(connected component)는 트리이다.
- 트리가 1개일 경우 포레스트는 connected graph이고, 2개 이상일 경우 disconnceted graph이다.
정규 그래프(Regular Graph) : 모든 정점의차수가 같은 그래프
완전 그래프(Complete Graph) : 모든 정점간에 간선이 존재하는 그래프
- 완전 그래프는 그 자체로 클리크(clique)이다. (maximum clique)
- n개의 정점으로 이루어진 완전 그래프라면 차수가 n-1인 정규(Regular Graph)이다.
단순 그래프(Simple Graph) : 루프(loop)가 없고 동일한 간선을 포함하지 않는 그래프 (no loop, no parralel edges)
다중 그래프(Multi Graph) : Parralel edge를 포함하는 그래프 (일반적인 그래프에서는 허용하지 않는다)
평면 그래프(Planar Graph) : 정점이 아닌 곳에서는 두 간선이 교차하지 않는 그래프
정점과 간선을 그렸을 때 간선이 교차하는 지점이 노드가 아니면 평면 그래프가 아니다
이분 그래프(Bipartite Graph) : 그래프의 모든 정점을 두 부분으로 나눴을 때, 각각의 모든 간선이 두 그룹의 정점 사이를 연결하는 그래프를 이분 그래프라 한다.
(주의!! 같은 그룹에 속한 정점끼리는 서로 인접하지 않도록 해야 한다)
이분 그래프트 다음과 같은 특징을 갖는다.
인접한 정점끼리 서로 다른 색으로 칠해서 모든 정점을 두 가지 색으로만 칠할 수 있다.
완전 이분 그래프(Complete Bipartite Graph) : 이분 그래프에서 각 그룹의 모든 정점이 다른 그룹의 모든 정점과 연결 되어 있는 그래프
그래프의 표현
그래프를 표현하는 방법으로 배열을 사용하는 인접 행렬(adjacency matrix)과 연결리스트를 사용하는 인접 리스트(adjacency list) 두가지가 있다.
다음 그림은 그래프를 인접행렬과, 인접 리스트로 도식화한 그림이다.
가중치가 없는 방향그래프를 인접행렬로 표현하는 방식을 도식화한 그림은 다음과 같다.
가중치가 없는 방향그래프를 인접리스트로 표현하는 방식을 도식화한 그림은 다음과 같다.
가중치가 있는 무방향그래프를 인접행렬로 표현하는 방식을 도식화한 그림은 다음과 같다.
(∞는 간선이 없는 경우로 간선의 가중치가 0인 경우와 구분하기 위한 표시이다)
가중치가 있는 무방향그래프를 인접리스트로 표현하는 방식을 도식화한 그림은 다음과 같다.
인접 행렬(adjacency matrix)
인접행렬은 정사각행렬로 2차원 배열로 표현한다.
N개의 정점과 E개의 간선을 갖는 그래프를 인접 행렬로 표현하면 다음과 같은 특징을 갖는다.
- 공간 복잡도가 항상 $n^2$ 이다. (간선 개수에 상관없이 정점 개수에만 영향을 받음)
- 간선의 존재 여부는 O(1) 시간안에 알 수 있다. (인접행렬 M에서 정점 u, v의 간선 존재 여부 - M[i][j]로 확인 가능)
- 특정 정점의 차수는 인접 행렬의 행이나 열을 조사하면 알 수 있으므로 시간 복잡도가 $O(N)$이다. 만약 모든 정점(n개)에 대한 차수를 구하려면 $O(N^2)$ 시간복잡도 만큼의 시간이 소요된다.
다음은 인접행렬로 표현할 때 그래프 성격에 따른 특징이다.
- 무방향 그래프 : 인접 행렬이 대칭행렬로 표현된다. 따라서 상삼각행렬 또는 하삼각행렬만 저장하면 된다.
- 방향 그래프 : 일반적으로 대칭이 아니다.
- 가중치 그래프 : 간선의 가중치를 저장한다. 이때, 간선이 없는 경우와 가중치 값이 0인 경우를 구분하기 위한 처리를 해야한다. 만약 두 경우 모두 0으로 처리할 경우 문제가 생길 수 있다.
간선 수가 많은 dense graph인 경우 인접행렬을 사용하면 좋다. (sparse graph에 비해 공간 낭비가 적으므로)
인접 리스트(adjacency list)
인접 리스트는 버킷과 연결 리스트로 표현한다.
각각의 버킷은 유일한 하나의 정점과 대응된다.
각각의 버킷은 대응되는 정점과 연결된 인접 정점들을 연결 리스트로 연결한다.
N개의 정점과 E개의 간선을 갖는 그래프를 인접 리스트로 표현하면 다음과 같은 특징을 갖는다.
- 공간 복잡도가 O(N+E)이다. (버킷 N개, 그래프의 모든 간선 E개)
- 특정 정점에 연결된 간선의 연결된 차수를 d라 할 때, 간선 존재 여부를 확인하려면 최악의 경우 연결된 모든 간선을 찾아야 하므로 O(d)의 시간복잡도를 갖는다. 최악의 경우(d = E), 평균적인 경우(d=E/N), 최선의 경우(d=0)
- 마찬가지로 특정 정점에 연결된 간선의 차수를 구하는 것은 O(d)만큼의 시간복잡도를 갖는다. 모든 정점에
간선 수가 적은 sparse graph인 경우 인접 리스트를 사용하면 좋다.
(희소 행렬일 경우 공간 낭비가 심하므로 인접 행렬 보다는 인접 리스트를 사용하는 것이 좋다)
> 그래프 순회(Graph Traversal/Search)
그래프 관련해서 자료를 찾으면서 공부하기 좋은 사이트 공유할까 합니다.
그래프 이론 공부할 수 있는 사이트
1. https://www.tutorialspoint.com/graph_theory/
2. https://d3gt.com/index.html
3. https://www.geeksforgeeks.org/engineering-mathematics-tutorials/#graph
참고)
en.wikipedia.org/wiki/Path_(graph_theory)
ratsgo.github.io/data%20structure&algorithm/2017/11/18/graph/
m.blog.naver.com/ndb796/221027866623
https://gmlwjd9405.github.io/2018/08/13/data-structure-graph.html
