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 减 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 ***/

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处理点，并为复杂的图形得到了正确的结果。