BFS学习笔记

八数码问题

在3×3的棋盘上，摆有八个棋子，每个棋子上标有1至8的某一数字。棋盘中留有一个空格，空格用0来表示。空格周围的棋子可以移到空格中。要求解的问题是：给出一种初始布局（初始状态）和目标布局（为了使题目简单,设目标状态为123804765），找到一种最少步骤的移动方法，实现从初始布局到目标布局的转变。

BFS

#include<iostream>
#include<queue>
#include<map>
using namespace std;
int ma[4][4];
queue<int>q;
int x_div[] = { 0,0,-1,1 };
int y_div[] = { -1,1,0,0, };
map<int, int>step;
int aim = 123804765;
int temp_x, temp_y, next_x, next_y;
void BFS()
{
 int next = 0;
 while (q.size() != 0)
 {
  int temp = q.front();
  q.pop();
  int temp_ = temp;
  for (int i = 3; i >= 1; i--)
  {
   for (int j = 3; j >= 1; j--)
   {
    ma[i][j] = temp % 10;
    temp = temp / 10;
    if (ma[i][j] == 0)
    {
     temp_x = i;
     temp_y = j;
    }
   }
  }
  for (int i = 0; i <= 3; i++)
  {
   if (temp_x + x_div[i] >= 1 && temp_x + x_div[i] <= 3 && temp_y + y_div[i] >= 1 && temp_y + y_div[i] <= 3)
   {
    next_x = temp_x + x_div[i];
    next_y = temp_y + y_div[i];
    ma[temp_x][temp_y] = ma[temp_x + x_div[i]][temp_y + y_div[i]];
    ma[temp_x + x_div[i]][temp_y + y_div[i]] = 0;
    next = 0;
    //在每次计算next时一定要赋初值为0，我又木有赋初值，崩溃了
    for (int i = 1; i <= 3; i++)
    {
     for (int j = 1; j <= 3; j++)
     {
      next = next * 10 + ma[i][j];
     }
    }
    ma[temp_x + x_div[i]][temp_y + y_div[i]] = ma[temp_x][temp_y];
    //这两行是对查找后修改的状态进行恢复，使得程序仍然以当前状态查找其他可行的解，忘记恢复的后果（不是忘记恢复，而是把它放在了continue后面，相当于没有）我已经体验到了，有点像DFS里的回溯
    ma[temp_x][temp_y] = 0;
    if (step[next] == 0)
    //如果map中key对应得value不为0，证明已经查找过这个状态，不用再查找，直接continue
    {
     step[next] = step[temp_] + 1;
     //第一个问题，我忘记前面为了把这个二维数组弄出来（见42行）已经把temp除成了0，然后这里就一直是查找map中key为0的value
    }
    else
    {
     continue;
    }
    q.push(next);
    if (next == aim)
    {
     return;
    }
   }
  }
 }
 return;
}
int main()
{
 int start;
 cin >> start;
 q.push(start);
 step[start] = 0;
 if (start == aim)
 //题目有个点是开局直接结束（别问我是怎么知道的），注意考虑这一种情况
 {
  cout << 0 << endl;
  return 0;
 }
 BFS();
 cout << step[123804765] << endl;
 return 0;
}

DFS实现路径标记

原理是在搜索过程中记录路径，设置一个标记，一旦达到终点，标记值置为1，在DFS中逐层判断标记值，
让程序控制权能尽快返回到主程序中。

#include<iostream>
#include<vector>
using namespace std;
int fx[4] = { 0,1,0,-1 };
int fy[4] = { 1,0,-1,0 };
int land[105][105];
int height, wide, start_x, start_y, end_x, end_y;
bool visit[105][105];
int flag = 0;
struct position
{
 int x;
 int y;
 int next = 0;
};
vector<position>v;
bool judge_size(int x, int y)
{
 if (x < 0 || y < 0)
  return false;
 else if (x > height || y > wide)
  return false;
 else if (visit[x][y] == 1)
  return false;
 else if (land[x][y] == 1)
  return false;
 else
  return true;
}
int DFS(int x, int y)
{
 int temp_x, temp_y, i, step;
 visit[x][y] = 1;
 if (!v.empty())
 {
  int last_x = v.back().x;
  int last_y = v.back().y;
  if (y - last_y == 1)
   step = 1;
  else if (x - last_x == 1)
   step = 2;
  else if (y - last_y == -1)
   step = 3;
  else if (x - last_x == -1)
   step = 4;
  v.back().next = step;
 }
 position a;
 a.x = x;
 a.y = y;
 v.push_back(a);
 if (x == end_x && y == end_y)
 {
  flag = 1;
  return 1;
 }
 for (i = 0; i < 4; i++)
 {
  temp_x = x + fx[i];
  temp_y = y + fy[i];
  //if (judge_size(temp_x, temp_y))
  if (temp_x < 0 || temp_y < 0 || temp_x > height || temp_y > wide || visit[temp_x][temp_y] == 1 || land[temp_x][temp_y] == 1)
   continue;
  else
  {
   DFS(temp_x, temp_y);
   if (flag == 1)
    return 1;
  }
 }
    visit[x][y] = 0;
 v.pop_back();
 if (x == start_x && y == start_y && i >= 4)
  return 0;
}
int main()
{
 //cin >> height >> wide;
 //cin >> start_x >> start_y;
 //cin >> end_x >> end_y;
 //scanf_s("%d %d", &height, &wide);
 scanf("%d %d", &height, &wide);
 //scanf_s("%d %d", &start_x, &start_y);
 scanf("%d %d", &start_x, &start_y);
 //scanf_s("%d %d", &end_x, &end_y);
 scanf("%d %d", &end_x, &end_y);
 for (int i = 0; i <= wide + 1; i++)
 {
  land[0][i] = 1;
  land[height + 1][i] = 1;
 }
 for (int i = 0; i <= height + 1; i++)
 {
  land[i][0] = 1;
  land[i][wide + 1] = 1;
 }
 for (int i = 1; i <= height; i++)
 {
  for (int j = 1; j <= wide; j++)
  {
   //cin >> land[i][j];
   //scanf_s("%d", &land[i][j]);
   scanf("%d", &land[i][j]);
  }
 }
 if (!DFS(start_x, start_y))
 {
  //cout << "no" << endl;
  printf("no\n");
  return 0;
 }
 /*int step = 0;
 for (int i = 1; i <= height; i++)
 {
  for (int j = 1; j <= wide; j++)
  {
   cout << visit[i][j];
   if (visit[i][j] == 1)
   {
    if (visit[i][j + 1] == 1)
     step = 1;
    else if (visit[i + 1][j] == 1)
     step = 2;
    else if (visit[i][j - 1] == 1)
     step = 3;
    else if (visit[i - 1][j] == 1)
     step = 4;
   }
  }
  cout << endl;
 }*/
 if (!v.empty())
 {
  v.back().next = 1;
 }
 //cout << '(' << v[0].x << ',' << v[0].y << ',' << v[0].next << ')';
 printf("(%d,%d,%d)", v[0].x, v[0].y, v[0].next);
 for (int i = 1; i < v.size(); i++)
 {
  //cout << ",(" << v[i].x << ',' << v[i].y << ',' << v[i].next << ')';
  printf(",(%d,%d,%d)", v[i].x, v[i].y, v[i].next);
 }
 return 0;
}

图的BFS遍历求连通子图的个数

#include<iostream>
#include<queue>
#include<algorithm>
using namespace std;
int map[105][105];
int value;
int number_node;
int visit[105];
int cnt = 0;
void BFS(int start)
{
 cnt++;
 queue<int>Q;
 int i,j;
 cout << start << " ";
 visit[start] = start;
 Q.push(start);
 while (!Q.empty())
 {
  i = Q.front();
  Q.pop();
  for (j = 1; j <= number_node; j++)
  {
   if (map[i][j] == 1 && (!visit[j]))
   {
    cout << j << " ";
    visit[j] = start;
    Q.push(j);
   }
  }
 }
}
int main()
{
 ios::sync_with_stdio(false);
 cin >> number_node;
 for (int i = 1; i <= number_node; i++)
 {
  for (int j = 1; j <= number_node; j++)
  {
   cin >> map[i][j];
  }
 }
 for (int i = 1; i <= number_node; i++)
 {
  if (!visit[i])
   BFS(i);
 }
 cout << '\n';
 cout << cnt<< '\n';
 return 0;
}

图的DFS遍历并求图的连通子图的个数

#include<iostream>
using namespace std;
int map[105][105];
int number_node;
int visit[105];
int cnt;
void DFS(int n)//这个DFS不需要递归终点，当循环结束后就会自动return了。
{
 visit[n] = 1;
 cout << n << " ";
 int i;
 for (i = 1; i <= number_node; i++)
 {
  if ((!visit[i]) && map[n][i] == 1)
  {
   DFS(i);
  }
 }
}
int main()
{
 cin >> number_node;
 for (int i = 1; i <= number_node; i++)
 {
  for (int j = 1; j <= number_node; j++)
  {
   cin >> map[i][j];
  }
 }
 for (int i = 1; i <= number_node; i++)
 {
  if (!visit[i])
  {
   DFS(i);
   cnt++;
  }
 }
 cout << "\n";
 cout << cnt << "\n";
 return 0;
}

关键路径

//拓扑序，最早开始时间
//逆拓扑序，最迟开始时间
//二者相等即为关键节点
//关键节点连接的路径即为关键路径

#include<cstdio>
#include<algorithm>
using namespace std;

const int INF = 1 << 31;

int n;
bool hav_cy = 0;
int G[110][110];//图的邻接表
int es[110];//每个节点的最早开始时间数组
int ls[110];//每个节点的最晚开始时间数组
bool used[110];//DFS的标记数组

void init() {
    fill(es, es + n, 0);
    fill(ls, ls + n, INF);
    fill(used, used + n, 0);
}

void find_es(int now) {
    if (now == n) return;
    //如果这个节点已经是图的最后一个节点，则结束DFS
    for (int i = 0; i < n; ++i) {//循环节点位置，寻找更新es的目标
        if (G[now][i]) {//如果now和i节点连通
            if (used[i]) {//如果在循环过程中找到了已经搜索过的节点，则这个图中存在环，DFS结束
                hav_cy = 1;
                return;
            }
            else {
                es[i] = max(es[i], es[now] + G[now][i]);
                //更新i项目的最晚开始时间，为所有在它之前的项目完成时间取最大值
                used[i] = true;//将i项目标记为已访问
                find_es(i);//i项目为DFS的下一个目标，进一步更新路径
                used[i] = false;//回溯，在
            }
        }
    }
}

void find_ls(int now) {
    if (now == -1) return;
    for (int i = 0; i < n; ++i) {
        if (G[i][now]) {
            ls[i] = min(ls[i], ls[now] - G[i][now]);
            find_ls(i);
        }
    }
}

int main() {
    scanf("%d", &n);
    init();
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            scanf("%d", &G[i][j]);
        }
    }
    find_es(0);
    if (hav_cy) {
        printf("NO\n");
        return 0;
    }
    else {
        fill(ls, ls + n, es[n - 1]);
        find_ls(n - 1);
        for (int i = 0; i < n; ++i) {
            if (es[i] == ls[i]) {
                //printf("%d ", i);
            }
        }
        //printf("\n");
    }
    printf("%d\n", es[n - 1]);
    return 0;
}

查找有向图中是否有环

#include<iostream>
#include<vector>
#include<iterator>
using namespace std;
int map[105][105];
int visit[105];
int number_node;
int groups;
int hascircle = 0;
vector<int>V;
vector<int>::iterator it;
void initial()
{
 for (int i = 1; i <= number_node; i++)
 {
  visit[i] = 0;
  for (int j = 1; j <= number_node; j++)
  {
   cin >> map[i][j];
  }
 }
}
void DFS(int n)
{//这里递归终点不可以是n == number_node,因为这样子将会查找不出环就直接DFS结束了。
 for (int i = 1; i <= number_node; i++)
 {
  if (map[n][i] == 1)
  {
   if (visit[i])
   {
    hascircle = 1;
    return;
   }
   else
   {
    visit[i] = 1;
    DFS(i);
    visit[i] = 0;//一定要有回溯，否则会出错。
   }
  }
 }
}
int main()
{
 ios::sync_with_stdio(false);
 cin >> groups;
 for (int i = 1; i <= groups; i++)
 {
  hascircle = 0;
  cin >> number_node;
  initial();
  int cnt = 1;
  for (int i = 1; i <= number_node; i++)
  {
   if (!visit[i])
   {
    DFS(i);
   }
  }
  V.push_back(hascircle);
 }
 for (it = V.begin(); it != V.end(); it++)
 {
  cout << *it;
 }
 cout << "\n";
 return 0;
}