[기본] 그래프

dia·2023년 11월 24일
0

그래프

개념

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

용어

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

종류

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

탐색

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

profile
CS 메모장

0개의 댓글

Powered by GraphCDN, the GraphQL CDN