[C++] 그래프

 

 

 

 

그래프

비선형 문제를 다룰 수 있는 자료구조

관계에 특화된 자료구조로 정점(Vertex)와 간선(Edge)으로 구성되어 있다.

정점 : 고유하게 식별되는 객체

간선 : 정점간의 관계

 

그래프의 종류

 

용어

인접 (Adjacent)	간선으로 연결된 정점끼리 인접하다고 표현한다.
부속 (Incident)	간선은 연결된 정점에 부속되어 있다고 한다.
차수 (Degree)	정점에 부속되어 있는 간선의 수.
진입 차수	정점에 들어오는 방향의 간선의 수.
진출 차수	정점으로부터 나가는 방향의 간선의 수.
경로 (Path)	한 정점에서 다른 정점까지 간선으로 연결된 정점을 순서대로 나열한 리스트.
경로의 길이	경로를 구성하는 간선의 수.
단순 경로	모두 다른 정점으로 구성된 경로.
사이클 (Cycle)	단순 경로 중 경로의 시작 정점과 마지막 정점이 같은 경로.
연결 (Connected)	경로가 있으면 정점끼리 연결되었다고 표현한다.

 

순회

한 정점에서 시작해 그래프에 모든 정점을 한 번씩 방문하는 것

 

깊이 우선 탐색 (Depth First Search)

stack을 사용한다.

 

너비 우선 탐색 (Breadth First Search)

queue를 사용한다.