[기본] 그래프

그래프

개념

연결된 객체 관계를 표현하는 자료구조

용어

• 정점 V (vertices): 객체, 노드(node)
• 간선 E (edge): 정점 간 관계, 링크(link)
• 인접 정점: 해당 정점에 대해 인접한 정점
• 경로: 두 정점을 잇는 길, 두 정점 사이에 있는 정점들의 나열
  단순 경로: 반복되는 간선이 없는 경로
  사이클: 시작 정점과 종료 정점이 동일한 경로

종류

• 무방향 그래프
  간선의 방향이 없는 그래프
• 방향 그래프
  간선의 방향이 있는 그래프
• 가중치 그래프(네트워크)
  간선에 비용 또는 가중치가 할당된 그래프
• 부분 그래프
  다른 그래프의 일부가 되는 그래프
• 연결 그래프
• 완전 그래프

탐색

깊이 우선 탐색
너비 우선 탐색