При поиске по ширине не удается найти существующее назначение - PullRequest
Новая
       20

При поиске по ширине не удается найти существующее назначение

0 голосов
/ 29 апреля 2018

Итак, я работал над поиском Breadth First , чтобы получить путь с начальным и конечным узлом. Однако в некоторых случаях он кажется неудачным и не может найти путь, который, как я знаю, возможен, поскольку поиск в глубину и визуальный осмотр показывают, что он должен существовать.

У меня есть матрица смежности: 

     1       2       3       4       5       6       7       8

 1   0       20      25      20      0       0       0       0
 2   20      0       5       0       30      0       0       0
 3   25      5       0       13      8       21      0       0
 4   20      0       13      0       0       17      0       0
 5   0       30      8       0       0       33      0       0
 6   0       0       21      17      33      0       0       0
 7   0       0       0       0       0       0       0       10
 8   0       0       0       0       0       0       10      0

Который имеет следующий график: Graph

Это моя функция: 

void Network::BFS(int src, int dest, vector<bool>& visited, vector<int>& path) {
    // The Queue is the core for the BFS.
    queue<int> Queue;
    // Mark current node as visited.
    visited[src] = true;
    Queue.push(src);
    // While queue is not empty.
    while (!Queue.empty()) {
        // Add node to path.
        // Check if we have found the destination yet or not, if we have we do one last push to path and we're done!
        if (Queue.front() == dest) {
            return;
        }
        int top = Queue.front();
        path.push_back(Queue.front());
        // Pop off front.
        Queue.pop();
        // Iterate and process all none visited nodes.
        for (int node = 0; node < amountOfNodes; node++) {
            // Check if it is not visited already.
            if (visited[node] == false && (adjMatrix[node * amountOfNodes + src] != 0)) {
                Queue.push(node); // Add to end.
                visited[node] = true;
            }
        }
    }
}

Пример ввода и вывода:

(6, 3) -> Путь: 6

(1, 5) -> Путь: 1 2 3 4

Как видите, он вообще не правильно вычисляет путь. Где мой алгоритм работает неправильно и как я могу это исправить?

1 Ответ

0 голосов
/ 29 апреля 2018

BFS включает в себя посещение соседних узлов в режиме FIFO. Добравшись до узла, вы помещаете в очередь всех его соседей, если они еще не были посещены.

Во-первых, есть опечатка, в которой вы перебираете соседние узлы. Вы хотите пройти по столбцу top, а не по src: 

adjMatrix[node * amountOfNodes + top] != 0
//                               ~~^

Во-вторых, ваша текущая path реализация хранит порядок посещения узлов, не путь от источника до места назначения. Для последнего вам нужно сохранить родительский узел каждого узла, чтобы можно было восстановить окончательный путь, перейдя от дочернего (конечного пункта) к его родительскому, дедушке, прапрадедушке, ... и т. Д. 

std::vector<int> parent(amountOfNodes, -1);

//...

if (visited[node] == false && (adjMatrix[node * amountOfNodes + top] != 0))
{
    Queue.push(node); // Add to end.
    visited[node] = true;
    parent[node] = top;
}

Восстановление пути не вызывает затруднений: 

int u = dest;            
do
{
    std::cout << u << " ";
    u = parent[u];
}
while (u != -1);

DEMO

...