BFS и DFS в списке смежности
Таким образом, я знаю основы поиска в ширину и поиска в глубину на графиках, но я не могу понять, как выполнить их оба в списке смежности. Каждый поиск начинается с 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
Я не уверен, с чего начать. Мне нужно изучить это, так что, если вы могли бы объяснить, это было бы здорово.
Решение
Список смежности показывает, к каким узлам вы можете добраться за 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. Как вы выбираете заказ, зависит от вашей проблемы. Вам будет о чем подумать.
Другие решения
Других решений пока нет …