알고리즘 - 그래프

그래프

• 그래프: 복잡하게 연결된 객체 사이의 관계를 효율적으로 표현할 수 있는 자료구조
• 정점(객체)과 간선(위치 간의 관계, 다리)의 집합으로 구성

그래프의 종류

• 무방향 그래프: 두 정점을 연결하는 간선에 방향성이 없는 그래프, 간선은 양방향으로 갈 수 있는 길
• 방향 그래프: 간선에 방향이 있는 그래프, 다이그래프, 간선은 한 방향으로만 갈 수 있는 길
• 완전 그래프: 모든 정점 사이에 간선이 존재하는 그래프
• 부분 그래프: 원래의 그래프에서 정점이나 간선 일부만을 이용해 만든 그래프
• 가중치 그래프: 간선에 가중치가 할당된 그래프 => 네트워크

그래프의 용어

• 인접(adjacent): 간선으로 연결된 두 정점을 인접해 있다고 말함
• 정점의 차수(degree): 정점에 연결된 간선의 수 방향 그래프에선 외부에서 오는 간선의 수 => 진입 차수, 외부로 향하는 간선의 수 => 진출 차수
• 경로(path): 간선을 따라갈 수 있는 길을 순서대로 나열한 것
• 경로 길이(path length): 경로를 구성하는 간선의 수
• 단순(simple) 경로: 반복되는 간선이 없는 경로 ex. B-A-C-A 는 단순경로가 아님
• 사이클(cycle): 시작 정점과 종료 정점이 같은 단순 경로
• 연결(connected) 그래프: 모든 정점 사이에 경로가 존재하는 그래프
• 트리(tree): 사이클을 가지지 않는 연결 그래프