10.4 깊이 우선 탐색(정점과 간선 그래프) [소스 코드]

다음은 정점과 간선 그래프로 표현한 깊이 우선 탐색 알고리즘의 전체 코드입니다.

여기에서는 간선의 무게(비중 혹은 비용, weight)나 정점의 이름을 부여하지는 않았습니다. 다음에 너비 우선 탐색을 하면서 간선의 무게나 정점의 이름을 부여하는 그래프도 다루기로 할게요.

그리고 이 책에서는 최소 신장 트리를 다루면서 다시 그래프를 이용할 거예요. 이번 장에서는 그래프를 이용한 깊이 우선 탐색 알고리즘은 동적 알고리즘으로 구현하 수 있다는 것에 초점을 두었습니다.

원본 그래프와 출발지, 목적지를 설정한 초기 경험 정보를 생성

스택에 보관

반복(스택이 비어 있지 않다면)

    스택에서 경험 정보 꺼내옮

    스택에서 꺼내온 경험 정보에서 다음 경험(이웃을 방문하는) 목록 조사

    반복(다음 경험 목록을 순차적으로 반복)

        목적지에 도달하면

            결과 출력

        그렇지 않다면

            스택에 보관