10.4 깊이 우선 탐색(정점과 간선 그래프)

이번에는 그래프를 정점(Vertex)과 간선(Edge) 집합으로 표현한 후에 깊이 우선 탐색을 구현해 보아요.

먼저 간선을 정의합시다. 여기에서는 방향성 없는 그래프로 표현할게요.

간선의 두 정점을 멤버 필드로 추가하세요.

생성할 때 두 개의 정점을 입력 인자로 받습니다.

특정 점정을 포함하는지 판별하는 메서드를 제공하세요.

두 개의 정점을 포함하는지 판별하는 메서드도 제공하세요.

하나의 정점을 입력 인자로 받은 후에 나머지 정점을 반환하는 메서드도 제공하세요.

간선 정보를 출력하는 메서드도 제공합시다.

간선 생성자에서는 입력 인자로 전달받은 값으로 멤버 필드를 설정하세요.

정점을 포함하는지 판별하는 메서드를 구현하세요.

두 개의 정점을 모두 포함하는지 판별하는 메서드를 구현하세요.

하나의 정점을 입력 인자로 받아 나머지 정점을 반환하는 메서드를 구현하세요.

간선의 정보를 출력하는 메서드를 구현하세요.

이제 Graph 클래스를 구현합시다. 제공할 기능은 인접 행렬로 구현한 그래프와 비슷하겠죠.

먼저 정점의 집합을 Vertexs로 타입 재지정하세요.

Edge *의 집합을 Edges로 타입 재지정하세요.

Graph 클래스를 정의합시다.

그래프에는 정점의 집합인 Vertexs 형식 멤버와 간선의 집합인 Edges 형식 멤버가 필요합니다.

제공할 메서드를 추가합시다.

Grpah 소스 코드를 작성합시다. 먼저 소멸자를 먼저 구현하기로 해요.

그래프 내에서 간선을 동적으로 생성합니다. 그래프의 소멸자에서는 간선 집합에 보관하고 있는 간선들을 소멸하세요.

정점을 추가하는 메서드를 구현합시다.

먼저 정점이 존재하는지 확인하세요. 존재하면 추가하지 않고 거짓을 반환합니다.

존재하지 않을 때 정점 집합에 추가하세요.

정점이 존재하는지 판별하는 메서드를 구현하세요.

간선을 추가하는 메서드를 구현하세요.

먼저 두 개의 정점을 포함하는지 확인하세요.

그리고 두 개의 정점을 잇는 간선이 이미 있는지 확인하여 이미 있다면 거짓을 반환하세요.

없을 때 간선을 생성하여 간선 집합에 추가한 후에 참을 반환하세요.

두 개의 정점이 모두 포함하고 있지 않을 때 거짓을 반환하세요.

두 개의 정점을 잇는 간선이 존재하는지 판별하는 메서드를 구현하세요.

간선 집합을 순차적으로 순회합니다.

현재 반복자의 위치에 간선이 두 개의 정점을 포함한다 존재하는 것이므로 참을 반환하세요.

전체를 순회하여 조사하였는데 없으면 거짓을 반환하세요.

모든 정점의 이웃을 출력하는 메서드를 구현하세요.

정정 집합을 순차적으로 순회합니다.

특정 정점의 이웃을 출력하는 메서드를 구현하세요.

특정 정점의 이웃을 출력하는 메서드를 구현하세요.

간선 집합을 순차적으로 순회하세요.

간선에 입력 인자로 받은 정점이 존재하면 다른 나머지 정점을 출력하세요.

같은 방법으로 특정 정점의 이웃하는 정정 집합을 구하는 메서드를 구현하세요.

간선에 입력 인자로 받은 정점이 존재하면 다른 나머지 정점을 이웃 정점 집합에 추가하세요.

경험 정보 클래스는 인접 행렬을 이용한 깊이 우선 탐색의 코드와 차이가 없습니다. 10.3.3 을 참고하세요.

진입점 main에서도 그래프를 동적 생성하여 정점을 추가하는 앞부분만 차이가 있을 뿐 간선 추가부터는 똑같습니다.

다음은 테스트에 사용한 그래프입니다.방향성 없는 그래프

 

▷ 실행 결과