그래프

그래프는 정점 혹은 노드 or 간선으로 표현한 것을 그래프라고 한다. 내가 생각 했을 때 그래프는 길 찾기 문제를 풀 때 혹은 최단거리 같은 문제를 풀때 그래프라는 말을 들어본 것 같다.

그래프의 용어

1. 노드: 위치를 말함, 정점이라고도 함
2. 간선: 위치 간의 관계를 표시한 선 , 노드를 연결한 선이라고 생각해도 무관(link, branch)라고도 함
3. 인접 정점(노드): 간선으로 직접 연결된 정점(노드)

그래프의 종류

무방향 그래프

방향이 없는 그래프로 간선을 통해서 양방향으로 이동이 가능하다 무방향 그래프의 노드 표기는
A와 B가 연결 되어 있으면 (A,B) or (B,A)라고 표기힌다.

단방향 그래프

방향이 있는 그래프로 간선을 통해서 정해진 방향으로만 이동이 가능하다. 노드의 표기법은
A에서 B로 향하는 간선이 있을 경우 <A,B>라고 표기한다.

                    			<A,B> <B,C> <B,D> <C,D>
                                

가중치 그래프

간선에 비용이(값,길이 등)이 할당된 그래프

사이클

단순 경로의 시작 노드와 종료 노드가 동일한 그래프

비순환 그래프

사이클이 없는 그래프

완전 그래프

모든 노드가 서로 연결되어 있는 그래프

트리

트리 또한 그래프의 일종으로 단방향성이 있는 비순환 그래프를 트리라고 한다. 트리는 알고리즘에서 매우 중요하기 때문에 차후에 더 집중적으로 공부하려고 한다.