美文网首页
清北NOIP训练营集训笔记——图论(提高组精英班)

清北NOIP训练营集训笔记——图论(提高组精英班)

作者: 清北OI | 来源:发表于2019-06-05 19:08 被阅读0次

    清北NOIP训练营集训笔记——图论(提高组精英班)

    本文摘自清北学堂内部图论笔记,作者为潘恺璠,来自柳铁一中曾参加过清北训练营提高组精英班,笔记非常详细,特分享给大家!更多信息学资源关注微信订阅号noipnoi。

    最短路径:

    1.Floyd算法(插点法):

    通过一个图的权值矩阵求出它的每两点间的最短路径(多源最短路)。

    算法描述:

    一个十分暴力又经典的DP,假设i到j的路径有两种状态:

    ①i和j直接有路径相连:[if !vml]

    [endif]

    ②i和j间接联通,中间有k号节点联通:[if !vml]

    [endif]

    假设dis[i][j]表示从i到j的最短路径,对于存在的每个节点k,我们检查一遍dis[i][k]+dis[k][j]。

    //Floyd算法,时间复杂度:O(n^3) 

    //Floyd算法,时间复杂度:O(n^3)

    int dis[MAXN][MAXN];

    for(k=1;k<=n;k++)//枚举

    {

    for(i=1;i<=n;i++)

    {

    for(j=1;j<=n;j++)

    {

    dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);//DP

    }

    }

    }

    【清北2019NOIP夏令营助你圆梦OI】

    2.Dijkstra算法(无向图,无负权边):

    算法描述:

    多源最短路!

    a.初始时,S只包含源点,即S={v},v的距离为0。U包含除v外的其他顶点,即:U={其余顶点},若v与U中顶点u有边,则<u,v>正常有权值,若u不是v的出边邻接点,则<u,v>权值为∞。

    b.从U中选取一个距离v最小的顶点k,把k,加入S中(该选定的距离就是v到k的最短路径长度)。

    c.以k为新考虑的中间点,修改U中各顶点的距离;若从源点v到顶点u的距离(经过顶点k)比原来距离(不经过顶点k)短,则修改顶点u的距离值,修改后的距离值的顶点k的距离加上边上的权。

    d.重复步骤b和c直到所有顶点都包含在S中。

    啊~上面的的乱七八糟的概念太难懂了,还是举个例子吧!如下图!

    [if !vml]

    [endif]

    我们假设1号节点为原点。

    第一轮,我们可以算出2,3,4,5,6号节点到原点1的距离为[7,9,∞,∞,14],∞表示无穷大(节点间无法直接连通),取其中最小的7,就确定了1->1的最短路径为0,1->2的最短路径为7,同时取最短路径最小的2节点为下一轮的前驱节点。

    第二轮,取2节点为前驱节点,按照 前驱节点到原点的最短距离 + 新节点到前驱节点的距离 来计算新的最短距离,可以得到3,4,5,6号节点到原点1的距离为[17,22,∞,∞](新节点必须经过2号节点回到原点),这时候需要将新结果和上一轮计算的结果比较,3号节点:17>9,最短路径仍然为9;4号节点:22<∞,更新4号节点的最短路径为22,;5号节点:仍然不变为∞;6号节点:14<∞,更新6号节点的最短路径为14。得到本轮的最短距离为[9,22,∞,14],1->3的最短路径为9,同时取最短路径最小的3节点为下一轮的前驱节点。

    第三轮:同理上,以3号节点为前驱节点,可以得到4,5,6号节点到原点1的距离为[20,∞,11],根据最短路径原则,和上一轮最短距离比较,刷新为[20,∞,11],1->3->6的最短路径为11,同时取最短路径最小的6节点为下一轮的前驱节点。

    第四轮:同理,得到4,5号节点最短距离为[20,20],这两个值相等,运算结束,到达这两个点的最短距离都是20,如果这两个值不相等,还要进行第五轮运算!

    #include<cstdio>

    #include<cstring>

    const int

    N=100500;

    const int

    M=200500;

    int

    point[N]={0},to[M]={0},next[M]={0},len[M]={0},cc=0;

    int dis[N];//最短路长度,dis[i]表示第i号点到源点(1号点)的最短距离

    bool ever[N];//当前节点最短路有没有确定 

    int n,m; 

    void AddEdge(int

    x,int y,int z)//添加新的边和节点:x到y边长z

    {

    cc++;

    next[cc]=point[x];

    point[x]=cc;

    to[cc]=y;

    len[cc]=z;//len记录x到y的边长 

    }

    int main()

    {

        int

    i,j,k;

    scanf("%d%d",&n,&m);

    for(i=1;i<=m;i++)

        {

        int a,b,c;

        scanf("%d%d%d",&a,&b,&c);

        AddEdge(a,b,c);//无向图,要加两遍 

        AddEdge(b,a,c);

        }

    memset(dis,0x3f,sizeof dis);//用极大值来初始化 

    dis[1]=0;//1号节点到自己最短距离为0 

    for(k=1;k<=n;k++)

        {

        int minp,minz=123456789;

        for(i=1;i<=n;i++)

        {

            if(!ever[i])

            {

                if(dis[i]<minz)

                {

                    minz=dis[i];

                    minp=i;

                }

            }

        }

        ever[minp]=1;

        int now=point[minp];

        while(now)

        {

          int tox=to[now];

            if(dis[tox]>dis[minp]+len[now])

            dis[tox]=dis[minp]+len[now];

            now=next[now];

        }

        }

    for(i=1;i<=n;i++)

        printf("%d\n",dis[i]);

    return 0;

    【清北2019NOIP夏令营与你相随OI之路】

    3.SPFA算法(有负权边,无负圈,能检测负圈但不能输出):

    多源最短路!

    SPFA和Dijkstra极为相似,只是加了个队列优化来检测负圈和负权边。

    算法描述:

    建立一个队列,初始时队列里只有起始点,再建立一个表格记录起始点到所有点的最短路径(该表格的初始值要赋为极大值,该点到他本身的路径赋为0)。然后执行松弛操作,用队列里有的点作为起始点去刷新到所有点的最短路,如果刷新成功且被刷新点不在队列中则把该点加入到队列最后。重复执行直到队列为空。

    判断有无负环:如果某个点进入队列的次数超过N次则存在负环(SPFA无法处理带负环的图)

    #include<cstdio>

    #include<cstring>

    const int

    N=100500;

    const int

    M=200500;

    int

    point[N]={0},to[M]={0},next[M]={0},len[M]={0},cc=0;

    int dis[N];//最短路长度

    int

    queue[N],top,tail;//双向队列queue,队头,队尾 

    bool in[N];//记录这个点在不在队列中,1表示在,0表示不在 

    int n,m; //n个节点,m条边 

    void AddEdge(int

    x,int y,int z)//x到y边长为z 

    {

    cc++;

    next[cc]=point[x];

    point[x]=cc;

    to[cc]=y;

    len[cc]=z;

    }

    int main()

    {

        int

    i,j;

        scanf("%d%d",&n,&m);

    for(i=1;i<=m;i++)

        {

        int a,b,c;

        scanf("%d%d%d",&a,&b,&c);

        AddEdge(a,b,c);//因为是双向队列,左边加一次,右边加一次

        AddEdge(b,a,c);

        }

    memset(dis,0x3f,sizeof dis);//用极大值来初始化

    dis[1]=0;//1号节点到自己最短距离为0 

        top=0;tail=1;queue[1]=1;in[1]=1;//初始化,只有原点加入 

    while(top!=tail)

        {

        top++;

        top%=N;

        int now=queue[top];

        in[now]=0;

        int ed=point[now];

        while(ed)

        {

            int tox=to[ed];

            if(dis[tox]>dis[now]+len[ed])

            {

                dis[tox]=dis[now]+len[ed];

                if(!in[tox])

                {

                    tail++;

                    tail%=N;

                    queue[tail]=tox;

                    in[tox]=1;

                }

            }

            ed=next[ed];

        }

        }

    for(i=1;i<=n;i++)

        printf("%d\n",dis[i]);

    return 0; 

    }

    4.Bellman Ford算法(有负权边,可能有负圈,能检测负圈并输出):

    单源最短路!

    算法描述:

    1.初始化:将除源点外的所有顶点的最短距离估计值d[all]=+∞, d[start]=0;

    2.迭代求解:反复对边集E中的每条边进行松弛操作,使得顶点集V中的每个顶点v的最短距离估计值逐步逼近其最短距离;(运行|v|-1次)

    3.检验负权回路:判断边集E中的每一条边的两个端点是否收敛。如果存在未收敛的顶点,则算法返回false,表明问题无解;否则算法返回true,并且从源点可达的顶点v的最短距离保存在 d[v]中。

    简单的说,如下图所示:

    [if !vml]

    [endif]

    松弛计算之前,点B的值是8,但是点A的值加上边上的权重2,得到5,比点B的值(8)小,所以,点B的值减小为5。这个过程的意义是,找到了一条通向B点更短的路线,且该路线是先经过点A,然后通过权重为2的边,到达点B

    如果出现了以下情况:

    [if !vml]

    [endif]

    松弛操作后,变为7,7>6,这样就不修改(Bellman Frod算法的高妙之处就在这),保留原来的最短路径就OK,代码实现起来非常简单。

    int n,m;//n个点,m条边 

    struct Edge//定义图类型结构体 

    {

        int

    a,b,c;//a到b长度为c 

    }edge[];

    int dis[];

    memset(dis,0x3f,sizeof

    dis);

    dis[1]=0;

    for(int

    i=1;i<n;i++)

    {

    for(int j=1;j<=m;j++)

        {

        if(dis[edge[j].b]>dis[edge[j].a]+edge[j].c)

        {

            dis[edge[j].b]=dis[edge[j].a]+edge[j].c; 

        }

        }

    }

    5.A*算法:

    这玩意儿我是没看懂,等以后我看懂了再更吧(无奈脸)~

    七、拓扑排序:

    对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序,是将G中所有顶点排成一个线性序列,使得图中任意一对顶点u和v,若边(u,v)∈E(G),则u在线性序列中出现在v之前。通常,这样的线性序列称为满足拓扑次序(Topological Order)的序列,简称拓扑序列。

    打个比喻:我们要做好一盘菜名字叫做红烧茄子,那么第一步得买茄子和配料,第二步就是要洗茄子,第三步就是要开始倒油进锅里啊什么七七八八的,第四步…,你不可能先洗茄子再买茄子和配料,这样的一些事件必须是按照顺序进行的,这些依次进行的事件就构成了一个拓扑序列。

    算法描述:

    我们需要一个栈或者队列,两者都可以无所谓,只是找个容器把入度为0的元素维护起来而已。

    ①从有向图中选择一个入度为0(无前驱)的顶点,输出它。

    ②从网中删去该节点,并且删去从该节点出发的所有有向边。

    ③重复以上两步,直到剩余的网中不再存在没有前驱的节点为止。

    具体操作过程如下:

    若栈非空,则在栈中弹出一个元素,然后枚举这个点能到的每一个点将它的入度-1(删去一条边),如果入度=0,则压入栈中。如果没有输出所有的顶点,则有向图中一定存在环

    //拓扑排序,时间复杂度:O(n+m) 

    #include<cstdio>

    #include<cstring>

    const int

    N=100500;

    const int

    M=200500;

    int

    point[N]={0},to[M]={0},next[M]={0},cc=0;

    int xu[N]={0};//栈,初始值为空,xu[0]表示栈的大小 

    int in[N]={0};//入度,a可以到达b,in[b]++ 

    int

    ans[N]={0};//ans[0]整个拓扑序列的大小 

    int n,m; 

    void AddEdge(int

    x,int y)//邻接表a到b 

    {

    cc++;

    next[cc]=point[x];

    point[x]=cc;

    to[cc]=y;

    }

    int main()

    {

        int

    i,j;

    scanf("%d%d",&n,&m);

    for(i=1;i<=m;i++)

        {

        int a,b;

        scanf("%d%d",&a,&b);

        in[b]++;//统计每个节点的入度 

        AddEdge(a,b);

        }

    for(i=1;i<=n;i++)

        {

        if(in[i]==0)//这个节点入度为0,压入栈 

        xu[++xu[0]]=i;

        }

    while(xu[0])

        {

        int now=xu[xu[0]];//出栈 

        xu[0]--;

        ans[++ans[0]]=now;

        int ed=point[now];

        while(ed)

        {

            int tox=to[ed];

            in[tox]--;

            if(!in[tox])

            xu[++xu[0]]=tox;

            ed=next[ed];//找下一个相邻节点 

        }

        }

    if(ans[0]<n)//有向图中一定存在环,无结果 

    printf("no solution");

        else

        {

        for(i=1;i<=n;i++)

        printf("%d ",ans[i]);

        }

    return 0;

    }

    联通分量:

    强连通:有向图中,从a能到b并且从b可以到a,那么a和b强连通。

    强连通图:有向图中,任意一对点都满足强连通,则这个图被称为强连通图。

    强联通分量:有向图中的极大强连通子图,就是强连通分量。

    一般用Tarjan算法求有向图强连通分量:

    欧拉路径与哈密顿路径:

    1.欧拉路径:从某点出发一笔画遍历每一条边形成的路径。

    欧拉回路:在欧拉路径的基础上回到起点的路径(从起点出发一笔画遍历每一条边)。

    欧拉路径存在:

    无向图:当且仅当该图所有顶点的度数为偶数

    或者 除了两个度数为奇数外其余的全是偶数。

    有向图:当且仅当该图所有顶点出度=入度 或者 一个顶点 出度=入度+1,另一个顶点 入度=出度+1,其他顶点出度=入度

    欧拉回路存在:

    无向图:每个顶点的度数都是偶数,则存在欧拉回路。

    有向图:每个顶点的入度都等于出度,则存在欧拉回路。

    求欧拉路径/欧拉回路算法常常用Fleury算法:

    在这里推荐一个不错的知乎作者:神秘OIer

    2.哈密顿路径:每个点恰好经过一次的路径是哈密顿路径。

    哈密顿回路:起点与终点之间有边相连的哈密顿路径是哈密顿回路。

    相关文章

      网友评论

          本文标题:清北NOIP训练营集训笔记——图论(提高组精英班)

          本文链接:https://www.haomeiwen.com/subject/cqgsxctx.html