Week10_ 그래프

와! 벌써 그래프까지 왔네요. 여기까지 온 당신 정말 대단해!

 

이번 시간에는 그래프의 개념과 종류를 알아봅시다.

 

1. 그래프  ADT

-그래프(graph): (V, E) 쌍 

--> V: 정점(vertex)이라 불리는 노드의 집합

--> E: 간선(edge)이라 불리는 정점쌍들의 집합

*정점과 간선은 원소(정보)를 저장해요.

 

ex) 그림 첨부

 

2. 간선에 따른 그래프 유형

-방향간선(directed edge): 정점들의 순서쌍(u, v) (u는 시점, v는 종점)

-방향그래프(directed graph): 모든 간선이 방향 간선인 그래프

 

-무방향간선: 정점들의 무순쌍 (u, v)

-무방향그래프: 무방향간선으로 이루어진 그래프

 

<그래프 용어 정리>

-간선의 끝점(end vertex)

-정점의 부착(incident) 간선

-정점의 인접 정점

-정점의 차수(degree): 간선의 개수

-병렬 간선

-루프

-경로: 정점과 간선의 교대열 ex) P1=(V, b, X, h, Z)

-단순경로: 모든 정점이 간선과 유일한 경로

<그림 첨부>

 

**참고) 배열과 연결리스트는 자료 구조가 아니라, 자료 구조를 표현하는 방식입니다!!

자료 구조는 힙, 스택, 트리 같은 구조를 말해요.