6장 그래프 - (1) 그래프 개념

1. 그래프(Graph)

-자료구조의 일종

-정점(Node, Vertex)

-간선(Edge) : 정점 간의 관계를 나타냄

-G=(V,E) 로 나타낸다.

2. 경로(Path)

-정점 A에서 정점 B로 가는 경로

3. 사이클(Cycle)

-정점 A에서 다시 A로 돌아오는 경로   

4. 단순 경로와 단순 사이클(Simple Path and Simple Cycle)

-경로/사이클에서 같은 정점을 두 번 이상 방문하지 않는 경로/사이클

-특혈한 말이 없으면, 일반적으로 사용하는 경로와 사이클은 단순 경로/사이클을 말한다.

5. 방향 있는 그래프(Directed Graph)

-간선에 방향이 있는 그래프

6. 방향 없는 그래프(Undirected Graph)

-간선에 방향이 없음

-양방향 그래프라고도 함(Bidirection Graph)

7. 간선 여러개(Multiple Edge)

-두 정점 사이에 간선이 여러 개일 수도 있음

-두 간선은 서로 다른 간선

-최단 거리를 구할 때는, 두 정점 사이의 여러 간선 중 가중치가 작은 것을 선택하면 됨

8. 루프(Loop)

- 간선의 양 끝 점이 같은 경우

9. 가중치(Weight)

- A->B 간선에 가중치가 있는 경우에는

- A에서 B로 이동하는 거리, 이동하는데 필요한 시간, 이동하는데 필요한 비용 등이 될 수 있음

- 가중치가 없는 경우에는 모든 간선의 가중치를 1이라고 생각하고 접근

10. 차수(Degree)

- 정점과 연결되어 있는 간선의 개수

- 방향 그래프의 경우, 나가는 간선을 out-degree, 들어오는 간선을 in-degree