문제 설명
깊이 우선 탐색 가능한 노드 (Depth First Search Possible Nodes)
깊이 우선 탐색과 너비 우선 탐색을 수행할 때 주어진 그래프 노드를 방문할 수 있는 가능한 순서를 찾으려고 합니다. 깊이 우선 검색을 하면 FACBDE를, 너비 우선 검색을 하면 FACDEB를 얻었습니다. 이미지를 보려면 여기를 클릭하십시오. 하지만 이것이 정답인지 확실하지 않습니다. 누군가 그것을 확인하고 내 대답이 맞다고 말해 주시겠습니까?
참조 솔루션
방법 1:
I'll waste no time by saying that your BFS and DFS answers do look correct. I'm assuming that the nodes that are given are to be ordered lexicographically. Are you asking this question because you are confused by how each search method works?
Keep in mind that if you get confused, you can always think of BFS as level based search. So, search for all neighbors in respective order. And DFS is more brute forced search. I'd recommend memorizing the psuedo code for each of these search methods. It helps a bunch when your actually coding these things.
BFS:
- enqueue start node and mark as visited
- start loop
- find all neighbors and if not already visited mark as visited
- add new visited to queue
- search for goal
- dequeue ( pop first element off the queue )
- repeat...
DFS:
- add start node to stack
- start loop
- find first encountered and unvisited neighbor
- mark as visited
- add to stack
- if no neighbors, pop stack
- repeat...
방법 2:
DFS is correct. BFS should be FACEDB.
When expanding A, the order should be C‑>E‑>D according to the edge number.
(by davidnahm、afterShock、immiao)