BFS, DFS 세미나

그래프 기초

- 그래프 이론과 그래프 탐색 

 

01. 그래프 용어

 

정점 (vertax) ,노드 (node)

 

간선 (edge), 정점을 잇는선

: 간선에는 양방향 간선 , 무방향 간선,단방향 간선이 있음

 

그래프 (graph)

: 노드와 그들을 잇는 간선으로 이루어져 있음

 

 

차수 :  (in degree, out degree 가 있음 

in degree - 나에게로 들어오는 간선

out degree - 나로부터 나가는 간선

 

 

 

이웃 노드의 개수

각 정점에 연결된 간선의 개수

 

이웃 노드 , 인접한 노드

: 두 노드를 잇는 간선이 있을때, 두 노드를 이웃노드라고함

 

경로 

: 한 노드에서 그래프의 간선을 지나 다른 노드까지 가는길

(경로의 길이 ) = (경로에 포함된 간선으 ㅣ개수)