그래프
•
정점과 간선으로 이루어진 자료 구조
•
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) | 단순 경로의 시작 정점과 종료 정점이 동일한 경우를 의미한다. |
그래프의 종류
•
무방향 그래프 (양방향)
◦
두 정점을 연결하는 간선에 방향이 없는 그래
•
방향 그래프 (단반향)
◦
간선에 방향이 있는 그래프
•
완전 그래프
◦
한 정점에서 다른 모든 정점과 연결되어 최대 간선 수를 갖는 그래프
•
부분 그래프
◦
기존 그래프에서 일부 정점이나 간선을 제외하여 만든 그래프
•
가중치 그래프
◦
정점을 연결하는 간선에 가중치를 할당한 그래프
