template:图论

树的dfs

dfs俗称爆搜，用于搜索所有情况
dfs需要维护的数据结构：表征当前遍历位置的u，表征某个状态是否被遍历过的st[N],（可能）当前遍历路径下的方案。
输出n个数的全排列

#include<iostream>
using namespace std;
const int N = 40;
int path[N],n;
bool st[N];
void dfs(int u)
{
    //设置递归出口
    if(u==n+1) 
    {
        for(int i=1;i<=n;i++) cout<<path[i]<<' ';
        cout<<endl;
        return;
    }
    for(int i=1;i<=n;i++)
    {
        if(!st[i])
        {
            st[i]=true;
            path[u]=i;
            dfs(u+1);
            //状态复原是关键
            st[i]=false;
        }
    }
}
int main()
{
    cin>>n;
    dfs(1);
}

树的bfs

bfs用于寻找最短路，因为他每次先把等距离的路径全搜完再搜索更进一步的路

bfs维护的数据结构：g[N][N]存图，d[N][N]存距离，一个queue存当下需要遍历的状态，并不断分裂队头状态为他的子状态并将子状态入队队尾

#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
const int N=110;
int n,m;
int g[N][N],d[N][N];
typedef pair<int,int> pii;
//不要建坐标系，x第x行，y第y列
void bfs()
{
    queue<pii> q;
    q.push({0,0});
    memset(d,-1,sizeof d);
    d[0][0]=0;
    int dx[4]={1,-1,0,0};
    int dy[4]={0,0,1,-1};
    while(q.size())
    {
        pii t=q.front();
        q.pop();
        for(int i=0;i<4;i++)
        {
            int x=t.first+dx[i];
            int y=t.second+dy[i];
            if(x>=0&&x<n&&y>=0&&y<m&&g[x][y]==0&&d[x][y]==-1)
            {
                q.push({x,y});
                d[x][y]=d[t.first][t.second]+1;
            }
        }
    }
}
int main()
{
    cin>>n>>m;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        cin>>g[i][j];
    }
    bfs();
    cout<<d[n-1][m-1];
}

图的dfs

考虑树的重心问题

定义：树的重心是一个节点，当从树中移除该节点（及其所有连接的边）后，剩余的子树中最大的那棵包含最少的节点数。换句话说，树的重心是将树分成若干部分时，使得各部分节点数尽可能均衡的那个节点

如何存储无向图？邻接表：开一个vector数组存储每一个点联通的点

#include<iostream>
#include<vector>
using namespace std;
const int N = 1e5+10;
vector<int> d[N];    //点u联通的点存在 vector d[u]中
int n,ans=N;   //注意ans的初始化
bool st[N];
void add(int a,int b)    //无向图
{
    d[a].push_back(b);
    d[b].push_back(a);
}
//求u的子支大小之和，包括u自己
int dfs(int u)
{
    st[u]=true;
    int sum=0,size=0;     //sum存子支大小之和，size存最大子支大小
    for(auto son:d[u])    //遍历所有联通点
    {
        if(st[son]) continue;    //已经遍历过，跳过
        int s=dfs(son);          //该子支大小
        sum+=s;                  //更新sum
        size=max(size,s);        //更新size
    }
    size=max(size,n-sum-1);      //更新size
    ans=min(ans,size);           //更新全局答案
    return sum+1;              
}
//所有点一定可以都被遍历到，因为这是联通图
int main()
{
    cin>>n;
    for(int i=0;i<n-1;i++)
    {
        int a,b;
        cin>>a>>b;
        add(a,b);
        add(b,a);
    }
    dfs(1);
    cout<<ans;
}

图的bfs

#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
using namespace std;
int n,m;
const int N = 1e5+10;
int d[N];
vector<int> e[N];
void add(int a,int b)
{
    e[a].push_back(b);
}
void bfs()
{
    memset(d,-1,sizeof d);
    queue<int> q;
    q.push(1);
    d[1]=0;
    while(q.size())
    {
        int t=q.front();
        q.pop();
        for(auto son:e[t])
        {
            if(d[son]!=-1) continue;
            else
            {
                q.push(son);
                d[son]=d[t]+1;
            }
        }
    }
   
}
int main()
{
    cin>>n>>m;
    for(int i=0;i<m;i++)
    {
        int a,b;
        cin>>a>>b;
        //注意有向边还是无向边
        add(a,b);
    }
    bfs();
    cout<<d[n];
}

拓扑序列

给定一个n个点 m 条边的有向图，点的编号是 1 到 n, 图中可能存在重边和自环。 请输出任意一个该有向图的拓扑序列，如果拓扑序列不存在，则输出 一1。 若一个由图中所有点构成的序列A满足：对于图中的每条边(x, y), x在 A 中都出现在 y之前，则称 A 是该图的 一个拓扑序列。

拓扑序列的主要思路是：关注入度的变化，一开始有入度为0的点直接入队，入队后更新他连接的子节点的入度，如果子节点的入度变为零则入队，直到队列变空
期间维护一个数组存储每次出队元素进入拓扑序列即可，最终cout出去。

#include<iostream>
#include<queue>
#include<vector>
#include<cstring>
using namespace std;
const int N = 1e5+10;
vector<int> d[N]; // 邻接表
int top[N],in[N],idx=-1,n,m;
//top存序列，in存入度，idx维护拓扑序列指针
void add(int a,int b)
{
    d[a].push_back(b);
}
bool topsort()
{
    queue<int> q;
    for(int i=1;i<=n;i++)
    {
        //一开始有入度为0的点直接入队
        if(!in[i]) q.push(i);
    }
    while(q.size())
    {
        //先删掉的点肯定是在拓扑序列前面的点，直接加入top
        int t=q.front();
        top[++idx]=t;
        q.pop();
        //分裂，更新他子节点的入度，判断每个子节点是否可以入队
        for(auto son: d[t])
        {
            in[son]--;
            if(in[son]==0) q.push(son);
        }
    }
    //判断所有点是否都用上，都用上说明这是一个拓扑序列
    return n==(idx+1);
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=0;i<m;i++)
    {
        int a,b; cin>>a>>b;
        add(a,b);
        in[b]++;
    }
    top[0]=-1;    
    if(topsort()) for(int i=0;i<=idx;i++) cout<<top[i]<<" ";
    else  cout<<"-1";
}

dijkstra求最短路

朴素版本

dijkstra适用于求所有边权都是正值的最短路，他基于贪心的基本思想。
简单来说，就是要维护这样的一个状态表格 $$\begin{array}{l|l|l|l|l|l|l|l}\text{步骤}&\text{S}&\text{v}2&\text{v}3&\text{v}4&\text{v}5&\text{v}6\\\hdashline1&\text{v}1&10&\infty&\infty&\infty&3\\\hline2&\text{v}1—\text{v}6&5&\infty&9&4\\\hdashline3&\text{v}1—\text{v}6—\text{v}5&\infty&\infty&\infty&\end{array}$$

g[N][N]存图，dist[N]存当前每个节点临时认定的最短路，再用st[N]存每个节点是否已经确认了最短状态，若st[i]==true,则dist[N]存的就是确定的最短路。
观察这个表，发现几条性质
- S列中，后面的路一定是由前面的路继续走出来的，因此一旦一条路作为全表最小被断言为最短，那么他一定就永远是最短，不可能被后续的路更新得更短，因为后面的路都是前面的路发展而来的 - 全表最小值t一定是当前状态的最短路，因为他无法更新了，他想由别的状态更新而来，然而别的状态还没接着走就都已经比他大了，而其他的未定dist还有可能接着更新，因为他有可能由t发展而来

为此我们的dist需要求每一列的最小值，也就是不断更新dist[j]=min(dist[t]+g[t][j]),同时每次循环中吧st[t]=true即可

#include<iostream>
#include<cstring>
using namespace std;
const int N = 510;
int g[N][N],dist[N],m,n;
bool st[N];
void dijkstra()
{
    memset(dist,0x3f,sizeof dist);
    dist[1]=0;
    for(int i=0;i<n;i++)
    {
        int t=0;
        for(int j=1;j<=n;j++)
        {
            //在没确定是否是最短路的集合中找出最短的
            if(!st[j]&&dist[j]<dist[t])
            {
                t=j;
            }
        }
        st[t]=true;
        //不必判断，全部更新即可，事实上st[j]==true的点不会被更新
        for(int j=1;j<=n;j++) dist[j]=min(dist[j],dist[t]+g[t][j]);
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    memset(g,0x3f,sizeof g);
    for(int i=0;i<m;i++)
    {
        int a,b,c; scanf("%d%d%d",&a,&b,&c);
        g[a][b]=min(g[a][b],c);
    }
    dijkstra();
    //这里是因为memset赋值是按字节赋值，把每个字节赋值为0x进制下的3f，为此dist作为int数组有4个字节，则应与0x3f3f3f3f比较大小
    if(dist[n]>=0x3f3f3f3f) printf("-1");
    else printf("%d",dist[n]);
}

堆优化版本

堆优化版本就是说，我们始终维护一个堆进行全局最小值的查询而非采用先前的遍历算法

#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
typedef pair<int,int> pii;
const int N = 151010;
vector<pii> node[N];
int n,m,dist[N];
bool st[N];
void addn(int a,int b,int c)
{
    node[a].push_back({b,c});
}
void dijkstra()
{
    memset(dist,0x3f,sizeof dist);
    dist[1] = 0;
    priority_queue<pii,vector<pii>,greater<pii>> heap;
    //dist,node，因为按照pii的第一个元素进行排序
    heap.push({0,1});
    
    while(heap.size())
    {
        auto t = heap.top();
        heap.pop();
        
        int j = t.second;
        int d = t.first;
        
        if(st[j]) continue;
        //懒惰删除
        st[j] = true;

        for(auto son :node[j])
        {
            int w = son.second;
            int idx = son.first;
            if(d+w<dist[idx]) {
                dist[idx] = d+w;
                //有了新dist就把新dist入堆
                heap.push({dist[idx],idx});
            }
        }
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=0;i<m;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        addn(a,b,c);
    }
    dijkstra();
    if(dist[n]>=0x3f3f3f3f) printf("-1");
    else printf("%d",dist[n]);
}

优先队列（heap）中可能会有冗余元素

冗余元素的出现主要是因为：

• 重复加入：在算法的执行过程中，同一个顶点可能会因为多条路径被多次加入优先队列。例如，如果存在多条从起点到某个顶点的路径，并且这些路径的长度不同，那么该顶点可能会在每次找到更短路径时被重新加入优先队列。
• 懒惰删除：Dijkstra 算法的这个实现并没有在更新某个顶点的距离后立即从优先队列中删除所有旧的、距离更大的该顶点元素。这是因为直接删除优先队列中的元素是复杂的（通常需要 O(log N) 的时间复杂度），而且不是必要的。算法通过 st 数组来标记已经处理过的顶点，当从优先队列中取出一个顶点时，首先检查它是否已经被处理过。如果已经被处理过，就直接跳过；否则，进行距离更新和相邻顶点的处理。

时间复杂度由O(nm)变为O(nlog(m)),改动在于全表最小距离的查找方式，由遍历查找的O(m)->堆查找的O(log(m))

bellman-ford算法

Bellman - ford 算法是求含负权图的单源最短路径的一种算法。
其原理为不断对所有边进行遍历，每次使用这条边{a->b,w}的信息和两个节点的dist看看能否更新dist[b]=min(dist[b],dist[a]+w)
当遍历到第k次的时候，对应的是找到了允许最多走k条边的情况下的所有路
如何理解？在每一次遍历的时候，相当于状态向外扩张，若一个点已经被遍历到，则dist非无穷，会更新与他相连的0x3f的dist
若一个点还没走到，那么他指向的下一个边也不会被更新
因此，若在 n-1 次松弛后还能更新，则说明图中有负环，因此无法得出结果，否则就完成 bellman-ford算法存边权信息很随意，只要可以遍历所有的边即可，为了简单考虑结构体方法。

时间复杂度O(nm)

#include<iostream>
#include<cstring>
using namespace std;
const int N =510,M = 10010;
int n,m,k,dist[N],last[N];
struct Edge{
    int a;
    int b;
    int w;
} edge[M];
void bellman_ford()
{
    memset(dist,0x3f,sizeof dist);
    dist[1]=0;
    for(int i=0;i<k;i++)
    {
        //必须有copy这一步，因为走k条边的dist是由走k-1条边的状态更新过来的，不copy会导致“串联”
        memcpy(last,dist,sizeof dist);
        for(int j=0;j<m;j++)
        {
            int a = edge[j].a;
            int b = edge[j].b;
            int w = edge[j].w;
            dist[b]=min(dist[b],last[a]+w);
        }
    }
}
int main()
{
    scanf("%d%d%d",&n,&m,&k);
    for(int i=0;i<m;i++)
    {
        int a,b,w;
        scanf("%d%d%d",&a,&b,&w);
        edge[i].a=a;
        edge[i].b=b;
        edge[i].w=w†;
    }
    bellman_ford();
    //这是考虑到负权边的存在，为此取了一个大的比较合适的数作为判断边界
    if(dist[n]>0x3f3f3f3f / 2) printf("impossible");
    else printf("%d",dist[n]);
    
}

bellman-ford算法绝大部分情况下时间复杂度高于SPFA，在需要限制最多走k条边的情况下才必须使用SPFA算法

SPFA算法(队列优化的Bellman-Ford算法)

我们发现一件事，一个被更新的节点才有可能更新他的子节点，因此没必要每次遍历所有边，只需要维护一个队列，队列里记录刚被更新过的点即可

#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
using namespace std;
const int N = 1e5+10;
const int M = 1e5+10;
typedef pair<int,int> pii;
vector<pii> adj[N];
int dist[N];
bool st[N];
void add(int a,int b,int c)
{
    adj[a].push_back({b,c});
}
void spfa()
{
    memset(dist,0x3f,sizeof dist);
    dist[1]=0;
    queue<int> q;
    q.push(1);
    st[1]=true;
    while(q.size())
    {
        int t = q.front();
        q.pop();
        st[t]=false;
        for(auto edge : adj[t])
        {
            int j = edge.first;
            int w = edge.second;
            if(dist[t]+w<dist[j])
            {
                if(!st[j]) q.push(j);
                dist[j]=dist[t]+w;
                st[j]=true; //不加也可以过
            }
                
        }
    }
}
int main()
{
    int n,m; scanf("%d%d",&n,&m);
    for(int i=0;i<m;i++)
    {
        int a,b,c; scanf("%d%d%d",&a,&b,&c);
        add(a,b,c);
    }
    spfa();
    if(dist[n]>0x3f3f3f3f/2) printf("impossible");   //图不联通
    else printf("%d",dist[n]);
}

SPFA判断负环

• 1，判断有无负环：有负环则会陷入负环无限循环，维护一个对应的cnt（某个点在路径中出现的次数），当远大于n说明陷入了无限循环
• 2，由于图未必联通，因此要注意我们不是判断1所在的独立图是否有负环，而是全体是否有负环，为此一开始将所有点入队

#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
using namespace std;
const int N = 1e5+10;
const int M = 1e5+10;
typedef pair<int,int> pii;
vector<pii> adj[N];
int dist[N],cnt[N],n,m;
bool st[N];
void add(int a,int b,int c)
{
    adj[a].push_back({b,c});
}
bool spfa()
{
    memset(dist,0x3f,sizeof dist);
    dist[1]=0;
    queue<int> q;
    for(int i=1;i<=n;i++) 
    {
        q.push(i);
        st[i]=true;
    }
    while(q.size())
    {
        int t = q.front();
        q.pop();
        st[t]=false;
        for(auto edge : adj[t])
        {
            int j = edge.first;
            int w = edge.second;
            if(dist[t]+w<dist[j])
            {
                if(!st[j]) q.push(j);
                dist[j]=dist[t]+w;
                cnt[j]++;
                if(cnt[j]>=n+2) return true;
                
            }
                
        }
    }
    return false;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=0;i<m;i++)
    {
        int a,b,c; scanf("%d%d%d",&a,&b,&c);
        add(a,b,c);
    }
    if(spfa()) printf("Yes");
    else printf("No");
    
}

floyd算法

floyd算法基于动态规划，定义d(k,i,j)为只经过前k个点的前提下，i到j的最小路。
状态更新方程为 d(k,i,j)=min(d(k-1,i,k)+d(k-1,k,j))
第一维可以省去

#include<iostream>
#include<cstring>
using namespace std;
const int N = 210;
int dist[N][N],n,m,k;
void floyd()
{
    for(int k=1;k<=n;k++)
    {
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]);
        }
    }
}
int main()
{
    memset(dist,0x3f,sizeof dist);
    scanf("%d%d%d",&n,&m,&k);
    for(int i=0;i<m;i++)
    {
        int a,b,c; scanf("%d%d%d",&a,&b,&c);
        dist[a][b]=min(dist[a][b],c);
    }
    for(int i=1;i<=n;i++)
    {
        dist[i][i]=0;
    }
    floyd();
    for(int i=0;i<k;i++)
    {
        int x,y; cin>>x>>y;
        if(dist[x][y]>0x3f3f3f3f/2) printf("impossible\n");
        else printf("%d\n",dist[x][y]);
    }
    
}

prim求最小生成树

• 最小生成树指的是用上全部顶点和适当的边使得这一图形构成一个树，求使得边权重和最小的树
• 思路和dijkstra类似，基本思路也是对外扩充，d[i]维护的是点i距离当前的树(集合)最小的距离，每次向外扩展树选取距离最近的点加进来，重复n次直到所有点都进来或者中间发现无法把所有点都加进来。期间用st[N]记录哪些点已经加进了生成树

#include<iostream>
#include<cstring>
using namespace std;
const int N = 510;
int g[N][N],d[N],st[N],n,m,res=0;
bool prim()
{
    memset(d,0x3f,sizeof d);
    d[1]=0;
    for(int i=0;i<n;i++)
    {
        int t=0;
        for(int j=1;j<=n;j++)
        {
            if(!st[j]&&d[j]<d[t]) t=j;
        }
        st[t] = true;
        res += d[t];
        if(d[t]==0x3f3f3f3f) return true;
        for(int j=1;j<=n;j++)
        {
            if(!st[j]) d[j]=min(d[j],g[t][j]);
        }
    }
    return false;
}
int main()
{
    memset(g,0x3f,sizeof g);
    scanf("%d%d",&n,&m);
    for(int i=0;i<m;i++)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        g[a][b]=min(g[a][b],c);
        g[b][a]=g[a][b];
    }
    if(prim()) printf("impossible");
    else printf("%d",res);
}

kruskal求最小生成树

• 将所有边按照权值的大小进行升序排序，然后从小到大一一判断。

• 如果这个边与之前选择的所有边不会组成回路，就选择这条边（并查集检查祖宗，应当不一样才可选择）；反之，舍去。

• 直到具有 n 个顶点的连通网筛选出来 n-1 条边为止。

• 筛选出来的边和所有的顶点构成此连通网的最小生成树。

此方法可以用数学归纳法证明：任何时候 Kruskal 算法选择的边集都被 MST 所包含：

奠基：

选择的第一条边必然属于MST，也就是证明最短的边一定属于MST，证明如下：倘若两点之间最短的边不属于MST，那么连接这两点，必然在MST中构成一个环，断开这个环上任意一条边都可使得MST更小，这不符合MST最优的性质，因此只能是选择的第一条边一定属于MST

归纳

如果选择的前k条边都属于MST，则下面遍历过程中被抛弃的边一定不属于MST，被选择的那条边一定就是MST里面的边 - 先证明遍历过程中被抛弃的边一定不属于MST：抛弃的边都是加入后会成环的边，由于我们由小到大的遍历顺序，成的这个环上边权最大的就是刚加进来的那条边，他不可能替代掉先前的任何一条边，为此此边可以抛弃 - 再证明被选择的边就是MST里面的边，这是因为他是第一个出现的不成环的边，后面出现的不成环的边一定比他权大，因此就选择这条边

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1e5+10;
const int M = 2e5+10;
int n,m,p[N],res=0,cnt=0;
struct Edge{
    int a,b,c;
    
} edge[M];
bool cmp(const Edge& e1,const Edge& e2)
{
    return(e1.c<e2.c);
}
int find(int x)
{
    if(p[x]!=x) p[x]=find(p[x]);
    return p[x];
}
bool kruskal()
{
    for(int i=1;i<=n;i++) p[i]=i;
    for(int i=0;i<m;i++)
    {
        int a = edge[i].a, b = edge[i].b,c = edge[i].c;
        int pa = find(a);int pb = find(b);
        if (pa != pb)
        {
            p[pa] = pb;
            res += c;
            cnt ++ ;
        }
    }
    if(cnt<n-1) return false;
    else return true;
}
int main()
{
    scanf("%d%d",&n,&m);
    for (int i = 0; i < m; i ++ )
    {
        int a, b, w;
        scanf("%d%d%d", &a, &b, &w);
        edge[i] = {a, b, w};
    }
    sort(edge,edge+m,cmp);
    if(kruskal()) printf("%d",res);
    else printf("impossible");
    
}

染色法判断二分图

这个题的图包含连通图和非连通图两种情况，若是连通图便不需要主函数里的for循环了，但是这里只需处理非联通图即可，主函数使用for循环枚举所有图，就把两种情况都包含进去了

#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
int n,m;
const int N = 1e5+10;
const int M = 1e5+10;
int color[N];
vector<int> edge[N];
void add(int a,int b)
{
    edge[a].push_back(b);
    edge[b].push_back(a);
}
bool dfs(int x,int c)
{
    color[x]=c;
    for(auto t: edge[x])
    {
        if(!color[t])
        {
            if(!dfs(t,3-c)) return false;
        }
        if(color[t]==c) return false;
    }
    return true;
    
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=0;i<m;i++)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        add(u,v);
    }
    bool flag=true;
    for(int i=1;i<=n;i++)
    {
        if(!color[i])
        {
            if(!dfs(i,1))
            {
                flag=false;
                break;
            }
        }
    }
    if(flag) printf("Yes");
    else printf("No");
}

最短路的总结