그래프(Graph)

개념 : 연결되어 있는 원소간의 관계를 표현한 자료구조로 정점(vertex)와 객체를 연결하는 간선(Edge)의 집합으로 구성됨

✔️ 그래프 용어

• 사이클(cycle) : 한 정점에서 시작해 해당 정점으로 끝나는 경로 ( ex : A-B-C-D-A )

• 차수(degree) : 차수는 정점에 부속되어 있는 간선의 수를 뜻한다. 무방향그래프에서는 단순히 정점에 연결된 간선의 수를 뜻하지만, 방향 그래프에서는 진입차수(in-degree) 와 진출차수(out-degree)가 다르다. 예를 들어 무방향 그래프에서 E의 차수는 3이지만, 방향 그래프에서는 진입차수는 3이고 진출차수는 1이다. 즉, 진입차수는 들어오는 간선의 개수를 뜻하고, 진출차수는 나가는 간선의 개수를 뜻한다.

• 경로(path) : 그래프에서 간선을 따라 갈 수 있는 길을 정점으로 나열한 것( ex : A->B->C->E->F )

• 경로 길이(path length) : 경로를 구성하는 간선의 수

• 단순 경로 (simple path) : 모두 다른 정점으로 구성된 경로를 뜻한다.

✔️ 그래프 구현은 어떤게 효율적일까 ?

→ 인접 리스트 공간복잡도가 작아짐

✔️ 그래프 종류

1. 무방향 그래프

• 무방향 그래프: 두 정점을 연결하는 간선에 방향이 없는 그래프
• 최대 간선 수: n(n-1) / 2

2. 방향 그래프

• 방향 그래프 : 두 정점을 연결하는 간선에 방향이 있는 그래프
  <Vi,Vj> : 꼬리(tail), 머리(head)
• 최대 간선 수: n(n-1)

3. 완전 그래프

• 한 정점에서 다른 모든 정점과 연결 되어 최대 간선 수를 갖는 그래프

4. 부분 그래프

• 기존의 그래프에서 일부 정점이나 간선을 제외하여 만든 그래프

5. 가중 그래프 (=네트워크)

• 가중 그래프(weight Graph)는 정점을 연결하는 간선에 가중치(weight)를 할당한 그래프

6. 연결 그래프 (Connected Graph)

• 서로 다른 모든 쌍의 정점들 사이에 경로가 있는 그래프를 말함

7. 비연결 그래프(Disconnected Graph)

• 연결되지 않은 정점이 있는 그래프를 뜻한다.