그래프

그래프 (graph)

그래프는 연결되어 있는 객체간의 관계를 표현할 수 있는 자료구조로 지도, 전기회로 와 같이 선형 리스트나 트리의 구조로 표현할 수 없는 복잡한 문제들을 표현하는데 사용된다.

정점(vertex)과 간선(edge)들의 집합으로 구성되며 간선의 종류에 따라 무방향 그래프(undirected graph)와 방향 그래프(directed graph)로 구분된다.

간선에 의해 연결된 정점은 인접 정점(adjacent vertex)라고 부르며 하나의 정점에 인접한 정점의 수는 차수(degree)라 부른다.

트리도 그래프 중 하나의 특수한 종류로 볼 수 있다.

추상 자료형

create_graph() /* 그래프를 생성 */
init(g) /* 그래프를 초기화 */
is_empty(g) /* 그래프가 공백 상태인지 검사 */
insert_vertex(g, v) /* 그래프에 정점 v를 삽입 */
insert_edge(g, u, v) /* 그래프에 간선 (u, v)를 삽입 */
delete_vertex(g, v) /* 그래프에서 정점 v를 삭제 */
delete_edge(g, u, v) /* 그래프에서 정점 (u, v)를 삭제 */
adjacent(v) /* 정점 v에 인접한 정점들의 리스트를 반환한다. */
destory_graph(g) /* 그래프를 제거한다. */

구현

• 인접 행렬로 구현한 그래프
• 인접 리스트로 구현한 그래프

탐색

• DFS, BFS