알고리즘 그래프(Graph)

소개글

알고리즘 그래프(Graph)

목차

1. 그래프의 정의와 종류
(1) 그래프란?
(2) 그래프의 용어
(3) 그래프의 종류

2. 그래프의 표현
(1) 인접 행렬(Adjacency Matrix)
(2) 인접 리스트(Adjacency List)

3. 그래프의 운행
(1) 깊이우선 검색방식(DFS:Depth First Search)
(2) 너비우선 검색방식(BFS:Breadth First Search)

본문내용

1. 그래프의 정의와 종류
(1) 그래프란?
정점과(Vertex)와 간선(Edge)를 이용하여 객체들과 객체간의 연결을 모델링하는 것을 뜻한다. 즉 각각의 단위 정보를 링크로 연결하여 구조화시킨 자료 구조라고 할 수 있다. 항공로의 공항과 노선, 전자회로의 칩과 선로가 그 예에 해당한다.
그래프에서는 객체의 절대적 위치나 연결의 모양은 의미가 없고 오로지 객체의 연결 상태가 중요하다. 이것은 위상(Topology)이 중요하다고 말할 수 있다.

(2) 그래프의 용어
① E(G) : 간선들의 집합
② V(G) : 정점들의 집합
* 집합 E는 공집합일 수 있다. 즉 점이 하나도 없는 그래프는 존재하지 않지만, 연결선이 하나도 없는 그래프는 존재한다.
③ 인접하다(adjacent) : 정점에서 간선으로 연결된 다른 정점들을 인접한다고 한다.
④ 부속하다(incident) : 정점에 연결된 간선들은 그 정점에 부속되었다고 한다.
⑤ 차수(degree) : 점점에 부속되어 있는 간선의 개수를 말한다.
* c(indegree)와 진출차수(outdegree)로 나누어진다.
⑥ 경로(path) : 임의의 정점으로부터 다른 정점에 이르는 간선들의 집합을 말한다.
⑦ 단순 경로(simple path) : 모든 정점이 다른 경로일 때를 말한다.
⑧ 사이클(cycle) : 첫 번째 정점과 마지막 정점이 동일한 단순 경로를 말한다.
⑨ 루프(self loop) : 임의의 한 정점에서 같은 정점으로 이르는 간선을 말한다.
⑩ 경로의 길이(length of path) : 경로 상에 존재하는 간선의 개수를 말한다.

참고 자료

없음