[数据结构与算法] 深度优先搜索DFS广度优先搜索BFS 遍历矩阵

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 深度优先搜索DFS广度优先搜索BFS 遍历矩阵 -> 正文阅读

[数据结构与算法]深度优先搜索DFS广度优先搜索BFS 遍历矩阵

深度优先搜索DFS,用递归,相当于先序遍历
广度优先搜索BFS, 用队列, push进去的时候访问,标记

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

struct axis
{
    axis() : x(-1), y(-1) {}
    axis(int x_, int y_) : x(x_), y(y_) {}
    int x;
    int y;
};

void DFS(vector<vector<int>> &MAT, int i, int j);
void BFS(vector<vector<int>> &MAT, int i, int j);

int main()
{
    vector<vector<int>> MAT{{1, 2, 3, 4, 5, 0, 0},
                            {6, 7, 8, 9, 0, 0, 10},
                            {0, 0, 11, 12, 13, 14, 0},
                            {0, 15, 16, 0, 0, 17, 18},
                            {19, 20, 0, 0, 0, 24, 0}};

    DFS(MAT, 2, 3);
    BFS(MAT, 2, 3);
    return 0;
}

//深度优先,用递归,相当于先序遍历
void DFS(vector<vector<int>> &MAT, int i, int j)
{
    int row = MAT.size();
    int col = MAT[0].size();
    cout << i << " " << j << " " << MAT[i][j] << endl;
    MAT[i][j] = -1;
    if (i - 1 >= 0 && j >= 0 && i - 1 < row && j < col && MAT[i - 1][j] != -1)
        DFS(MAT, i - 1, j);
    if (i + 1 >= 0 && j >= 0 && i + 1 < row && j < col && MAT[i + 1][j] != -1)
        DFS(MAT, i + 1, j);
    if (i >= 0 && j - 1 >= 0 && i < row && j - 1 < col && MAT[i][j - 1] != -1)
        DFS(MAT, i, j - 1);
    if (i >= 0 && j + 1 >= 0 && i < row && j + 1 < col && MAT[i][j + 1] != -1)
        DFS(MAT, i, j + 1);
}

//广度优先搜索, 用队列, push进去的时候访问,标记
void BFS(vector<vector<int>> &MAT, int i, int j)
{
    int row = MAT.size();
    int col = MAT[0].size();
    queue<axis> QUEUE;
    QUEUE.push(axis(i, j));
    cout << i << " " << j << " " << MAT[i][j] << endl;
    MAT[i][j] = -1;
    axis front;
    int x, y;

    while (!QUEUE.empty())
    {
        front = QUEUE.front();
        QUEUE.pop();
        x = front.x;
        y = front.y;
        if (x - 1 >= 0 && x - i < row && MAT[x - 1][y] != -1)
        {
            QUEUE.push(axis(x - 1, y));
            cout << x - 1 << " " << y << " " << MAT[x - 1][y] << endl;
            MAT[x - 1][y] = -1;
        }
        if (x + 1 >= 0 && x + 1 < row && MAT[x + 1][y] != -1)
        {
            QUEUE.push(axis(x + 1, y));
            cout << x + 1 << " " << y << " " << MAT[x + 1][y] << endl;
            MAT[x + 1][y] = -1;
        }
        if (y - 1 >= 0 && y - 1 < col && MAT[x][y - 1] != -1)
        {
            QUEUE.push(axis(x, y - 1));
            cout << x << " " << y - 1 << " " << MAT[x][y - 1] << endl;
            MAT[x][y - 1] = -1;
        }
        if (y + 1 >= 0 && y + 1 < col && MAT[x][y + 1] != -1)
        {
            QUEUE.push(axis(x, y + 1));
            cout << x << " " << y + 1 << " " << MAT[x][y + 1] << endl;
            MAT[x][y + 1] = -1;
        }
    }
}