목록2024/03/26 (1)
Skipalong's tistory
240325 TIL - 그래프
오늘은 기술면접에서 공부한 그래프에 대해서 정리해보겠다. 그래프 정점과 간선으로 이루어진 자료 구조 ex )정점 3개와 간선 3개 실생활에서 지하철 노선도 최단 경로, 도로, 선수 과목 등에 쓰임 그래프 관련 용어 용어 뜻 정점(Vertex or Node) 데이터를 저장하는 위치 간선(Edge) 정점(노드)를 연결하는 선. 링크(Link) 또는 브랜치(branch) 로도 불린다. 인접 정점(adjacent vertex) 간선에 의해 직접 연결된 정점을 의미한다. 위의 그림에서 1과 2는 인접 정점이다. 단순 경로(simple path) 경로 중에서 반복되는 정점이 없는 경우를 의미한다. 한붓 그리기와 같이 같은 간선을 지나가지 않는 경로를 의미한다. 차수(degree) 무방향 그래프에서 하나의 정점에 인..
TIL
2024. 3. 26. 01:28