그래프 자료 구조

그래프 소개

용어 정의

그래프의 표현 - 인접 행렬

그래프의 표현 - 인접 리스트

그래프 소개

Koenigsberg 다리 문제에서 최초로 그래프를 사용한 것으로 알려져 있다. 그래프는 현재 컴퓨터 공학 분야뿐만 아니라 여러 학문 분야에서 가장 많이 사용되는 수학적 모델 중의 하나이다.

그래프 용어 정의 I

그래프(graph)

정점(vertex), 에지(edge)

무향 그래프(undirected graph), 유향 그래프(directed graph)

분지수(degree), indegree, outdegree

완전 그래프(complete graph)

인접(adjacent, incident)

경로(path), 사이클(cycle)

단순 그래프(simple graph)

loop

다중 그래프(multigraph)

그래프 용어 정의 II

부그래프(subgraph)

연결된 그래프(connected graph)

연결된 요소(connected component)

강연결된 요소(strongly connected component)

그래프 표현 - 인접 행렬

다음과 같은 기본적인 연산은 어떻게 수행될 수 있을까?

- [eqn: (v, w)]가 그래프 [eqn: G]의 에지인가?

- [eqn: G]의 에지 수는?

- 에지 [eqn: (v, w)]를 추가하라. 혹은 삭제하라.

그래프 표현 - 인접 리스트