그래프는 현상이나 사물을 정점과 간선으로 표현하는 것이며,
정점은 대상이나 개체를 나타내고, 간선은 이들과의 관계를 나타낸다.
그래프는 두가지로 나누어 지는데
방향을 가진 관계의 그래프 예를 들어 기업간의 제품공급관계, 제품 생산 공정에서의 선후 관계를 나타내는 그래프는
유향그래프 라고 하며, 간선의 방향이 없는 그래프는 무향그래프, 무방향 그래프 라고 한다.
그래프에서는
1. 그래프의 표현
2. 너비 우선 탐색BFS 과 깊이 우선 탐색DFS
3. 최소신장트리
4.위상 정렬
5. 최단 경로
6. 강연결 요소
를 다뤄보도록 한다.
1. 그래프의 표현
그래프의 표현법에는 행렬을 이용한 인접행렬방법과, 인접 리스트를 이용한 방법, 인접배열과 인접 해시 테이블 세가지로 나눠진다.
1. 인접행렬 방법
2. 인접 리스트를 이용한 방법
3. 인접배열과 인접 해시 테이블
간선의 밀도가 아주 높은 그래프는 인접행렬 표현이 적합하다.
인접리스트로서의 표현법은 각 정점에 인접한 정점들을 리스트로 표현 하는 방법이다.
인접 리스트는 공간이 간선의 총수에 비례하는 양만큼 필요하므로 대체로 행렬 표현에 비해 공간의 낭비가 없다.
모든 가능한 정점 쌍에 비해 간선의 수가 적을 때 유용하게 사용할 수 있다.
그리고, 인접 리스트 표현법은 간선의 밀도가 아주 높은 경우에는 그리 적합하지 않다.
간선 밀도가 높은 경우에는 인접 행렬 표현법이 더 낫다.
인접배열과 인접 해시 테이블 방법은 인접 리스트처럼 간선의 수에 비례하는 공간을 쓰면서 간선의 존재 여부를 훨씬 빨리 체크할 수 있는 방법이다.
각 정점의 인접 배열을 위해 각 공간을 따로 할당 받을 수도 있고 공간 사용의 깔끔함을 위해 하나의 배열을 할당받은 다음 같이 사용할 수도 있는 것이다. 우선 각 인접 배열 크기를 더해 필요한 전체 배열 크기를 다 계산한 다음 하나의 배열을 할당받고, 각 헤더에는 자신의 인접 배열이 끝나는 자리를 표시해 둔다.
이 방법은 공간사용은 인접리스트에 준하고 검색시간은 대폭 줄여 실용적으로 손색이 없지만, 다루어야할 그래프가 엄청난 크기면 탐색에 한계가 생기게 된다.
2. 너비 우선 탐색BFS 과 깊이 우선 탐색DFS
그래프에서 모든 정점을 방문해야 할 떄가 자주 있는데, 대표적인 방법으로
너비 우선 탐색 BFS
깊이 우선 탐색 DFS
이 두가지가 있다. 이 두방법은 매우 간단하지만 그래프 알고리즘에서 핵심적 위치를 차지한다.
그러므로 이 두 탐색 방법에 대해서는 아주 깊은 직관을 갖고 있을 필요가 있다.
너비우선 탐색 BFS
먼저 루트의 자식을 차례로 방문한다. 다음으로 루트의 자식의 자식, 즉 루트에서 두개의 간선을 거쳐서 도달할 수 있는 정점을 방문한다. 또 다음으로 루트에서 세 개의 간선을 거쳐서 도달하는 정점들 순으로 루트에서 거리순으로 방문한다.
옆으로 쭉 훑어 나가는 방법
깊이 우선 탐색 DFS
자식 정점을 하나 방문한 다음 아래로 내려갈 곳이 있으면 즉각 내려간다. 아래로 갈 수 있는 데 까지 갔다가 막히면 되돌아 와서 다시감.
3. 최소신장트리