챕터6-1. 그래프 | 개념 및 용어

그래프의 개념

# 그래프(Graph)

- 자료구조의 일종

- 그래프는 정점집합과 간선집합으로 만들어진다. G = (V, E)

- 정점(Node, Vertex)은 말그대로 점을 의미하고, 간선(Edge)은 정점간의 관계를 나타낸다.

- 예시1) 지하철노선이나 도로를 그래프로 나타낼 수 있음.
- 예시2) 페이스북같은 경우는 사람이 정점이고 두 사람이 친구사이면 둘을 간선으로 연결해줄 수 있음

그래프에서 사용되는 용어

# 경로(Path)

- 출발지와 도착지가 있고 그 사이를 연결하는 정점과 간선이 있으면 이것을 경로라고 한다.
- 예시)
   A->C->D->E->B
   A->B
   A->C->B

# 사이클(Cycle)

- 경로 중에서 시작점과 도착점이 같은 경우를 사이클이라고 한다.

- 예시)
   'A'->C->B->'A'

   'A'->C->E->B->'A'

   'A'->C->D->E->B->'A'

 

# 단순 경로와 단순 사이클(Simple Path and Simple Cycle)
- 같은 정점을 두 번 이상 방문하지 않는 경로 / 사이클
- 일반적으로 특별한 말이 없으면, 사용하는 경로와 사이클은 단순 경로 /사이클을 의미한다.

ex) "같은 정점을 두 번이상 방문해도 된다." 혹은 "같은 간선을 여러번 사용해도 된다." 일땐 단순 경로와 사이클이 아님.

# 방향이 있는 그래프(Directed Graph)

- A->C와 같이 간선에 방향이 있다.
- A->C는 있지만 C->A는 없다. 

 

# 방향이 없는 그래프(Undirected Graph)     -> 양방향 그래프(Bidirection Graph)
- A-C는 A->C와 C->A를 나타낸다.
- 실제 구현에서는 두 방향에 대한 간선을 모두 저장하여 양방향 그래프로 저장하여 문제를 풀게 된다.

 

# 간선 여러개(Multiple Edge)
- 두 정점 사이에 간선이 여러 개일 수도 있다.
- 주로 풀게될 문제는 간선마다 가중치를 가지고 있는 그래프에서 최단거리를 구하는 문제인데
   이땐 A->B로 가는 여러 간선 중에서 가장 작은 가중치를 가지는 간선 하나만 택하게 된다.

 

# 루프(Loop)

- 간선의 양 끝 점이 같은 경우 루프라고 한다. 자기자신에서 출발해서 자기 자신으로 돌아오는 동글뱅이 간선
- A->A

 

# 가중치(Weight)

- 간선에 가중치가 있는경우 A에서 B로 이동하는 거리, 이동하는데 필요한 시간, 이동하는데 필요한 비용 등을 의미한다.
- 가중치가 없는 경우 모든 간선의 가중치가 1이라고 생각하고 문제를 풀면된다.

 

# 차수(Degree)

- 정점과 연결되어 있는 간선의 개수
- 방향이 있는 그래프라면 in-degree(정점으로 들어오는 간선), out-degree(정점에서 나가는 간선)를 따로 세어주어야 한다.