c++ - 使用广度优先搜索(BFS)调试简单图算法

我正在构建一个程序，用于在简单的二维数组中搜索，识别和标记整数值图的位置。

我手工追踪了第一个示例，它看起来很准确。话虽如此，我要么写的代码不符合我的预期，要么我的手迹不准确。

我认为我的代码已经接近，并且正在寻找一些调试帮助以及对常规样式的任何想法，等等。

最终，将对该算法进行修改以找到OCR的字符像素图。我只是想证明我的算法实现是正确的，然后才将事情与处理图像的代码复杂化。

输入数组可能如下所示：

0 0 0 0 0 0
0 0 0 0 0 0
0 0 1 1 0 0
0 0 1 1 0 0
0 0 0 0 0 0
0 0 0 0 0 0

预期的结果是这样的：

3 3 3 3 3 3
3 0 0 0 0 3
3 0 2 2 0 3
3 0 2 2 0 3
3 0 0 0 0 3
3 3 3 3 3 3

另一个类似的可能性是：
在：

0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 1 1 0 0 0 0 0 0 0
0 0 0 1 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 1 1 1 1 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0

出：

0 3 3 3 3 3 3 0 0 0 0 0
0 3 0 0 0 0 3 0 0 0 0 0
0 3 0 2 2 0 3 0 0 0 0 0
0 3 0 2 2 0 3 0 0 0 0 0
0 3 0 0 0 0 3 0 0 0 0 0
0 3 3 3 3 3 3 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0
0 0 3 3 3 3 3 3 3 3 3 0
0 0 3 0 0 0 0 0 0 0 3 0
0 0 3 0 2 2 2 2 2 0 3 0
0 0 3 0 0 0 0 0 0 0 3 0
0 0 3 3 3 3 3 3 3 3 3 0

基本规则：


输入文件的数组大小必须与.cpp文件中定义的GS匹配（H等于W等于GS）。
图被定义为彼此相邻的一个或多个“ 1”值。
通过使用简单队列的基本BFS技术执行搜索。
找到图后，其值将从“ 1”更新为“ 2”。
确定图形中的最终值后，将在图形周围绘制一个“ 3”值的边界框。框的最小X等于图的最小X减2，框的最小Y等于图的最小Y减2。框的最大X等于图的最大X加上两个，框的最大Y等于图的最大Y加上两个。假设所有图形从边框起至少有两行/列的缓冲区，以允许绘制框。


处理此数组的最新尝试：

0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 1 1 0 0 0
0 0 0 1 1 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0

产生以下输出：

0 0 0 0 0 0 0 0
0 3 3 3 3 3 0 0
0 3 3 3 3 3 3 0
0 3 3 2 1 3 3 0
0 3 3 2 2 3 3 0
0 3 3 3 3 3 3 0
0 3 3 3 3 3 3 0
0 0 0 0 0 0 0 0

而一位数图形效果很好：

0 0 0 0 0
0 0 0 0 0
0 0 1 0 0
0 0 0 0 0
0 0 0 0 0

产生输出：

3 3 3 3 3
3 0 0 0 3
3 0 2 0 3
3 0 0 0 3
3 3 3 3 3

这是我的代码：

#include <iostream>
#include <fstream>
#include <cstdlib>
#include "queue.h"

#define GS 8 /* GRID SIZE */

using namespace std;

void processCmdArgs (ifstream& input, int argc, char* argv[]);
void drawBoundingBox (int arr[][GS], int xLo, int yLo, int xHi, int yHi);
void checkNeighbors (int arr[][GS], bool vis[][GS], queue Q, point* p);
void print (int arr[][GS]);

int main( int argc, char* argv[] ) {

    int xLo = 0;
    int xHi = GS - 1;
    int yLo = 0;
    int yHi = GS - 1;
    ifstream input; /* filestream to read in file to parse */
    int arr[GS][GS]; /* declare array of vals to check for graph */
    bool visited[GS][GS]; /* array of bools to track progress */
    int count = 0; /* number of graphs found */
    processCmdArgs(input, argc, argv);

    /* populate array */
    for (int i = 0; i < GS; i++) {
        for (int j = 0; j < GS; j++) {
            input >> arr[i][j];
        }
    }
    input.close();

    /*init visited */
    for (int y = yLo; y < GS; y++) {
        for (int x = xLo; x < GS; x++) {
            visited[x][y] = false;
        }
    }

    /* print array */
    cout << "The array to find a graph is:\n";
    print(arr);

    /* find graph(s) in array */
    queue Q;
    for (int j = yLo; j < GS; j++) {
        for (int k = xLo; k < GS; k++) {
            if (arr[k][j] == 1) {
                count++;
                xLo = xHi = k;
                yLo = yHi = j;
                point *p = new point(k, j);
                Q.insert(p);
                delete p;
                visited[k][j] = true;
                while (!Q.isEmpty()) {
                    *p = Q.del(); /* does this really work? */
                    int x = p->getx();
                    int y = p->gety();
                    arr[x][y] = 2;
                    if (x < xLo) xLo = x;
                    if (y < yLo) yLo = y;
                    if (x > xHi) xHi = x;
                    if (y > yHi) yHi = y;
                    checkNeighbors(arr, visited, Q, p);
                }
                drawBoundingBox(arr, xLo, yLo, xHi, yHi);
            }
            else {
                visited[k][j] = true;
            }
        }
    }
    cout << "The updated array is:\n";
    print(arr);
    cout << "The number of graphs in arr is " << count << endl;

    return 0;
}
/*** END OF MAIN ***/

/*** START OF FUNCTIONS ***/
void processCmdArgs(ifstream& input, int argc, char* argv[]) {
    /* Check command-line args first to avoid accessing nonexistent memory */
    if (argc != 2) {
        cerr << "Error: this program takes one command-line argument.\n";
        exit(1);
    }
    /* Try to open the file using the provided filename */
    input.open(argv[1]);
    /* Exit with error if it doesn't open */
    if (input.fail()) {
        cerr << "Error: could not open " << argv[1] << ".\n";
        exit(1);
    }
}

void drawBoundingBox (int arr[][GS], int xLo, int yLo, int xHi, int yHi) {
    // draw a box with (lowx-2,lowy-2) as NW and
    // (highx + 2, highy + 2) as SE boundary
    /* draw top and bottom of box */
    for (int x = xLo - 2; x <= xHi + 2; x++) {
        arr[x][yLo - 2] = 3;
        arr[x][yHi + 2] = 3;
    }
    /* draw sides of box */
    for (int y = yLo - 1; y <= yHi + 1; y++) {
        arr[xLo - 2][y] = 3;
        arr[xHi + 2][y] = 3;
    }
}

void checkNeighbors (int arr[][GS], bool vis[][GS], queue Q, point* p) {
    int pX = p->getx();
    int pY = p->gety();
    for (int y = pY - 1; y <= pY + 1; y++) {
        for (int x = pX - 1; x <= pX + 1; x++) {
            if (x == pX && y == pY) {/* easier than opposite boolean logic */ }
            else {
                if (vis[x][y] == false) vis[x][y] = true;
                if (arr[x][y] == 1) {
                    point *n = new point(x, y);
                    Q.insert(n);
                    delete n;
                }
            }
        }
    }
}

void print (int arr[][GS]) {
    /* print array */
    for (int i = 0; i < GS; i++) {
        for (int j = 0; j < GS; j++) {
            cout << arr[i][j] << " ";
        }
        cout << endl;
    }
}
/*** END OF FUNCTIONS ***/

/*** START of QUEUE CLASS ***/

const int MSIZE = 1000;

class point {
private:
    int x; int y;

public:
    point(int p, int q) {
        x = p; y = q;
    }

    int getx() {
        return x;
    }

    int gety() {
        return y;
    }
};

class queue {

private:
    point* Q[MSIZE];

    int front, rear, size;

public:
    queue() {
        // initialize an empty queue
        //front = 0; rear = 0; size = 0;
        front = rear = size = 0;
        for (int j = 0; j < MSIZE; ++j)
            Q[j] = 0;
    }

    void insert(point* x) {
        if (size != MSIZE) {
            front++; size++;
            if (front == MSIZE) front = 0;
            Q[front] = x;
        }
    }

    point del() {
        if (size != 0) {
            rear++; if (rear == MSIZE) rear = 0;
            point temp(Q[rear]->getx(), Q[rear]->gety());
            size--;
            return temp;
        }
    }
    void print() {
        for (int j = 1; j <= size; ++j) {
            int i = front - j + 1;
            cout << "x = " << Q[i]->getx() << " y = " << Q[i]->gety() << endl;
        }
        cout << "end of queue" << endl;
    }
    bool isEmpty() {
        return (size == 0);
    }
};

/*** END of QUEUE CLASS ***/

最佳答案

此代码无法编译。您已经忽略了“ queue.h”。我们可以推断出来，但是您不应该让我们这样做。
您在此源文件中有类声明。它们属于头文件（否则拥有头文件没有多大意义）。
如果要在源文件中包含类声明，那么出于天生的缘故，请将它们放在需要它们的代码之前。
在queue :: del（）中有一个简单的编译时错误。您的编译器不是很好，或者您已经关闭了警告，或者您忽略了警告，或者您也不必费心去修复简单的东西。
您使用数组而不是STL容器有什么充分的理由吗？
您是否有充分的理由在堆上声明所有这些点？
我不想得出结论，但是主循环中的逻辑看起来确实很混乱且过于复杂。
最重要的是：如果您不需要边界框，我非常怀疑该程序将运行无错误，并且这些错误将更容易找到。在为边界框编写代码之前，您是否尝试过？您应该在输入每个新行为时对其进行测试，并且切勿添加任何无效代码。 （我说我经常应该开始称它为“贝塔法则”。）


现在让我们寻找错误...


在主循环中，您从xLo和yLo进行迭代，但是在循环中修改了这些变量。
有时，您使用“ [j] [k]”建立索引，有时使用“ [k] [j]”建立索引。当我清理它时，一些不良行为就会消失。
您正在图形的每个点周围绘制一个单独的边界框。
边界框例程中有一个简单的一次性错误。


现在，它只适用于一张图。我不会尝试两个。

编辑：
我不得不吃掉我的一些话：您不使用[j][k]编制索引，我只是对您使用(k,j) <=> (x,y)感到困惑，并将其与其他地方的实际错误混为一谈。现在，我了解到您正在使用queue进行操作，但是认真地考虑一下STL。

真正严重的错误在于checkNeighbors(...)的签名。您是按值而不是引用传递Q。修复此问题，该代码可用于多个图形。

编辑：
是的，另一个错误：queue出于特殊原因（而不是上面的原因，请参见“ 6”）存储指向点的指针，而不是指向点的指针，并以某种方式使它们变得肮脏。我没有寻找确切的错误，而是更改了queue来处理点，并为复杂的图形获得了正确的结果。

关于c++ - 使用广度优先搜索(BFS)调试简单图算法，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/7785356/