7.2.2 그래프 구현(DFS 알고리즘에 사용할 그래프)

동적으로 그래프를 생성하는 함수를 구현합시다.

그래프 형식 크기의 메모리를 할당합니다.

정점을 보관할 동적 배열과 간선을 보관할 동적 배열을 생성한 후에 그래프를 반환합니다.

동적으로 생성한 그래프를 소멸하는 함수를 구현합시다.

그래프 내부에서는 간선을 동적으로 생성하므로 그래프를 소멸하는 과정에서 간선들도 소멸해야 합니다. 따라서 간선을 순차적으로 접근하기 위한 반복자 변수를 선언할게요.

간선을 보관한 동적 배열의 시작과 끝을 구합니다.

순차적으로 보관한 간선을 참조하여 메모리를 해제합니다.

정점을 보관하는 동적 배열과 간선을 보관하는 동적 배열을 소멸한 이후에 자신을 소멸합니다.

 

그래프에 정점을 추가하는 함수를 구현합시다.

먼저 이미 존재하는 정점인지 확인합니다. 만약 존재한다면 0을 반환합니다.

정점을 보관하고 1을 반환합니다.

 

간선을 추가하는 함수를 구현합시다.

먼저 두 개의 정점이 모두 그래프에 있는지 확인합니다.

두 개의 정점 사이에 간선이 이미 있다면 0을 반환합니다.

두 개의 정점이 모두 존재하고 두 정점 사이에 간선이 없는 것을 확인했다면 간선을 동적으로 생성한 후에 보관합니다. 간선을 동적으로 생성하는 함수는 별도로 구현합시다.

두 개의 정점이 모두 포함하고 있지 않을 때는 0을 반환합니다.

 

동적으로 간선을 생성하는 함수를 구현합시다.

동적으로 메모리를 할당합니다.

입력 인자로 전달받은 값으로 설정한 후에 간선을 반환합니다.

 

그래프에 특정 정점이 존재하는지 확인하는 함수를 구현합시다.

정점을 보관하는 동적 배열의 시작과 끝을 구합니다.

순차적으로 이동하면서 보관한 정점을 구합니다.

만약 보관한 정점과 입력 인자로 받은 정점을 비교하였을 때 차이가 없으면 존재하는 것이므로 1을 반환합니다.

끝까지 찾아도 없으면 0을 반환합니다.

 

그래프에 특정 간선이 존재하는지 확인하는 함수를 작성합시다.

간선을 보관하는 동적 배열의 시작과 끝을 구합니다.

순차적으로 이동하면서 보관한 간선을 구합니다.

만약 보관한 간선에 입력 인자로 받은 두 개의 정점을 포함하고 있으면 두 정점 사이의 간선이 있는 것이므로 1을 반환합니다.

끝까지 찾아도 없으면 0을 반환합니다.

 

그래프의 정보를 출력하는 함수를 구현합시다.

그래프는 정점과 간선의 집합입니다. 따라서 정점 목록을 출력하는 함수와 간선 목록을 출력하는 함수를 호출합시다.

정정 목록을 출력하는 함수를 구현합시다.

정점 목록을 출력하기 위해서는 반복자를 이용하여 순차적으로 접근해야 합니다. 이에 필요한 변수를 선언합니다.

먼저 정점 개수를 출력합시다.

정점을 보관하는 동적 배열의 시작과 끝을 구합니다.

순차적으로 보관한 정점을 구하여 콘솔 화면에 출력합니다.

 

간선 목록을 출력하는 함수도 구현합시다.

간선 개수를 출력합시다.

간선을 보관하는 동적 배열의 시작과 끝을 구합니다.

순차적으로 이동하여 간선을 구합니다.

간선의 두 정점과 무게(거리)를 출력합니다.

 

이번에는 특정 정점의 이웃 정점 목록을 구하는 함수를 작성합시다.

특정 정점과 이웃하는 정점 목록을 구하려면 간선 집합에서 해당 정점을 끝점으로 하는 간선을 찾아야 합니다. 이를 위해 반복자와 보관한 간선을 기억할 변수를 선언합시다.

간선을 보관하는 동적 배열의 시작과 끝을 구합니다.

순차적으로 이동하면서 보관한 간선을 구합니다.

만약 해당 간선에 입력 인자로 받은 정점을 포함하고 있다면 나머지 한 점이 이웃하는 정점입니다. 간선에 특정 정점을 포함하는지 확인하는 함수는 별도로 구현합시다.

나머지 정점을 구합니다. 이 부분은 별도의 함수로 작성합시다.

구한 정점을 이웃 목록에 추가합니다.

 

간선에 특정 정점을 포함하는지 확인하는 함수를 작성합시다.

간선의 두 정점 중에 입력 인자로 받은 정점과 문자열 비교했을 때 차이가 없는 정점이 있으면 포함하고 있는 것입니다.

 

간선에 특정 정점이 아닌 나머지 정점을 구하는 함수를 작성합시다.

만약 간선의 한 정점과 비교하여 차이가 없다면 나머지 정점을 반환합니다.

입력 인자로 받은 정점이 간선의 두 정점과 비교하여 차이가 있다면 빈 문자열을 반환합시다.

 

그래프의 두 정점 사이의 간선의 무게(거리)를 찾는 함수를 작성합시다.

간선 집합의 시작과 끝을 구합니다.

순차적으로 이동하면서 보관한 간선을 구합니다.

만약 해당 간선에 입력 인자로 받은 두 정점을 포함하고 있다면 두 정점 사이의 간선입니다. 이 때는 간선의 무게(거리)를 반환합니다.

두 정점을 포함하는 간선을 찾지 못하면 음수를 반환합니다.

참고로 그래프에서 정점과 정점 사이의 거리를 비중 혹은 무게로 많이 표시합니다. 이 책에서 매 번 간선의 거리를 말할 때 무게(거리)라고 표현하고 있는데 논리적으로 보면 거리가 맞는 말이고 일반적으로 그래프에서 사용하는 용어는 비중 혹은 무게로 말할 때가 많기 때문입니다.