グラフを使用して都市間マップを実装しています。無向なので、Graph クラスで頂点のベクトルと「辺の配列へのポインター」のベクトルを使用する上三角隣接行列を使用しました。
そのようなグラフをトラバースする必要があります。頂点には情報があり、エッジには重みが付けられています。
直接アクセスによってすべての頂点とエッジの情報を既に持っているのに、なぜこのようなトラバーサルで BFS や DFS が必要になるのでしょうか?
1 に答える
0
一般に、次の場合:
すべての頂点に (頂点のリストなどの形式で) 直接アクセスできます。
ある頂点からどの頂点に到達できるかなど、BFS または DFS から取得した情報は必要ありません。
次に、BFS や DFS を使用せずに、頂点のリストを直接反復処理できます。
BFS と DFS は確かに便利ですが、アプリケーションで必要とされない場合は使用する気はありません。
サイドノート - 隣接行列の BFS と DFS は(隣接するものを見つけるために頂点ごとO(|V|^2)に一定の作業を行う必要があるため) かかると思いますが、直接トラバーサルには.O(|V|)O(|V|)
于 2013-12-25T16:37:49.000 に答える