猫史档案馆

【C++OI教程提高】基础图论问题程序设计详细讲解



图论〔Graph Theory〕是数学的一个分支，属于应用数学，《离散数学及其应用》里面就有。

图论也是OI中非常重要的一项，是打OI必须掌握的。

概念

center_image

点：图中 1~10 都成为点。

边：连接点与点的双向或单向的边。

点权：如果不同的点有不同的值，那么这些值就叫点权。

边权：如果不同的边有不同的值，那么这些值就叫边权。

有向边：从点v到点u连接的一条有向边，表示能从v到达u，但不能从u到达v。

无向边：点v与点u间有一条无向边，表示v,u能互相到达。

连通图：无向图中，每个点都能互相到达。

强连通图：有向图中，每个点都能互相到达。

环：有一个点通过边能绕回到原来的点，那么就形成了环。

欧拉回路：专门指有向图中，一个点能通过边绕回到原来的点，并且每条边只走过一次。简单地说就是能够绕回来的一笔画。其中必然有环。

欧拉路径：绕不回来但是能一笔画的。

建图

（先来看看蒟蒻的一篇博客吧--->https://www.luogu.com.cn/blog/Jazzq喵/tu-lun-zong-jie-yi-post）

一般来讲存图如果不用向量或者什么自带的数据结构喵存的话，有如下两种。

邻接矩阵

简单地说，存一个二维数组g[i][j]表示i节点和j节点，如果两个点中间有边，那么g[i][j]=(边权)，如果没有边，默认为无穷大。

//先把g数组全弄成一个很大的数，表示没有边，代码略
for(i=0;i<m;i++){
    cin>>x>>y>>z;//x,y是两个节点，z是他们的边的权值
    g[x][y]=z;//如果是无向图就对称一下
}

邻接表

邻接表貌似更强一点，不过蒟蒻觉得太难了

邻接表就是把与顶点相连的边弄成一条链。

像下面这样就行了，非常简单

struct edge{
    int to;//这条边的终点
    int next;//下条边的编号
    int w;//边权
}e[xxxx]；//多少自定
//这里在弄一些变量记录边数和next的编号，比如m和bh
void readd(int x,int y,int z){
    m++;
    e[m].to=y;
    e[m].next=bh[x];
    bh[x]=m;
    e[m].w=z;
}

注意一下稠密图还是用邻接矩阵好一点。

遍历

（先来看看蒟蒻的一篇博客吧--->https://www.luogu.com.cn/blog/Jazzq喵/tu-lun-zong-jie-er-post）

DFS 和 BFS 都行。

（这里只讲邻接矩阵存图）

深度优先

深搜的话，简单地说就是找一个点，按一定的顺序访问和这个点相连的其他点，每个点都这么操作，到头了就返回，再弄一些标记免得重复。

像下面这样就行了。

bool v[xxxx];
bool g[xxxx][xxxx];
void search(int p){
    v[p]=1;//标记访问
    for(i=1;i<=n;i++){
        if(!g[p][i])continue;//没边，跳
        if(vis[i])continue;//访问了，跳
        dfs(i);//递归，应该看得懂
    }
}

当然这个只是展现了过程，如果要更多功能那么最好弄个栈还有一些其他什么东西。

其实我觉得和图论没关系的一些深搜回溯题即使不用栈也是模拟了栈的过程，递归就是用栈来实现的。

广度优先

总的来说就是用一个队列呗，先随便入队一个，然后访问队头把和队头相连的全都加进队列（前提是这个节点不在队列里面），然后把队头拿出来，重复执行即可。

还是有于本人太懒，直接手动写队列了，不想弄queue。

像下面这样就行了。

for(i=1;i<=n;i++){
    if(vis[i])continue;
    int head=1,tail=1;
    q[1]=i;
    vis[i]=1;
    while(h<=l){
        u=q[head++];
        for(j=bh[u;j;j=e[j].next){
            int v=e[j].to;
            if(vis[v])continue;
            vis[v]=1;
            q[++tail]=v;
        }
    }
}
//注释不打了吧，邻接表应该都还记得，过程前面也讲了。

如此简单。

猫史档案馆

【C++OI教程提高】基础图论问题程序设计详细讲解

回复