# [算法] 基本图算法的c++实现：广度优先搜索

xiaoxiao2021-02-28  11

# 伪代码

BFS(G, s): for each vertex u ∈ G.V - {s}: u.color = White u.d = ∞ u.π = NIL s.color = Gray s.d = 0 s.π = NIL Q = ∅ Q.push(s) while Q ≠ ∅: u = Q.pop() for each v ∈ G.Adj[u]: if v.color == White then v.color = Gray v.d = u.d + 1 v.π = u Q.push(v) u.color = Black

# C++的一般实现方式

## 第一种写法

enum vertexcolor { WHITE, GRAY, BLACK }; struct vertex { vertexcolor color; int d; int pi; };

struct graph { vector<vertex> V; map<vertex *, vector<vertex *> > Adj; };

void BFS(graph *G, vertex *s) { const int INF = 0x3f3f3f; for (vertex u : G->V) { u.color = WHITE; u.d = INF; u.pi = nullptr; } s->color = GRAY; s->d = 0; //s->pi = nullptr; 此句在上述循环中已经进行过 queue<vertex *> Q; Q.push(s); vertex *u; while (!Q.empty()) { u = Q.front(); Q.pop(); for (vertex *v : G->Adj[u]) { if (v->color == WHITE) { v->color = GRAY; v->d = u->d + 1; v->pi = u; Q.push(v); } u->color = BLACK; } } }

#include<iostream> #include<map> #include<vector> #include<queue> #define FIND(Row, Col) ((Row) * 5 + Col) #define INIT(Row, Col) (Row >= 0 && Row < 5 && Col >= 0 && Col < 5) //FIND宏用于查找处于i行j列的结点的下标 //INIT宏用于判定给定的i行j列是否在迷宫当中 using namespace std; enum vertexcolor { WHITE, GRAY, BLACK }; struct vertex { vertexcolor color; int d; vertex *pi; }; struct graph { vector<vertex> V; map<vertex *, vector<vertex *> > Adj; }; void BFS(graph &G, vertex *s) { const int INF = 0x3f3f3f; for (vertex &u : G.V) { u.color = WHITE; u.d = INF; u.pi = nullptr; } s->color = GRAY; s->d = 0; queue<vertex *> Q; Q.push(s); vertex *u; while (!Q.empty()) { u = Q.front(); Q.pop(); for (vertex *v : G.Adj[u]) { if (v->color == WHITE) { v->color = GRAY; v->d = u->d + 1; v->pi = u; Q.push(v); } } u->color = BLACK; } } int main() { graph it; it.V.resize(25); //将结点个数设为25个 for (int i = 0; i < 5; i++) { for (int j = 0; j < 5; j++) { int t; cin >> t; if (t == 0) { //若此处不是一堵墙 if (INIT(i + 1, j)) //若该结点下方有一个结点 it.Adj[&it.V[FIND(i, j)]].push_back(&it.V[FIND(i + 1, j)]); if (INIT(i, j + 1)) //若该结点右方有一个结点 it.Adj[&it.V[FIND(i, j)]].push_back(&it.V[FIND(i, j + 1)]); } } } BFS(it, &it.V[0]); cout << it.V[FIND(4, 4)].d << endl; //输出右下角到左上角的距离 return 0; }

## 第二种写法

bool graph_struct[5][5]; //true表示路径，false表示墙壁

bool graph_color[5][5]; //true表示白色，false表示非白色

int dist[5][5] { 0 }; //显然[0][0]所表示的左上角点到自身的距离为0

struct pos { int x, y; //表示该点是存储在graph_struct[x][y]的点 };

#include<iostream> #include<queue> #define INIT(Row, Col) (Row >= 0 && Row < 5 && Col >= 0 && Col < 5) using namespace std; bool graph_struct[5][5]; //true表示路径，false表示墙壁 bool graph_color[5][5]; //true表示白色，false表示非白色 int dist[5][5]; //显然[0][0]所表示的左上角点到自身的距离为0 struct pos { int x, y; }; void BFS() { const int INF = 0x3f3f3f; for (int i = 0; i < 5; i++) { for (int j = 0; j < 5; j++) { graph_color[i][j] = true; dist[i][j] = INF; } } dist[0][0] = 0; graph_color[0][0] = false; queue<pos> Q; Q.push(pos{0, 0}); //将起点放入队列 pos u, v; while (!Q.empty()) { u = Q.front(); Q.pop(); if (INIT(u.x + 1, u.y) && graph_struct[u.x + 1][u.y]) { v.x = u.x + 1; v.y = u.y; graph_color[v.x][v.y] = false; //设置颜色 dist[v.x][v.y] = dist[u.x][u.y] + 1; //设置距离 Q.push(v); } if (INIT(u.x, u.y + 1) && graph_struct[u.x][u.y + 1]) { v.x = u.x; v.y = u.y + 1; graph_color[v.x][v.y] = false; dist[v.x][v.y] = dist[u.x][u.y] + 1; Q.push(v); } /* 此处是因为只有两种情况，故选择使用两个if。 * 若有多个方向，可以考虑以下形式：(以下以此题做一个该种写法的例子）： const int opr[2][2] = { 1, 0, 0, 1 }; for (int i = 0; i < 2; i++) { v.x = u.x + opr[i][0]; v.y = u.y + opr[i][1]; if (INIT(v.x, v.y) && graph_struct[v.x][v.y]) { graph_color[v.x][v.y] = false; dist[v.x][v.y] = dist[u.x][u.y] + 1; Q.push(v); } } */ } } int main() { for (int i = 0; i < 5; i++) { for (int j = 0; j < 5; j++) { cin >> graph_struct[i][j]; graph_struct[i][j] = !graph_struct[i][j]; } } BFS(); cout << dist[4][4] << endl; return 0; }

#include<iostream> #include<queue> #define INIT(Row, Col) (Row >= 0 && Row < 5 && Col >= 0 && Col < 5) using namespace std; bool graph_struct[5][5]; //true表示路径，false表示墙壁 bool graph_color[5][5]; //true表示白色，false表示非白色 struct pos { int x, y, dist; //将dist作为pos的一个属性 }; int BFS() { //将返回值作为算法的结果 const int INF = 0x3f3f3f; for (int i = 0; i < 5; i++) { for (int j = 0; j < 5; j++) { graph_color[i][j] = true; } } graph_color[0][0] = false; queue<pos> Q; Q.push(pos{0, 0, 0}); pos u, v; while (!Q.empty()) { u = Q.front(); Q.pop(); //判断是否到达终点 if (u.x == 4 && u.y == 4) return u.dist; if (INIT(u.x + 1, u.y) && graph_struct[u.x + 1][u.y]) { v.x = u.x + 1; v.y = u.y; graph_color[v.x][v.y] = false; //设置颜色 v.dist = u.dist + 1; //###设置距离### Q.push(v); } if (INIT(u.x, u.y + 1) && graph_struct[u.x][u.y + 1]) { v.x = u.x; v.y = u.y + 1; graph_color[v.x][v.y] = false; v.dist = u.dist + 1; Q.push(v); } } } int main() { for (int i = 0; i < 5; i++) { for (int j = 0; j < 5; j++) { cin >> graph_struct[i][j]; graph_struct[i][j] = !graph_struct[i][j]; } } cout << BFS() << endl; return 0; }