Матрица смежности BFS (поиск в ширину) C ++

Question

Я пытаюсь изучить BFS (поиск в ширину) с матрицей смежности.

Что я пробовал:

• вообще не знал, что такое BFS, поэтому я выучил концепцию и псевдокод
• попробовал посмотреть примеры
• попытался реализовать с указателем на версию массива ниже

Цель:

• хочу убедиться, что я правильно делаю BFS, используя указатель на матрицу массива

График Класс для матрицы смежности:

#include <iostream>
#include <queue>
using namespace std;

class Graph {
private:
    bool** adjMatrix;
    int numVertices;
    bool* visited;
public:
    //constructor
    Graph(int numVertices) {
        this->numVertices = numVertices;
        adjMatrix = new bool*[numVertices];
        for(int i = 0; i < numVertices; i++) {
            adjMatrix[i] = new bool[numVertices];
            for(int j = 0; j < numVertices; j++)
                adjMatrix[i][j] = false;
        }

        visited[numVertices]; //init visited array


    }

    //member function
    void BFS(int sp) {
        //make a queue of type int
        queue<int> Q;

        //make bool visited array & mark all positions unvisited
        for(int i = 0; i < numVertices; i++)
            visited[i] = false;

        //push sp into queue
        Q.push(sp);

        //mark sp as visited
        visited[sp] = true;

        //while queue isn't empty
        while(!Q.empty()) {

            //make temp node
            int temp = Q.front();

            //pop temp node
            Q.pop();

            //use loop & check if it has children
            int rows =  sizeof adjMatrix / sizeof adjMatrix[0]; //get row size
            for(int i = 0; i < rows; i++) { //check neighboring nodes
                if(!visited[i] && adjMatrix[sp][i] == true) {
                    Q.push(i); //if so push them into queue
                    visited[i] = true; //mark children as visited
                }
            }
        }

    }



};

Answer 1

Хорошо, поскольку вы не прикрепили свой журнал ошибок или выходные данные тестового примера, рассмотрите приведенную ниже реализацию

#include <iostream>
#include <queue>
#include <vector>
#include <set>
#include <cstdlib>

// using namespace std;   Don't do this. Good CPP production code uses separate namespaces 

const int BUFFER_CLEAR_VALUE = 999;

class Graph {
private:
    std::vector<std::vector<bool> > adj_mat;

public:
    //constructor
    Graph() {
        std::cout << "Enter vertex num" << std::endl;
        int num_vertices;
        std::cin >> num_vertices;
        while (std::cin.fail()) {
            std::cout << "Enter a valid num" << std::endl;
            std::cin.clear();
            std::cin.ignore(BUFFER_CLEAR_VALUE, '\n');
            std::cin >> num_vertices;
        }
        for (int i = 0; i < num_vertices; i++) {
            std::vector<bool> temp;
            temp.resize(num_vertices);
            adj_mat.push_back(temp);
        }
    }

    // member fn
    void initialize() {
        for (int i = 0; i < adj_mat.size(); i++) {
            for (int j = 0; j < adj_mat[0].size(); j++) {
                char choice;
                do {
                    std::cout << "Enter adj mat value for [y/n] " << i << ":" << j << std::endl;
                    std::cin >> choice;
                    if (choice == 'y') {
                        adj_mat[i][j] = true;
                    } else {
                        adj_mat[i][j] = false;
                    }

                    if (std::cin.fail() || (choice!='y' && choice!='n' )) {
                        std::cout << "enter a valid value please!!" << std::endl;
                        std::cin.clear();
                        std::cin.ignore(BUFFER_CLEAR_VALUE,'\n');
                    }
                } while( std::cin.fail() || (choice!='y' && choice!='n' ));
            }
        }
    }

    // member fn
    void showMatrix() {
        std::cout << std::endl << "Adjacency Matrix" << std::endl;
        for (int i = 0; i < adj_mat.size(); i ++) {
            for (int j = 0; j < adj_mat[i].size(); j++) {
                std::cout << adj_mat[i][j] << "\t";
            }
            std::cout << std::endl;
        }
    }

    // member fn
    void breadthFirstSearch(int start_point, int end_point) {
        std::queue<int> vertex_queue;
        std::set<int> visited_vertices;
        vertex_queue.push(start_point);

        while(!vertex_queue.empty()) {
            // Get next vertex
            int current_vertex = vertex_queue.front();
            vertex_queue.pop();

            // Make note of current visit
            visited_vertices.insert(current_vertex);
            std::cout << "Looking at " << current_vertex << std::endl;

            for (int j = 0; j < adj_mat[current_vertex].size(); j++) {
                if (adj_mat[current_vertex][j]) {
                    if (j == end_point) {
                        std::cout << "Found it " << j << std::endl;
                        return;
                    } else if (!(visited_vertices.find(j) != visited_vertices.end())) {
                        vertex_queue.push(j);
                    }
                }
            }
        }
        std::cout << "Could not find it!" << std::endl;
    }
};


int main() {
    Graph g;
    g.initialize();
    g.showMatrix();
    g.breadthFirstSearch(0, 1);
    g.breadthFirstSearch(0, 4);
    return 0;
}

Некоторые баллы

• Это C ++, почему бы не использовать vector и т. Д., Которые вместо этого обрабатывают такие вещи, как память? (если это не то, что вы хотите, вы не указали так)
• Они имеют ключевое значение для BFS:
  • Посмотрите на всех соседей текущего узла, начните обработку соседей соседей
  • обрабатывать узел можно только в том случае, если раньше этого не было
• То, как вы делаете это, ничто не является рядом с чем-либо. Матрица имеет только false. Вы хотели изменить это в какой-то момент?
• Ваши расчеты размера неверны, они работают только с указателями!
• У вас нет действительного критерия прекращения. Что вы ищете с BFS? Вы также должны знать, когда прекратить поиск. и сообщить, что случилось
• Что я изменил
  • Вместо этого использовались стандартные контейнеры cpp
  • Удалено использование using namespace std;
  • предоставил очень простой тестовый пример в main
  • добавлены методы для инициализации и печати матрицы

Запуск кода, которым я поделился выше, для такого графика

$ ./Adjacency                       
Enter vertex num                             
5                                            
Enter adj mat value for [y/n] 0:0            
y                                            
Enter adj mat value for [y/n] 0:1            
y                                            
Enter adj mat value for [y/n] 0:2            
n                                            
Enter adj mat value for [y/n] 0:3            
n                                            
Enter adj mat value for [y/n] 0:4            
n                                            
Enter adj mat value for [y/n] 1:0            
y                                            
Enter adj mat value for [y/n] 1:1            
y                                            
Enter adj mat value for [y/n] 1:2            
y                                            
Enter adj mat value for [y/n] 1:3            
y                                            
Enter adj mat value for [y/n] 1:4            
n                                            
Enter adj mat value for [y/n] 2:0            
n                                            
Enter adj mat value for [y/n] 2:1            
y                                            
Enter adj mat value for [y/n] 2:2
y
Enter adj mat value for [y/n] 2:3
n
Enter adj mat value for [y/n] 2:4
n
Enter adj mat value for [y/n] 3:0
n
Enter adj mat value for [y/n] 3:1
y
Enter adj mat value for [y/n] 3:2
n
Enter adj mat value for [y/n] 3:3
y
Enter adj mat value for [y/n] 3:4
n
Enter adj mat value for [y/n] 4:0
n
Enter adj mat value for [y/n] 4:1
n
Enter adj mat value for [y/n] 4:2
n
Enter adj mat value for [y/n] 4:3
n
Enter adj mat value for [y/n] 4:4
y

Adjacency Matrix
1       1       0       0       0
1       1       1       1       0
0       1       1       0       0
0       1       0       1       0
0       0       0       0       1
Looking at 0
Found it 1
Looking at 0
Looking at 1
Looking at 2
Looking at 3
Could not find it!

Предлагаемые возможные улучшения

1. Резюмируйте функциональность лучше, прямо сейчас Graph класс бога
2. Не собирать входные данные для входных данных в матрице смежности, где column = row
3. Экстраполировать значения матрицы на основе предыдущих значений, например: если 1 рядом с 2, то вы знаете, что 2 рядом с 1
4. обработка ввода становится лучше, я забыл чистый способ cin вещи

Если вы настаиваете на указателях на массивы, все, что вам нужно, это изменить конструктор и .size() вызовы.