图论复习

lijunhao2023 · 2021-07-14 01:07:16 · 个人记录

by lijunhao2023.
今天就要考试了，怎么写得完啊QwQ

图

定义

图(Graph)是由顶点的有穷非空集合和顶点之间边的集合组成，通常表 示为:G(V,E)，其中，G表示一个图，V是图G中顶点的集合，E是图G中边的集合。

分类

图是按照无方向和有方向分为无向图和有向图。

无向图

连接方式

用不带箭头的边连接两个有关联的结点。

无向完全图

在具有n个结点的无向图中，边的最大数目为n*(n-1)/2。边数达到最 大值的图称为无向完全图。

有向图

连接方式

在有向图中,通常用带箭头的边连接两个有关联的结点(方向由前指向后)。

入度

高级定义：其前继个数称为该结点的入度。
大白话：有多少个箭头指着这个节点的屁股。

出度

大白话：这个结点指向了多少个结点的屁股。

图的储存

邻接矩阵

用数组表示从i到j的距离。

#define maxn 1000 //图的边界，视具体情况而定
type a[maxn][maxn]; // type:int,long,double... 用于表示有没有边和路程长度
bool flag[maxn];//标记访问过的结点

邻接表 (using 前向星）

struct edge {
    int to,//
    next,//
    v;//权值
}w[400005];

这些不重要，直接跳过

省略100行...

图的遍历

BFS

其他BFS看这里:暂时还没有。。。
q:队列

void BFS() {
    int i,L=0,R=0,x,y;
    for(i=2;i<=n;i++)d[i]=INF;//初始化为无限
    d[1]=0; 
    R++;
    q[R]=1;
    g[1]=1;
    while(L<R) { 
        x=q[++L];
        vst[x]=1;
    for(i=h[x];i;i=w[i].nx) {   
    y=w[i].to;
    if(!vst[y]) { 
        vst[y]=1; 
        d[y]=d[x]+1; 
        g[y]=g[x];
        q[++R]=y; //y入队
    }
    else if(d[x]+1==d[y])
        g[y]=(g[y]+g[x])%mod;
        }
    }
}