【第三讲】搜索与图论（1）-阿里云开发者社区

第三讲搜索与图论

树与图的存储

树是一种特殊的图，与图的存储方式相同。

对于无向图中的边ab，存储两条有向边a->b, b->a。

因此我们可以只考虑有向图的存储。

(1) 邻接矩阵：g[a][b] 存储边a->b

(2) 邻接表：

// 对于每个点k，开一个单链表，存储k所有可以走到的点。h[k]存储这个单链表的头结点

int h[N], e[N], ne[N], idx;
// 添加一条边a->b
void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
// 初始化
idx = 0;
memset(h, -1, sizeof h);

3.1DFS

树与图的遍历

时间复杂度 O(n+m)O(n+m), nn 表示点数，mm 表示边数

(1) 深度优先遍历 —— 模板题 AcWing 846. 树的重心

int dfs(int u)
{
    st[u] = true; // st[u] 表示点u已经被遍历过
    for (int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (!st[j]) dfs(j);
    }
}

(2) 宽度优先遍历 —— 模板题 AcWing 847. 图中点的层次

queue<int> q;
st[1] = true; // 表示1号点已经被遍历过
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 (!st[j])
        {
            st[j] = true; // 表示点j已经被遍历过
            q.push(j);
        }
    }
}

3.1.1 842. 排列数字

给定一个整数 n，将数字 1∼n 排成一排，将会有很多种排列方法。

现在，请你按照字典序将所有的排列方法输出。

输入格式

共一行，包含一个整数 n。

输出格式

按字典序输出所有排列方案，每个方案占一行。

数据范围

1≤n≤7

输入样例：

输出样例：

1 2 3

1 3 2

2 1 3

2 3 1

3 1 2

3 2 1

#include<bits/stdc++.h>
using namespace std;
const int N=100;
int n;
int a[N],st[N];
void dfs(int idx)
{
    if(idx>n)
    {
        for(int i=1;i<=n;i++)
        {
            cout<<a[i]<<" ";
        }
        cout<<endl;
        return;
    }
    for(int i=1;i<=n;i++)
    {
        if(st[i]==false)
        {
            a[idx]=i;
            st[i]=true;
            dfs(idx+1);
            st[i]=false;
        }
    }
}
int main()
{
    cin>>n;
    dfs(1);
    return 0;
}

3.1.1 843. n-皇后问题

n− 皇后问题是指将 n 个皇后放在 n×n 的国际象棋棋盘上，使得皇后不能相互攻击到，即任意两个皇后都不能处于同一行、同一列或同一斜线上。

现在给定整数 n，请你输出所有的满足条件的棋子摆法。

输入格式

共一行，包含整数 n。

输出格式

每个解决方案占 n 行，每行输出一个长度为 n 的字符串，用来表示完整的棋盘状态。

其中 . 表示某一个位置的方格状态为空，Q 表示某一个位置的方格上摆着皇后。

每个方案输出完成后，输出一个空行。

注意：行末不能有多余空格。

输出方案的顺序任意，只要不重复且没有遗漏即可。

数据范围

1≤n≤9

输入样例：

输出样例：

.Q…

…Q

Q…

…Q.

Q…

…Q

.Q…

#include<bits/stdc++.h>
using namespace std;
const int N=15;
int n;
char g[N][N];
bool dg[2*N],udg[2*N];
bool judge(int x,int y)
{
    for(int i=1;i<=n;i++)
    {
        if(g[x][i]=='Q'||g[i][y]=='Q') return false;
    }
    if(dg[x+y]||udg[n-x+y]) return false;
    return true;
}
void dfs(int u)
{
    if(u>n)
    {
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                cout<<g[i][j];
                if(j==n) cout<<endl;
            }
        }
        cout<<endl;
        return;
    }
    for(int i=1;i<=n;i++)
    {
        if(judge(u,i))
        {
            g[u][i]='Q';
            dg[u+i]=udg[n-u+i]=true;
            dfs(u+1);
            g[u][i]='.';
            dg[u+i]=udg[n-u+i]=false;
        }
    }
}
int main()
{
    cin>>n;
    fill(g[0],g[0]+N*N,'.');
    dfs(1);
    return 0;
}

3.2BFS

(2) 宽度优先遍历 —— 模板题 AcWing 847. 图中点的层次

queue<int> q;
st[1] = true; // 表示1号点已经被遍历过
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 (!st[j])
        {
            st[j] = true; // 表示点j已经被遍历过
            q.push(j);
        }
    }
}

3.2.1 844. 走迷宫

给定一个 n×m 的二维整数数组，用来表示一个迷宫，数组中只包含 0 或 1，其中 0 表示可以走的路，1 表示不可通过的墙壁。

最初，有一个人位于左上角 (1,1) 处，已知该人每次可以向上、下、左、右任意一个方向移动一个位置。

请问，该人从左上角移动至右下角 (n,m) 处，至少需要移动多少次。

数据保证 (1,1) 处和 (n,m) 处的数字为 0，且一定至少存在一条通路。

输入格式

第一行包含两个整数 n 和 m。

接下来 n 行，每行包含 m 个整数（0 或 1），表示完整的二维数组迷宫。

输出格式

输出一个整数，表示从左上角移动至右下角的最少移动次数。

数据范围

1≤n,m≤100

输入样例：

5 5

0 1 0 0 0

0 1 0 1 0

0 0 0 0 0

0 1 1 1 0

0 0 0 1 0

输出样例：

#include<bits/stdc++.h>
using namespace std;
const int N=110;
struct Node{
    int x,y,layer;
}node;
int n,m;
int g[N][N];
bool inq[N][N];
int X[4]={0,0,1,-1},Y[4]={1,-1,0,0};
int edx,edy;
bool judge(int x,int y)
{
    if(x<1||x>n||y<1||y>m) return false;
    if(inq[x][y]) return false;
    return true;
}
int bfs(int x,int y)
{
    node.x=x,node.y=y,node.layer=0;
    queue<Node> q;
    q.push(node);
    inq[x][y]=true;
    while(!q.empty())
    {
        Node top=q.front();
        q.pop();
        for(int i=0;i<4;i++)
        {
            node.x=top.x+X[i],node.y=top.y+Y[i],node.layer=top.layer+1;
            if(judge(node.x,node.y)&&!g[node.x][node.y])
            {
                q.push(node);
                inq[node.x][node.y]=true;
                if(node.x==edx&&node.y==edy) return node.layer;
            }
        }
    }
}
int main()
{
    cin>>n>>m;
    edx=n,edy=m;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cin>>g[i][j];
        }
    }
    cout<<bfs(1,1);
    return 0;
}

3.2.2 845. 八数码

在一个 3×3 的网格中，1∼8 这 8 个数字和一个 x 恰好不重不漏地分布在这 3×3 的网格中。

例如：

1 2 3

x 4 6

7 5 8

在游戏过程中，可以把 x 与其上、下、左、右四个方向之一的数字交换（如果存在）。

我们的目的是通过交换，使得网格变为如下排列（称为正确排列）：

1 2 3

4 5 6

7 8 x

例如，示例中图形就可以通过让 x 先后与右、下、右三个方向的数字交换成功得到正确排列。

交换过程如下：

1 2 3 1 2 3 1 2 3 1 2 3

x 4 6 4 x 6 4 5 6 4 5 6

7 5 8 7 5 8 7 x 8 7 8 x

现在，给你一个初始网格，请你求出得到正确排列至少需要进行多少次交换。

输入格式

输入占一行，将 3×3 的初始网格描绘出来。

例如，如果初始网格如下所示：

1 2 3

x 4 6

7 5 8

则输入为：1 2 3 x 4 6 7 5 8

输出格式

输出占一行，包含一个整数，表示最少交换次数。

如果不存在解决方案，则输出 −1。

输入样例：

2 3 4 1 5 x 7 6 8

输出样例

#include<bits/stdc++.h>
using namespace std;
int stx,sty;
int X[4]={0,0,-1,1},Y[4]={1,-1,0,0};
int bfs(string start)
{
    string ed="12345678x";
    queue<string> q;
    unordered_map<string,int> d;
    d[start]=0;
    q.push(start);
    while(!q.empty())
    {
        string top=q.front();
        int dis=d[top];
        if(top==ed) return dis;
        q.pop();
        int k=top.find("x");
        int x=k/3,y=k%3;
        for(int i=0;i<4;i++)
        {
            int newX=x+X[i],newY=y+Y[i];
            if(newX>=0&&newX<3&&newY>=0&&newY<3)
            {
                swap(top[k],top[newX*3+newY]);
                if(d.count(top)==0)
                {
                    d[top]=dis+1;
                    q.push(top);
                }
                swap(top[k],top[newX*3+newY]);
            }
        }
    }
    return -1;
}
int main()
{
    string start="";
    for(int i=0;i<9;i++)
    {
        char c;
        cin>>c;
        start+=c;
    }
    cout<<bfs(start);
    return 0;
}

3.3树与图的深度优先遍历

3.3.1 846. 树的重心

给定一颗树，树中包含 n 个结点（编号 1∼n）和 n−1 条无向边。

请你找到树的重心，并输出将重心删除后，剩余各个连通块中点数的最大值。

重心定义：重心是指树中的一个结点，如果将这个点删除后，剩余各个连通块中点数的最大值最小，那么这个节点被称为树的重心。

输入格式

第一行包含整数 n，表示树的结点数。

接下来 n−1 行，每行包含两个整数 a 和 b，表示点 a 和点 b 之间存在一条边。

输出格式

输出一个整数 m，表示将重心删除后，剩余各个连通块中点数的最大值。

数据范围

1≤n≤105

输入样例

1 2

1 7

1 4

2 8

2 5

4 3

3 9

4 6

输出样例：

#include<bits/stdc++.h>
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_to_head(int a,int b)
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
int dfs(int u)
{
    st[u]=true;
    int sz=0,sum=0;
    for(int i=h[u];i!=-1;i=ne[i])
    {
        int j=e[i];
        if(st[j]) continue;
        int s=dfs(j);
        sz=max(sz,s);
        sum+=s;
    }
    sz=max(sz,n-sum-1);
    ans=min(ans,sz);
    return sum+1;
}
int main()
{
    cin>>n;
    fill(h,h+N,-1);
    for(int i=0;i<n-1;i++)
    {
        int a,b;
        cin>>a>>b;
        add_to_head(a,b);
        add_to_head(b,a);
    }
    dfs(1);
    cout<<ans;
    return 0;
}

3.4树与图的广度优先遍历

3.4.1 847. 图中点的层次

给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环。

所有边的长度都是 1，点的编号为 1∼n。

请你求出 1 号点到 n 号点的最短距离，如果从 1 号点无法走到 n 号点，输出 −1。

输入格式

第一行包含两个整数 n 和 m。

接下来 m 行，每行包含两个整数 a 和 b，表示存在一条从 a 走到 b 的长度为 1 的边。

输出格式

输出一个整数，表示 1 号点到 n 号点的最短距离。

数据范围

1≤n,m≤105

输入样例：

4 5

1 2

2 3

3 4

1 3

1 4

输出样例：

#include<bits/stdc++.h>
using namespace std;
const int N=100010;
int n,m;
int d[N];
int h[N],e[N],ne[N],idx;
void add(int a,int b)
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
int bfs()
{
    queue<int> q;
    q.push(1);
    d[1]=0;
    while(!q.empty())
    {
        int t=q.front();
        q.pop();
        for(int i=h[t];i!=-1;i=ne[i])
        {
            int j=e[i];
            if(d[j]==-1)
            {
                d[j]=d[t]+1;
                q.push(j);
            }
        }
    }
    return d[n];
}
int main()
{
    cin>>n>>m;
    fill(h,h+N,-1);
    fill(d,d+N,-1);
    for(int i=0;i<m;i++)
    {
        int a,b;
        cin>>a>>b;
        add(a,b);
    }
    cout<<bfs();
    return 0;
}

3.5拓扑排序

拓扑排序 —— 模板题 AcWing 848. 有向图的拓扑序列

时间复杂度 O(n+m)O(n+m), nn 表示点数，mm 表示边数

bool topsort()
{
    int hh = 0, tt = -1;
    // d[i] 存储点i的入度
    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];
            if (-- d[j] == 0)
                q[ ++ tt] = j;
        }
    }
    // 如果所有点都入队了，说明存在拓扑序列；否则不存在拓扑序列。
    return tt == n - 1;
}

3.5.1 848. 有向图的拓扑序列

给定一个 n 个点 m 条边的有向图，点的编号是 1 到 n，图中可能存在重边和自环。

请输出任意一个该有向图的拓扑序列，如果拓扑序列不存在，则输出 −1。

若一个由图中所有点构成的序列 A 满足：对于图中的每条边 (x,y)，x 在 A 中都出现在 y 之前，则称 A 是该图的一个拓扑序列。

输入格式

第一行包含两个整数 n 和 m。

接下来 m 行，每行包含两个整数 x 和 y，表示存在一条从点 x 到点 y 的有向边 (x,y)。

输出格式

共一行，如果存在拓扑序列，则输出任意一个合法的拓扑序列即可。

否则输出 −1。

数据范围

1≤n,m≤105

输入样例：

3 3

1 2

2 3

1 3

输出样例：

1 2 3

#include<bits/stdc++.h>
using namespace std;
const int N=100010;
int n,m;
int h[N],e[N],ne[N],idx;
int d[N];
vector<int> vc;
void add(int a,int b)
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
bool topsort()
{
    queue<int> q;
    for(int i=1;i<=n;i++)
    {
        if(d[i]==0) q.push(i);
    }
    while(!q.empty())
    {
        int t=q.front();
        vc.push_back(t);
        q.pop();
        for(int i=h[t];i!=-1;i=ne[i])
        {
            int j=e[i];
            d[j]--;
            if(d[j]==0) q.push(j);
        }
    }
    if(vc.size()==n) return true;
    return false;
}
int main()
{
    cin>>n>>m;
    fill(h,h+N,-1);
    for(int i=0;i<m;i++)
    {
        int a,b;
        cin>>a>>b;
        add(a,b);
        d[b]++;
    }
    if(topsort())
    {
        for(int i=0;i<vc.size();i++) cout<<vc[i]<<" ";
    }
    else cout<<-1;
    return 0;
}

3.6Dijkstra

朴素dijkstra算法 —— 模板题 AcWing 849. Dijkstra求最短路 I

时间复杂是 O(n2+m)O(n2+m), nn 表示点数，mm 表示边数

int g[N][N];  // 存储每条边
int dist[N];  // 存储1号点到每个点的最短距离
bool st[N];   // 存储每个点的最短路是否已经确定
// 求1号点到n号点的最短路，如果不存在则返回-1
int dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    for (int i = 0; i < n - 1; i ++ )
    {
        int t = -1;     // 在还未确定最短路的点中，寻找距离最小的点
        for (int j = 1; j <= n; j ++ )
            if (!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;
        // 用t更新其他点的距离
        for (int j = 1; j <= n; j ++ )
            dist[j] = min(dist[j], dist[t] + g[t][j]);
        st[t] = true;
    }
    if (dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];
}

堆优化版dijkstra —— 模板题 AcWing 850. Dijkstra求最短路 II

时间复杂度 O(mlogn)O(mlogn), nn 表示点数，mm 表示边数

typedef pair<int, int> PII;

int n;      // 点的数量
int h[N], w[N], e[N], ne[N], idx;       // 邻接表存储所有边
int dist[N];        // 存储所有点到1号点的距离
bool st[N];     // 存储每个点的最短距离是否已确定
// 求1号点到n号点的最短距离，如果不存在，则返回-1
int dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    priority_queue<PII, vector<PII>, greater<PII>> heap;
    heap.push({0, 1});      // first存储距离，second存储节点编号
    while (heap.size())
    {
        auto t = heap.top();
        heap.pop();
        int ver = t.second, distance = t.first;
        if (st[ver]) continue;
        st[ver] = true;
        for (int i = h[ver]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > distance + w[i])
            {
                dist[j] = distance + w[i];
                heap.push({dist[j], j});
            }
        }
    }
    if (dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];
}

3.6.1 849. Dijkstra求最短路 I

给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环，所有边权均为正值。

请你求出 1 号点到 n 号点的最短距离，如果无法从 1 号点走到 n 号点，则输出 −1。

输入格式

第一行包含整数 n 和 m。

接下来 m 行每行包含三个整数 x,y,z，表示存在一条从点 x 到点 y 的有向边，边长为 z。

输出格式

输出一个整数，表示 1 号点到 n 号点的最短距离。

如果路径不存在，则输出 −1。

数据范围

1≤n≤500,

1≤m≤105,

图中涉及边长均不超过10000。

输入样例：

3 3

1 2 2

2 3 1

1 3 4

输出样例：

#include<bits/stdc++.h>
using namespace std;
const int N=510,INF=0x3f3f3f3f;
int n,m;
int g[N][N];
int dist[N];
bool st[N];
int dijkstra(int s)
{
    fill(dist,dist+N,INF);
    dist[s]=0;
    for(int i=1;i<=n;i++)
    {
        int t=-1;
        for(int j=1;j<=n;j++)
        {
            if(!st[j]&&(t==-1||dist[t]>dist[j]))
                t=j;
        }
        st[t]=true;
        for(int j=1;j<=n;j++)
        {
                dist[j]=min(dist[j],dist[t]+g[t][j]);
        }
    }
    if(dist[n]==INF) return -1;
    return dist[n];
}
int main()
{
    cin>>n>>m;
    fill(g[0],g[0]+N*N,INF);
    for(int i=0;i<m;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        g[a][b]=min(g[a][b],c);
    }
    cout<<dijkstra(1);
    return 0;
}

3.6.2 850. Dijkstra求最短路 II

给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环，所有边权均为非负值。

请你求出 1 号点到 n 号点的最短距离，如果无法从 1 号点走到 n 号点，则输出 −1。

输入格式

第一行包含整数 n 和 m。

接下来 m 行每行包含三个整数 x,y,z，表示存在一条从点 x 到点 y 的有向边，边长为 z。

输出格式

输出一个整数，表示 1 号点到 n 号点的最短距离。

如果路径不存在，则输出 −1。

数据范围

1≤n,m≤1.5×105,

图中涉及边长均不小于 0，且不超过 10000。

输入样例：

3 3

1 2 2

2 3 1

1 3 4

输出样例：

#include<bits/stdc++.h>
using namespace std;
const int N=150010,INF=0x3f3f3f3f;
typedef pair<int,int> PII;
int n,m;
int h[N],e[N],w[N],ne[N],idx;
bool st[N];
int dis[N];
void add(int a,int b,int c)
{
    e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}
int dijkstra(int s)
{
    fill(dis,dis+N,INF);
    dis[s]=0;
    priority_queue<PII,vector<PII>,greater<PII> > heap;
    heap.push(make_pair(0,s));
    while(heap.size())
    {
        PII t=heap.top();
        heap.pop();
        int ver=t.second,distance=t.first;
        if(st[ver]) continue;
        st[ver]=true;
        for(int i=h[ver];i!=-1;i=ne[i])
        {
            int j=e[i];
            if(dis[j]>dis[ver]+w[i])
            {
                dis[j]=dis[ver]+w[i];
                heap.push(make_pair(dis[j],j));
            }
        }
    }
    if(dis[n]==INF) return -1;
    return dis[n];
}
int main()
{
    cin>>n>>m;
    fill(h,h+N,-1);
    for(int i=0;i<m;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c);
    }
    cout<<dijkstra(1);
    return 0;
}

【第三讲】搜索与图论（1）