c++ - 邻接表上的 BFS 和 DFS

Question

所以我知道图上的广度优先搜索和深度优先搜索的基础知识，但我似乎无法弄清楚如何在邻接列表上执行它们。每次搜索从 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

我不知道从哪里开始。我需要学习这个，所以如果你能解释一下，那就太好了。

Answer 1

邻接列表告诉您可以在每个节点的 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 结束时从剩余节点之一开始重复执行 BFS。您如何选择订单取决于您的问题。这将是你需要考虑的事情。