Graph

Graph

• Data structure
• 2021년 6월 3일

연결되어 있는 객체 간의 관계를 표현할 수 있는 자료구조로 Tree도 그래프의 일종인데 그래프 중에서도 사이클이 허용되지 않는 그래프이다. 1. 개념 정점(vertex) / 노드(node) : 위치 간선(edge) / 링크(link) : 위치간의 관계 인접 정점 : 간선에 의해 직접 연결된 노드 차수 : 하나의 노드에 인접한 노드의 수 경로 길이 : 경로를 구성하는 데 사용된 간선의 수 단순 경로 : 경로 중에서 반복되는 간선이 없을 경우 사이클 : 단순경로의 시작 정점과 종료 정점이 동일한 경로 오일러 경로 : 모든 간선을 한 번만 통과하면서 처음 정점으로 돌아오는 경로 오일러 정리 : 간선이 짝수일 때만 오일러 경로가 존재 부분 그래프 : 원래의 그래프의 일부 정점 및 간선으로 이루어진 그래프...