12-01 그래프(Graph)

 

아래의 상기 내용은

"이것이 자료구조+알고리즘이다. With C언어"의 도서 내용과 인터넷의 내용을 실습 및 정리한 글입니다.

1.그래프(Graph)

 1)정의

 -정점 및 혹은 노드와 그들을 연결하는 간선으로 이루어진 자료구조.

 -간선으로 연결된 두 정점을 가리켜 서로 인접한 이웃관계라고 한다.

-간선은 정점들 간의 경로(Path) 및 관계(Relation) 등 여러가지로 표현된다.

-간선은 정점과 정점으로 된 방향이 존재할 수 있고 방향이 존재하는 그래프를

 방향성 그래프(Directed Graph) 존재하지 않은 그래프를 무방향성 그래프(Undirected Graph).

2.그래프의 표현 방법

1)개요

 -그래프는 정점과 간선의 결합으로 여러가지 형태로 표현될 수 있다. 대표적으로 행렬과

리스트이다.

 2)인접 행렬(Adjacency Matrix)

 -정점들간의 인접관계를 나타내는 행렬.

 -그래프의 정점 수를 N으로 할 때 N x N 크기의 행렬을 만들고 간선이 존재를 1의 요소로 표현한 것.

3)인접 리스트(Adjacency List)

-정점들간의 인접관계를 나타내는 리스트.

-정점이 자신과 인접한 정점의 목록을 리스트로 관리하는 방법.