[알고리즘] 그래프

• 그래프는 아이템들과 이들 사이의 연결 관계 표현
• 그래프는 정점(Vertex)들의 집합과 이들을 연결하는 간선(Edge)들의 집합으로 구성된 자료 구조
  • |V| : 정점의 개수, |E| : 그래프에 포함된 간선의 개수
  • |V|개의 정점을 가지는 그래프는 최대 |V| ( |V| - 1 ) / 2 간선 가능  -> 무향 그래프에 해당

---

< 그래프 유형 >

• 무향 그래프 (양방향)
• 유향 그래프
• 가중치 그래프
• 사이클 없는 방향 그래프
• 완전 그래프 : 모든 노드가 연결되어 있는 그래프
• 부분 그래프
• 트리는 싸이클이 없는 무향 연결 그래프이다.
  • 두 노드 사이에는 유일한 경로 존재
  • 각 노드는 최대 하나의 부모 노드가 존재할 수 있다.
  • 각 노드는 자식 노트가 없거나 하나 이상이 존재할 수 있다.

---

인접(Adjacency)

• 두 개의 정점에 간선이 존재하면 서로 인접해 있다고 한다.
• 완전 그래프에 속한 임의의 두 정점들은 모두 인접해 있다.

---

• 경로란 간선들을 순서대로 나열한 것.
  • 간선들 : (0,2), (2,4), (4,6)
  • 정점들 : 0 - 2 - 4 - 6
• 경로 중 한 정점을 최대 한 번만 지나는 경로 : 단순경로
• 시작한 정점에서 끝나는 경로 : 사이클(Cycle)

---

< 그래프 구현 >

• 인접 행렬-정점중심
  • |V| x |V| 크기 2차원 배열 이용해서 간선 정보 저장
  • 관계성이 없는 접점도 표현되어 공간 낭비
• 인접 리스트-정점중심
  • 각 정점마다 해당 정점으로 나가는 간선의 정보 저장
• 간선 리스트-간선중심
  • 간선(시작 정점, 끝 정점)의 정보를 객체로 표현하여 리스트에 저장