Как написать функцию BFS в C ++? - PullRequest
Новая
       34

Как написать функцию BFS в C ++?

0 голосов
/ 19 февраля 2020 
#include <iostream>
#include <string>
#include <queue>

using namespace std;
void BFS(const string&, const string[], int[][10]);

int main()
{
    const int CAP = 10;

    string states[CAP] = { "Arizona", "California", "Idaho", "Nevada", "Oregon", "Utah", "Washington" };
    string Point;

    int matrix[CAP][CAP] =
    {
    {0,1,0,1,0,1,0},
    {1,0,0,1,1,0,0},
    {0,0,0,1,1,1,1},
    {0,1,1,1,0,0,1},
    {1,1,1,1,0,0,0},
    {0,0,1,0,1,0,0},
    {0,0,1,0,1,0,0}
    };


    BFS("California", states, matrix);


}

void BFS(const string& Point, const string states[], int matrix[][10])
{
    int SPoint = 0;
    queue<string> visited;
    queue<string> Queue;


    string temp = Point;

    visited.push(temp);
    do
    {

        for (int i = 0; i < 10; i++)
        {
            if (states[i] == temp)
            {
                SPoint = i;
            }
        }
        for (int i = 0; i < 10; i++)
        {
            if (matrix[SPoint][i] == 1)
            {
                Queue.push(states[i]);
            }
        }

        visited.push(Queue.front());
        Queue.pop();

        temp = visited.back();

    } while (!Queue.empty());


    for (int i = 0; i < 10; i++)
    {
        cout << visited.front();
        visited.pop();
    }


}

Я делаю упражнение, в котором я должен создать функцию, которая выполняет поиск в ширину и распечатывает посещенный путь. Но моя функция ничего не печатает. Что я здесь не так делаю?

Примечание. Матрица представлена ​​в алфавитном порядке и представляет связь между штатами.

Мой ожидаемый результат: Калифорния, Аризона, Орегон, штат Невада, штат Юта, Айдахо, Вашингтон

Описание упражнения

1 Ответ

2 голосов
/ 19 февраля 2020

Хотя я не буду предлагать полное решение, я могу помочь выявить некоторые проблемы, возникающие в коде.

Основные проблемы

  • Поскольку у вас есть цикл c На графике важно пометить узлы как посещенные во время BFS, иначе вы получите бесконечный l oop (именно поэтому в вашей текущей реализации ничего не печатается). Ваша visited очередь может быть unordered_set. Когда узлы посещаются, добавьте их в набор и напишите условие, чтобы избежать их повторного посещения.
  • Матрица смежности выглядит неправильно. Поскольку это неориентированный график, я ожидаю, что матрица будет отображаться сверху вниз слева направо, но это не так. Кроме того, в графе нет собственных ребер, но Невада, похоже, имеет в себе ребро в матрице.
  • Нет необходимости в l oop над матрицей смежности - вы можете индексировать в нее с помощью Соответствующее отображение di git индексов и имен строк. Если вам нужно l oop, бег до 10 выходит за пределы матрицы 7x7.

Незначительные проблемы

  • Нет смысла произвольно ограничивать размер матрицы. Несмотря на то, что назначение обеспечивает это, это плохой выбор дизайна, потому что код должен быть переписан всякий раз, когда вы хотите использовать другой входной граф.

  • Матрица выглядит немного неуклюжей структурой данных, потому что она вводит дополнительный уровень косвенности для перевода строк в целые числа и обратно. Хотя проект этого не разрешает, я бы предпочел использовать такую ​​структуру, как: 

    std::unordered_map<std::string, std::vector<std::string>> graph({
    {"California", {"Oregon", "Nevada", "Arizona"}},
    // ... more states ...
});

    В идеале это были бы Node объекты с neighbor векторными членами вместо строк.

  • C ++ предлагает std::vector и std::array, которые предпочтительнее массивов C. Я предполагаю, что они еще не были введены в вашем классе или не разрешены в задании, но если вы застряли, вы можете попробовать написать код, используя их, а затем вновь ввести ограничения вашего инструктора после того, как вы заработаете. Если ничего другого, это был бы опыт обучения.
  • Избегайте using namespace std;.
  • Зарезервируйте имена переменных в верхнем регистре для имен классов. Объекты и примитивы должны быть в нижнем регистре.

Псевдокод для BFS

Предполагается, что предпочтительная структура данных указана выше; Вы можете конвертировать в и из строк и индексов матрицы смежности по мере необходимости. 

func BFS(string start, unordered_map<string, vector<string>> graph):
    vector traversal
    queue worklist = {start}
    unordered_set visited = {start}

    while !worklist.empty():
        curr = worklist.pop_front()            
        traversal.push_back(curr)

        for neighbor in graph[curr]:
            if neighbor not in visited:
                visited.insert(neighbor)
                worklist.push(neighbor)

    return traversal

Поскольку это задание, я оставлю это здесь и позволю вам еще раз взломать код. Удачи.

...