algorithm - 有向グラフ - 到達不能ノード

Question

有向加重グラフで到達できないノードを見つける最良の方法は何ですか? 私はすでにパスファインディングに A* を使用しています。したがって、データにはノード、リンク、および隣接リストのリストが含まれます。私は BFS/DFS (どちらが正しいですか??) を考えていて、マークされていないノードを探します。ノードの数は 100 ～ 200 になる可能性があるため、大きなグラフではありません。より良い方法はありますか？

Answer 1

どこから到達できませんか? 開始ノードを指定する必要があります。bool[]グラフ ノードごとに 1 つのエントリを入力する BFS が機能します。この場合、ノード ビジット操作によって node のbool[i]が true に設定されますi。最後に、 がi付いbool[i]==falseているノードは、到達できないノードです。これは、実行時間に関して最適なはずです。BFSフロンティア/キューの「開始ノード」から始めます。