[코딩테스트] 그래프

reference : 2021 코딩테스트 기초(최백준) 강의를 공부하며 정리한 내용입니다.

그래프

• 자료구조의 일종
• 정점(Node, Vertex) : 하나의 점
• 간선(Edge) : 정점간의 관계를 나타낸다. 정점과 정점을 연결함.

• G = (V,E)로 나타냄

• 경로
  • 정점 A에서 B로 가는 경로 : 연결되어 있는 간선을 통해서만 이동 가능함, 연속하는 정점 사이의 간선을 통해서!
• 사이클
  • 시작정점 == 도착정점
  • 정점 A에서 다시 A로 돌아오는 경로 ex) A->C->B->A, A->C->E->B->A …
• 단순 경로와 단순 사이클
  • 경로 / 사이클에서 같은 정점을 두 번 이상 방문하지 않는 경로/사이클
  • 특별한 말이 없으면, 일반적으로 사용하는 경로와 사이클은 단순 경로/사이클
• 방향 있는 그래프(Directed Graph)
  • 화살표가 있는 방향으로만 갈 수 있다
• 방향 없는 그래프(Undirected Graph)
  • 간선에 방향이 없다. A - C는 A->C 와 C->A를 나타냄.
  • 양방향 그래프(Bidirection Graph)
• 간선 여러개
  • 두 정점 사이에 간선이 여러 개
• 루프
  • 간선의 양 끝 점이 같은 경우
  • A -> A
• 가중치
  • 간선에 가중치가 있는 경우엔 A->B 이동하는 거리, 시간, 비용 등..
  • 매우 중요!!!
  • 가중치가 없는 경우엔 1이라고 생각하기
• 차수
  • 정점과 연결되어 있는 간선의 개수
  • 방향 그래프의 경우엔 In-degree, Out-degree 나누어서 차수 계산