隣接リストは、各ノードから 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 を実行する必要があります。順序の選択方法は、問題によって異なります。それはあなたが考えるべきことです。