1. 그래프(Graph)란?
그래프란 실제 세계의 현상이나 사물의 정점(Vertex) 또는 노드(Node)와 간선(Edge)로 표현하기 위해 사용한다.
위 이미지에서 A, B, C, D, E는 정점에 해당하며 각 정점들을 잇는 선은 간선에 해당한다.
2. 그래프 관련 용어
📌 주요 용어
- 노드(Node): 위치를 말하며, 정점(Vertex)라고도 함
- 간선(Edge): 위치 간의 관계를 표시한 선으로 노드를 연결한 선임(Link 또는 branch라고도 함)
- 인점 정점(Adjacent Vertex): 간선으로 직접 연결된 정점(또는 노드)
📌 참고 용어
- 정점의 차수 (Degree): 무방향 그래프에서 하나의 정점에 인접한 정점의 수
- 진입 차수 (In-Degree): 방향 그래프에서 외부에서 오는 간선의 수
- 진출 차수 (Out-Degree): 방향 그래프에서 외부로 향하는 간선의 수
- 경로 길이 (Path Length): 경로를 구성하기 위해 사용된 간선의 수
- 단순 경로 (Simple Path): 처음 정점과 끝 정점을 제외하고 중복된 정점이 없는 경로
단, 시작 노드와 끝 노드는 동일해도 됨
- 사이클 (Cycle): 단순 경로의 시작 정점과 종료 정점이 동일한 경우
3. 그래프 종류
📌 무방향 그래프(Undirected Graph)
- 간선에 향이 없는 그래프
- 간선을 통해 노드는 양방향으로 갈 수 있음
- A와 B 노드가 연결돼있을 때 (A, B)와 같이 표기(혹은 (B, A))
📌 방향 그래프(directed Graph)
- 간선에 방향이 있는 그래프
- 간선을 통해 화살표 방향으로만 갈 수 있음
- A와 B 노드가 A → B로 가는 간선으로 연결돼 있는 경우 <A, B>와 같이 표기(<B, A>는 B → A로 가는 간선을 의미)
📌 가중치 그래프(Weighted Graph)
- 간선에 비용 또는 가중치가 할당된 그래프
📌 연결 그래프(Connected Graph)
- 무방향 그래프에 있는 모든 노드에 대해 항상 경로가 존재하는 경우
📌 비연결 그래프(Disconnected Graph)
- 무방향 그래프에서 특정 노드에 대해 경로가 존재하지 않는 경우
📌 사이클(Cycle)와 비순환 그래프(Acyclic Graph)
- 사이클(Cycle): 단순 경로의 시작 노드와 종료 노드가 동일한 경우
- 비순환 그래프: 사이클이 없는 그래프
📌 완전 그래프(Complete Graph)
- 그래프의 모든 노드가 서로 연결되어 있는 그래프
해당 게시글은 패트스캠퍼스의 알고리즘 / 기술면접 완전 정복 올인원 패키지 Online 강의를 참고하여 작성하였습니다.