-1

したがって、グラフでの幅優先検索と深さ優先検索の基本は知っていますが、隣接リストで両方を実行する方法がわかりません。各検索は 0 から始まります。

0 -> 5 -> 2 -> 1 -> 6

1 -> 7 -> 0

2 -> 7 -> 0

3 -> 5 -> 4

4 -> 6 -> 5 -> 7 -> 3

5 -> 0 -> 4 -> 3

6 -> 4 -> 0

7 -> 1 -> 2 -> 0 -> 4

どこから始めればよいかわかりません。私はこれを学ぶ必要があるので、説明していただければそれは素晴らしいことです。

4

1 に答える 1

10

隣接リストは、各ノードから 1 ホップで到達できるノードを示します。この例では、ノード 0 はノード 5、ノード 2、ノード 1、およびノー​​ド 6 に到達できます。

BFS の場合について説明します。これを理解すれば、DFS の場合でも問題はないでしょう。

BFS では、疑似コードは次のようになります。

Let graph be your adjacency list.
bool visited[num_nodes]; // Array of booleans to keep track if a node was visited.
for (int i = 0; i < num_nodes; i++)  // Set status of all nodes to be not visited.
  visited[i] = false;
start_node = 0; // E.g. start BFS at node 0.
visited[start_node] = true;
queue = Queue(); // Queue for keeping track of which node to check next
queue.append(start_node);
while (!queue.empty()) // While there is still nodes to check
{
 node = queue.pop_front(); // Get the node at the front of the queue.
 // For each of the neighbor of this node
 // This is where we make use of the adjacency list which tells us which nodes are the neighbors
 // of some other nodes.
 neighbors_of_node = graph[node];
 for (int i = 0; i < neighbors_of_node.size(); i++)
 {
  neighbor = neighbors_of_node[i];
  if (!visited[neighbor]) // If this node was not visited previously
  {
   do_something_with(neighbor);
   visited[neighbor] = true; // Indicate that we have visited this neighbor node.
   queue.append(neighbor);
  }
 }
}

上記のコードは、開始ノードから到達可能なすべてのノードにアクセスします。グラフが全結合要素でない場合はどうなるでしょうか? すべてのノードにアクセスする必要がある場合は、BFS の最後に残りのノードの 1 つから開始して、繰り返し BFS を実行する必要があります。順序の選択方法は、問題によって異なります。それはあなたが考えるべきことです。

于 2013-05-07T04:27:20.620 に答える