目录

一：DFS BFS

1、DFS    深度优先遍历

习题：n皇后问题

 2.BFS  广度优先遍历

习题1：走迷宫

习题2：八数码

 二、树和图的深度、广度优先遍历

1.习题1：树的重心（dfs）

2.习题二：图中点的层次

三、拓扑序列

一：DFS BFS

1、DFS    深度优先遍历

1.传入一个参数，表示选择第u个位置。

2.递归退出条件：走到最深处（然后可能要输出结果）

3.在这个位置尝试每一种可能的状态，如果不可行，则剪枝，如果可行，就选择这个状态，并标记“走过”，选择下一个位置

4.特别注意要回溯，在退出这次递归，回到上一层后“恢复现场"。为接下来的选择做准备。

选取全排列数字作为一个示范：

习题：n皇后问题

思路：

1.在排列数字中，使用了一个数组记录某个数字是否被选择过。类似的，n皇后问题要求同一行、同一列、对角线上都不能有两个皇后存在，又要求每一行必定有一个皇后，我们可以每一次在每一行上选择一个位置放皇后，然后用col、dg、udg三个数组存储某一条线上是否已经有皇后。

2.如何处理两条对角线数组：

对于某一行u。遍历正对角线数组下标有dg[u+i]，遍历反对角线有udg[n-u+i]。（自己画图可厘清）

3.处理方法和排列数字非常类似，故不赘述。

#include
using namespace std;
const int N =20;

bool col[N],dg[N],udg[N];//列、正对角线、副对角线
char g[N][N];
int n; 

void dfs(int u)
{
    if(u==n)
    {
        for(int i=0;i>n;
    for(int i=0;i 
 
 2.BFS  广度优先遍历 
留意初始化。
 
1 BFS算法：
 2 
 3 通常用队列（先进先出，FIFO）实现
 4 
 5 初始化队列Q；
 6 Q = {起点s};
 7 标记s为已访问；
 8 while（Q非空）
 9 {
10     取Q队首元素u；
11     u出队；
12     if（u==目标状态）
13     {
14         ……
15     }
16     else
17     {
18         所有与u相邻且未被访问的点进入队列；
19         标记u为已访问；
20     }
21 }
 
 主要思想是使用队列，存储有待遍历的每一层的值。
 
习题1：走迷宫 
 
 思路：
 
1.从初始结点开始，层次遍历，计算每一个点在迷宫中距离起点的步数
 
2.注意事项：每个点只需要遍历一次就好
 
3.计算距离方式，初始化起点距离为0，每个点距离为上一个点距离+1；
 
4.最后返回d[最后一个点的坐标];
 
//这里填你的代码^^
#include
#include
#include
#include
using namespace std;
const int N =110;
typedef pair PII;

int d[N][N],g[N][N];
int n,m;
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};

int bfs()
{
    queue  q;
    memset(d,-1,sizeof d);
    d[0][0]=0;
    q.push({0,0});
    while(q.size())
    {
        auto t=q.front();
        q.pop();
        for(int i=0;i<4;i++)
        {
            int x=t.first+dx[i],y=t.second+dy[i];


            if(x>=0&&y>=0&&x>n>>m;
    for(int i=0;i>g[i][j];
    }


    cout< 
习题2：八数码 
 
 难点：
 
1.如何存储每个状态
 
2.如何记录每个状态的距离。
 
 
思路
 
1.使用一个字符串来存储每个状态，用哈希表就可以存储dist值
 
2.状态转移时就转换成矩阵来进行操作。设定“12345678x”为终点，达到则退出
 
3.如此看这个问题就是个典型的bfs。运用queue 即可完成
 
4.图论难点在图的建立、抽象出边、距离、状态。要在这方面开拓思路。 
 
 
代码实现：（可以留意坐标转换的公式）
 
#include
#include
#include
#include
using namespace std;

int bfs(string start)
{
    string end="12345678x";
    queue q;
    unordered_map  d;
    q.push(start);
    d[start]=0;
    
    while(q.size())
    {
        auto t=q.front();
        q.pop();
        int distance=d[t];
        if(t==end)  return d[t];
        //状态转移
        int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

        int k=t.find('x');
        int x=k/3, y=k%3; //找到x在矩阵中的坐标
        for (int i = 0; i < 4; i ++ )
        {
            int a=x+dx[i],b=y+dy[i];
            if(a>=0&&a<3&&b>=0&&b<3)
            {
                swap(t[k],t[a*3+b]);//将x转换
                if(!d.count(t))//如果没有被搜过
                {
                    q.push(t);
                    d[t]=distance+1;
                }
                
                
                swap(t[k],t[a*3+b]);//因为要接着搜原来的t中x与其他方向交换
            }
        }
    }
    return -1;
}

int main()
{
    string start;//初始状态
    for(int i=0;i<9;i++)   
    {
        char c;
        cin>>c;
        start+=c;
    }
    
    cout< 
 二、树和图的深度、广度优先遍历 
  图和树一般用邻接表或者邻接矩阵存储，，稀疏图多用邻接表。
 
所谓邻接表，其实就是在每个节点上拉出一个链表，存储与之相连的其他节点。有向图存储则联通a->b，无向图则连两条边即可。
 
int h[N],e[N],ne[N],idx;
void add(int a,int b)
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
 
树与图的dfs，bfs和上述十分类似，只不过遍历改成遍历一个链表。
 
1.习题1：树的重心（dfs） 
 
 思路：
 
1.删除一个节点后，剩余联通块中点数最大值只可能是：该节点中子树某子树的连通点数最大值，或该节点之上的所有节点（总数减去该节点与该节点子树）.
 
 
 
 
 2.使用dfs可以返回该节点与其子树的节点个数。
 
3.使用全局变量ans，在递归dfs的过程中更新答案。
 
#include
#include
#include

using namespace std;
const int N=100010,M=2*N;
int n;
int h[N],e[M],ne[M],idx;
int ans=N;
bool st[N];

void add(int a,int b)
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}

int dfs(int u)
{
    st[u]=true;
    int size=0,sum=1;
    for(int i=h[u];i!=-1;i=ne[i])
    {
        int j=e[i];
        if(st[j])  continue;
        int s=dfs(j);
        sum+=s;
        size=max(size,s);
    }
    
    size=max(size,n-sum);//删除这个节点后,连通块节点的最大值。
    ans=min(size,ans);
    
    return sum;
}

int main()
{
    cin>>n;
    memset(h,-1,sizeof h);
    for(int i=0;i>a>>b;
        add(a,b),add(b,a);
    }
    
    dfs(1);//题目给的a b 编号从1开始，自然第一个结点就是1
    cout<
 
2.习题二：图中点的层次 
 
 思路：
 
1.有了上面使用邻接表的经验，这道题就是一道很裸的题。
 
2.直接使用bfs，建队列，初始化，更新距离。。。。return d【n】 即可
 
#include
#include
#include

using namespace std;

const int N =100010;
int h[N],e[N],ne[N],idx;
int n,m;
int d[N];
queue q;


void add(int a,int b)
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}

int bfs()
{
    memset(d,-1,sizeof d);
    d[1]=0;
    q.push(1);
    while(q.size())
    {
        int t=q.front();
        q.pop();
        for(int i=h[t];i!=-1;i=ne[i])
        {
            int j=e[i];
            if(d[j]==-1)
            {
                q.push(j);
                d[j]=d[t]+1;
            }
        }
    }
    
    return d[n];
}


int main()
{
    cin>>n>>m;
    memset(h,-1,sizeof h);
    for(int i=0;i>a>>b;
        add(a,b);
    }

    cout< 
三、拓扑序列 
 
拓扑序列不唯一:
 
 
 
思路:
 
1.找到一堆在同一层次的结点,然后bfs。
 
2.第一层次的节点必定是入度为0的结点。入度可以作为我们判断先后层次的标准。
 
3.首先把第一层次的push进队列，然后bfs，遇到一个没有被遍历到的节点就把该节点的入度减一（本质表示我们的遍历更深了一层，，浅显理解的话就是还有其他的结点在这个节点的前面），当一个节点的入度为0的时候，就代表轮到这个节点被遍历了，把这个节点push进队列。
 
 
 
 
 4.拓扑序列在哪里：使用数组模拟队列，其实按每次取出的队头元素的顺序就是拓扑排序。
 
如果用数组模拟队列的话，pop出队列的节点编号实际上还在数组里存储着，遍历一遍输出就好。
 
5.判断是否存在有拓扑序列的方式是队列里是否一共进了n个点（n个点都被遍历了
 
#include
#include
#include
#include
using namespace std;
//找到度数为0的点(必定在拓扑序列的开端),然后层序遍历。
//由a遍历到b节点时，删除a->b边,如果此时b的入度是0,把b加入队列
//如果遍历完了n个点(tt==n-1)  代表存在拓扑序列

//拓扑序列不唯一,此题有special judge
const int N =100010;
int h[N],e[N],ne[N],idx;
int d[N];//d存储每个节点的入度
int n,m;

int q[N];

void add(int a,int b)
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++,d[b]++;
}

int topsort()
{
    int hh=0,tt=-1;
    for(int i=1;i<=n;i++)  
    if(!d[i])  q[++tt]=i;
    
    while(hh<=tt)
    {
        int t=q[hh++];
        for(int i=h[t];i!=-1;i=ne[i])
        {
            int j=e[i];
            d[j]--;
            if(!d[j])  q[++tt]=j;
        }
    }
    
    return tt==n-1;
}


int main()
{
    memset(h,-1,sizeof h);
    cin>>n>>m;
    for(int i=0;i>a>>b;
        add(a,b);
    }
    if(topsort())
    {
        for(int i=0;i