백과

그래프를 다루는 각종 알고리즘의 총칭. 그래프를 다루는 고능률 산법에서는, 입력의 그래프를 표현하는 데에, 인접행렬을 직접배열로 표현하는 방법(행렬표현(그래프의) 참고), 또는 노드와 가지의 접속관계를 포인터로 표현하는 방법(리스트 표현(그래프의) 참고) 등이 쓰인다. 이것들은, 산법 자체의 구조라든가 그것들의 사용상황에 따라서 선택된다.

주어진 그래프를 검색해서 그 성질을 알아보는 데는 여러 가지 검색의 방법을 생각할 수 있는데, 특히 깊이 우선검색과 폭 우선검색이 흔히 쓰인다. 이 계통적인 검색을 기초로 하는 산법으로, 무향 그래프를 2연결성분(연결성 참고)으로 분해하는 것, 그래프가 평면 그래프인가 아닌가를 판정하는 것(평면 그래프의 판정 참고)을 비롯하여, 수많은 문제를 고속으로 풀 수 있다.

대개의 경우, 이와 같은 산법은 단지 이론적으로 고능률이라는 것뿐만 아니라, 실제의 프로그램으로서 실현하더라도 고속이고 실용성이 높다. 최단로 문제·최소 전역 트리·최대 플로 문제 등으로 대표되는 네트워크의 문제에 대해서도, 그래프 구조를 이용한 고능률 산법으로 실용적인 것이 많다. 그리고, 그래프에 관련되는 문제에서는, 여기서 든 예와 같은 이른바 클래스 P(다항식 시간계산 참고)에 속하는 문제뿐만 아니라, 실용적으로 중요한 문제 중에도 NP완전문제 등 힘이 너무 들어서 풀기가 어려운 것으로 알려져 있는 문제가 많다.