240325 TIL - 그래프

오늘은 기술면접에서 공부한 그래프에 대해서 정리해보겠다.

그래프

• 정점과 간선으로 이루어진 자료 구조
• ex )정점 3개와 간선 3개

• 실생활에서 지하철 노선도 최단 경로, 도로, 선수 과목 등에 쓰임

그래프 관련 용어

용어 뜻

정점(Vertex or Node)	데이터를 저장하는 위치
간선(Edge)	정점(노드)를 연결하는 선. 링크(Link) 또는 브랜치(branch) 로도 불린다.
인접 정점(adjacent vertex)	간선에 의해 직접 연결된 정점을 의미한다. 위의 그림에서 1과 2는 인접 정점이다.
단순 경로(simple path)	경로 중에서 반복되는 정점이 없는 경우를 의미한다. 한붓 그리기와 같이 같은 간선을 지나가지 않는 경로를 의미한다.
차수(degree)	무방향 그래프에서 하나의 정점에 인접한 정점의 수를 의미한다. 1의 차수는 2이다.
진출 차수(in-degree)	방향 그래프에서 외부로 향하는 간선의 수를 의미한다.
진입 자수(out-degree)	방향 그래프에서 외부에서 들어오는 간선의 수를 의미한다.
경로 길이(path length)	경로를 구성하는데 사용된 간선의 수를 의미한다.
사이클(cycle)	단순 경로의 시작 정점과 종료 정점이 동일한 경우를 의미한다.

그래프의 종류

• 무방향 그래프 (양방향)
  • 두 정점을 연결하는 간선에 방향이 없는 그래프

• 방향 그래프 (단반향)
  • 간선에 방향이 있는 그래프

• 완전 그래프
  • 한 정점에서 다른 모든 정점과 연결되어 최대 간선 수를 갖는 그래프

• 부분 그래프
  • 기존 그래프에서 일부 정점이나 간선을 제외하여 만든 그래프

• 가중치 그래프
  • 정점을 연결하는 간선에 가중치를 할당한 그래프

참고 사이트

https://leejinseop.tistory.com/43

[자료구조] 그래프(Graph)의 개념 설명

https://80000coding.oopy.io/125156cf-79bb-48da-82ae-1f2ee7896bb8

[자료구조] 그래프(Graph) 개념 정리

 

이렇게 그래프에 대해 알아보았는데 그래프에 대한 개념과 용어가 아직 부족하고 dfs나 그래프를 사용하는 알고리즘 문제들이 나오는 만큼 트리나 그래프에 대한 부분에 대해 개념을 잡고 알고리즘공부를 해야겠다.