그래프의 정의
그래프는 정점(node 혹은 vertex)과 그 노드를 연결하는 간선(edge)을 하나로 모아 놓은 자료 구조로,
연결되어 있는 객체 간의 관계를 표현할 수 있는 구조이다.
ex) 지도, 지하철 노선도의 최단 경로, 전기 회로의 소자들, 도로(교차점과 일방 통행길), 선수 과목 등
- 그래프는 여러 개의 고립된 부분 그래프(isolated subgraphs)로 구성될 수 있다.
- 그래프의 특성은 directed(방향) 또는 undirected(무방향) 그래프가 있다.
위 그림과 같이, 그래프가 한쪽 방향(one-way)으로 구성될 수 있다면 방향 그래프가 가장 적합하다.
방향 그래프: 간선에 방향성이 존재하는 그래프
- A -> B로만 갈 수 있는 간선은 <A, B>로 표시한다.
- <A, B>는 <B, A>와 다름
무방향 그래프: 간선을 통해서 양 방향으로 갈 수 있는 그래프
- 정점 A와 정점 B를 연결하는 간선은 (A, B)와 같이 정점의 쌍으로 표현한다.
- (A, B)는 (B, A)와 동일
그래프에서 노드를 연결하는 목적이 상호 교환 관계를 표현하기 위해서라면, 무방향 그래프가 가장 적합하다. 이는 교환 관계의 경우 두 노드 간에 양방향으로 노드 정보가 교환되는 상황이기 때문이다. 따라서 방향이 하나로 정해진 방향 그래프보다는 무방향 그래프로 표현하는 것이 적절하다.
- 간선으로 연결된 노드들끼리는 서로 인접(adjacent)해있다고 하며, 이웃(neighbor)라고 칭한다.
Cyclic and Acyclic Graphs(순환 및 비순환 그래프)
순환 그래프: 노드들 간에 순환(루프)을 형성하는 그래프
(예 : 방문한 노드에 다시 방문하는 경우)
위 이미지에서는 아래와 같이 순환 구조가 형성되어 있다.
1. 노드 B에서 출발
2. 가장자리를 따라 C, E, D로 이동
3. B(이미 방문한 노드)로 돌아감
참고 : 무방향 그래프는 항상 동일한 노드에 재방문할 수 있으므로 순환 그래프이다.
위 그림과 같이 순환을 형성할 수 없는 경우(간선을 따라 이미 방문한 노드에 방문할 수 없는 경우) 비순환(Acyclic) 그래프라고 한다.
Weighted Graphs (가중치 그래프)
가중치 그래프: 간선에 비용이나 가중치가 할당된 그래프
- ‘네트워크(Network)’ 라고도 한다.
ex) 도시-도시의 연결, 도로의 길이, 회로 소자의 용량, 통신망의 사용료 등
- 가중치는 서로 다른 그래프에서 서로 다른 데이터를 나타낸다.
ex) 도로 구간을 나타내는 그래프: 가중치는 도로의 길이를 나타낼 수 있다. - 그래프에서 경로의 총 가중치가 높을수록 경로이동시간(비용)이 길어진다.
- 가중치는 모든 경로 비교 시, 어떤 경로를 선택할 지에 사용된다.
Directed Acyclic Graphs (DAGs)
방향성 비순환 그래프(DAG): 순환되지 않고 특정한 단방향으로만 이루어진 그래프
위 그림처럼 edge가 순서대로 향하도록 DAG의 노드를 선형(단방향)으로 정렬할 수 있다.
레퍼런스
https://gmlwjd9405.github.io/2018/08/13/data-structure-graph.html
