지시 가중 그래프에서 도달 할 수없는 노드를 찾는 가장 좋은 방법은 무엇입니까? 이미 길 찾기에 A *를 사용하고 있습니다. 따라서 데이터에는 노드, 링크 및 인접성 목록의 목록이 포함됩니다. 나는 BFS/DFS (오른쪽 하나인가?)를 생각하고 있었고 표시가없는 노드를 찾는다. 노드 수는 100 - 200 일 수 있으므로 큰 그래프가 아닙니다. 더 좋은 방법이 있습니까?지향 그래프 - 연결할 수없는 노드
BFS 또는 DFS 중 어떤 것이 좋을 것입니다 : 노드의 일부를 도달 할 수 없다고 선언하기 전에 시작 정점에서 전체 하위 그래프를 트래버스해야하므로 도달 할 수있는 노드를 어떤 순서로 발견하는지는 중요하지 않습니다. 큰 그래프가 아니기 때문에 재귀 DFS는 문제가되지 않습니다. 실제로 그래프가 목록이라도 200 개의 노드가 스택 오버플로를 위협 할만큼 충분하지 않아야하기 때문입니다.
도달 할 수 없음 여기서? 시작 노드를 주어야합니다. 각 그래프 노드에 대해 하나의 항목으로 bool[]을 채우는 BFS가 작동합니다. 노드 방문 작업은 노드 i에 대해 bool[i]을 true로 설정합니다. 결국 노드 i은 bool[i]==false으로 도달 할 수 없습니다. 이것은 런타임 측면에서 최적이어야합니다. BFS 프론티어/대기열에서 "시작 노드"로 시작하십시오.
BFS가 최선의 선택이 될 것입니다 ... 나는 그보다 더 좋은 방법이 있다고 생각합니다. – Bill
요즘 그래프에 관한 많은 질문이 있습니다. 이번 학기에 제 수업이 아니길 바래요. – Woot4Moo