qhrrkfl2   1년 전

일단 그래프는 무방향 그래프이고 윤성우 아재의 코드를 베끼듯이 만들었습니다.

탐색은 깊이 우선 탐색이며

이미지를  보시면 실행시 0 1 3 4 5 2 방문이여야 하는데

0 1 3 2 4 5 방문을 합니다.

뭐가 문제죠?

그림이 업로드 안되네요;;;

0 - 1 -           -  4

              3         ↕

0 - 2-           -    5

연결은 이렇게 되어있습니다

0-1

0-2

1-3

2-3

3-4

3-5

4-5

washi   1년 전

3번 vertex와 연결된 vertex들의 순서가 1 2 4 5 순으로 되어있어서 dfs하시면 2번 vertex 먼저 방문을 하게 될 것 같아요

qhrrkfl2   1년 전

2번 먼저 방문하면 틀린 순회인가요?

washi   1년 전

아뇨 틀린 순회는 아니에요.

DFS는 깊이 우선 탐색이니 

맨 처음 0에서 시작을 하시면

0에서 방문 가능한 vertex를 찾음 -> 1을 찾아서 이동 -> 1에서 방문 가능한 vertex를 찾음 -> 3을 찾아서 이동 -> 3 에서 방문 가능한 vertex를 찾음 -> 2를 찾아서 이동 -> 2에서 방문 가능한 vertex를 찾음 -> 방문 가능한 vertex가 없으므로 3번 vertex로 돌아감 -> 3번 vertex에서  방문 가능한 vertex를 찾음 -> 4를 찾아서 이동 -> 4에서 방문 가능한 vertex를 찾음 -> 5를 찾아서 이동 -> 5에서 방문 가능한 vertex를 찾음 -> 없으므로 4로 돌아감 -> 4에서 방문 가능한 vertex를 찾음 -> 없으므로 3으로 돌아감 -> 1번에서 방문 가능한 vertex를 찾음 -> 없으므로 0으로 돌아감 -> 0에서 방문 가능한 vertex를 찾음 -> 없으므로 dfs 종료

정상적으로 순회하네요 @[email protected]

DFS에 관련된 내용을 좀 보시면 도움이 되실꺼같아요.

qhrrkfl2   1년 전

답변감사합니다.

댓글을 작성하려면 로그인해야 합니다.