1. 그래프
- 연결 관계를 갖는 상태를 포함하는 자료구조
- 논리적 특성 및 시각적 표현 용이
- 노드(node) / 정점(vertex) : 그래프의 각 상태
- 에지(edge, 간선) : 두 상태 간 연결
2. 그래프의 자료구조 표현
- 노드 간 관계를 배열의 형태로 표현 가능
아래 그래프를 행렬로 표현해보자.
3. 그래프의 종류
- 무방향 그래프(Undirected Graph)
- 에지에 방향이 없고, 두 노드 간 관계는 상호적
- 무방향 그래프의 간선은 간선을 통해서 양 방향으로 갈 수 있음.
- 정점 A와 정점 B를 연결하는 간선은 (A,B)와 같이 정점의 쌍으로 표현한다.
- (A,B)는 (B,A) 동일
- 방향 그래프(Directed Graph)
- 에지에 방향이 있고, 두 노드 간 관계는 명시적
- 간선에 방향성이 존재하는 그래프
- A -> B로만 갈 수 있는 간선은 <A,B>로 표시
- <A,B>는 <B,A>와 다름
- 가중치 그래프(Weighted Graph)
- 노드 간 에지에 가중치가 있는 그래프
- 가중치는 간선의 비용, 거리, 시간 등을 나타냄
- 완전 이분 그래프(Bipartite Graph)
- 무방향 그래프에서 노드를 두 그룹으로 나누었을 때 같은 그룹 내의 노드는 서로 인접하지 않고, 다른 그룹의 노드와만 인접하는 그래프
- 비순환 그래프(Acyclic Graph)
- 사이클이 없는 그래프
- 비연결 그래프(Disconnected Graph)
- 하나 이상의 노드가 에지로 연결되어 있지 않음
- 무방향 그래프에서 특정 정점쌍 사이에 경로가 존재하지 않은 경우
- 연결 그래프(Connected Graph)
- 무방향 그래프에 있는 모든 정점쌍에 대해서 항상 경로가 존재하는 경우
- 순환 그래프(Cycle Graph)
- 단순 경로의 시작 정점과 종료 정점이 동일한 경우
- 완전 그래프(Complete Graph)
- 모든 노드는 에지를 통해 다른 모든 노드와 연결
- 부분 그래프(Subgraph)
- 주어진 그래프의 일부 노드와 간선으로 이루어진 그래프
- 강결합 그래프(Strong Connected Graph)
- 방향 그래프에서, 모든 노드 사이에 양방향 경로가 존재하는 그래프
3. 그래프의 표현 방법
- 근접 행렬
- 높이 : 그래프의 노드 개수
- 너비 : 에지 개수
- 각 행 : 특정 에지와 노드의 관계
- 0 : 노드가 특정 에지와 연결되지 않은 상태
- 1 : 무향 그래프와 연결된 경우 (또는) 유향 그래프에서 특정 에지로 나가는 노드
- -1 : 유향 그래프에서 특정 에지를 통해 수신 노드로 연결되는 경우
- 인접 리스트
- 초기 리스트의 크기 : 그래프의 노드 수
- 각 값이 특정 노드에 연결된 노드를 나타내는 연결 리스트를 사용
Robotics