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

Question

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

我亲手描绘了第一个例子，结果似乎很准确。话虽如此，我要么编写的代码不符合我的想法，要么我的手部追踪不准确。

我认为我的代码很接近，我正在寻找一些调试帮助以及对一般风格等的任何想法。

最终将修改此算法以查找用于 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

基本规则:

1. 输入文件的数组大小必须与 .cpp 文件中定义的 GS 匹配(H 等于 W 等于 GS)。
2. 图形被定义为一个或多个彼此相邻的“1”值。
3. 搜索是通过使用简单队列的基本 BFS 技术执行的。
4. 找到图形后，其值将从“1”更新为“2”。
5. 确定图表中的最终值后，将在图表周围绘制一个包含“3”个值的边界框。盒子的最小X等于图形的最小X减二，盒子的最小Y等于图形的最小Y减二。框的最大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 ***/

Answer 1

1. 此代码无法编译。你遗漏了 `queue.h`。我们可以推断，但你不应该让我们那样做。
2. 您在此源文件中有类声明；它们属于头文件(否则拥有头文件没有多大意义)。
3. 如果您要在源文件中包含类声明，看在上帝的份上，请将它们放在需要它们的代码之前。
4. `queue::del()` 中存在一个简单的编译时错误。您的编译器不是很好，或者您关闭了警告，或者您忽略了警告，或者您懒得修复简单的东西。
5. 您使用数组而不是 STL 容器有什么充分的理由吗？
6. 在堆上声明所有这些点是否有充分的理由？
7. 我不想仓促下结论，但您的主循环中的逻辑看起来确实很困惑且过于复杂。
8. 最重要的是:如果您不使用边界框，我非常怀疑该程序是否可以无错误运行，并且更容易找到错误。您在为边界框编写代码之前尝试过吗？您应该在添加每个新行为时对其进行测试，并且永远不要添加不起作用的代码。(我经常说我应该开始称它为“Beta 规则”。)

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

1. 在主循环中，您从 `xLo` 和 `yLo` 进行迭代，但您在循环中修改了这些变量。
2. 有时您使用 `[j][k]` 进行索引，有时使用 `[k][j]`。当我清理它时，一些不良行为就会消失。
3. 您正在围绕图表的每个点 绘制一个单独的边界框。
4. 您的边界框例程中存在一个简单的差一错误。

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

编辑:
我不得不收回我的话:你没有使用 [j][k] 建立索引。 , 我只是对你对 (k,j) <=> (x,y) 的使用感到困惑并将它与其他地方的实际错误混淆。现在我看到你用 queue 做了什么，但说真的，你应该研究一下 STL。

真正严重的错误在 checkNeighbors(...) 的签名中. 你超过了Q按值，而不是按引用。解决这个问题，代码适用于多个图形。

编辑:
是的，另一个错误:queue存储指向点的指针，而不是点，没有特别的原因(见上面的“6”)，不知何故它弄脏了它们。我没有寻找确切的错误，而是更改了 queue处理点，并得到复杂图形的正确结果。