C++ 그래프 graph, 깊이우선탐색 depth first search 구현 (미완)

* 본문은 <C++로 구현하는 자료구조와 알고리즘>(범한서적주식회사, 2013)을 공부하면서 작성한 글입니다. 향후 객체지향 및 자료구조 수업을 들으며 정확한 + 최신 내용 이해를 반영하여 보완해 나갈 것입니다.

 

1. 그래프 ADT(비방향성 그래프)

그래프는 그래프의 위치, 즉 정점(vertex)과 간선(edge)에 저장된 원소들의 모임이다. 각 vertex 객체 u는 다음과 같은 연산을 지원한다.

- operator*(): u와 연관된 요소 반환

- incidentEdge(): u에 연결된 간선들의 간선 리스트 반환

- isAdjacentTo(v): u, v가 인접한지 테스트

 

각 edge 객체 e는 다음과 같은 연산을 지원한다.

- operator*()

- endVertices: e의 끝 정점을 포함하는 정점 리스트 반환

- opposite(v): 정점 v와 구별되는 간선 e의 끝 정점 반환. e가 v에 연결되지 않으면 오류 발생

- isAdjacentTo(f): e와 f가 인접한지 테스트

- isIncidentOn(v): e가 v에 연결되어 있는지 테스트

 

- vertices(): 그래프 모든 정점들에 대해 정점 리스트 반환

- edges(): 그래프 모든 간선에 대한 간선 리스트 반환

- insertVertex(x): x를 저장하는 새로운 정점을 삽입하고 반환

- insertEdge(v,w,x): 끝 정점 v와 w를 갖는 새로운 비방향 간선 삽입 후 반환, 그리고 요소 x에 저장

- eraseVertex(v): 정점 v와 그것에 연결된 모든 간선 제거

- eraseEdge(e)

 

이를 구체적인 코드로 정의하면 아래와 같다.

 

 

2. 깊이 우선 탐색 (DFS) 구현

데코레이터 패턴을 이용해 노드 방문 여부 yes, no를 결정한다. 데코레이터 패턴에 대한 개념은 아래 글을 참고하자.

https://gmlwjd9405.github.io/2018/07/09/decorator-pattern.html

그리고 아래는 깊이 우선 탐색 코드다. 그래프의 코드는 아직 구현하지 않았다.