图论

· · 个人记录

目录

1.图的基础算法

2.集合合并

3.最短路

4.最小生成树

5.拓扑排序

6.强连通分量

7.最近公共祖先

一、图的基础算法

\left (1 \right )图的遍历

1.邻接矩阵

①定义：

int ditu[N][N]; //N为点的个数

②遍历:

for(int i=1;i<=N;i++)
{
    for(int j=1;j<=N;j++)
    {
        ditu[i][j]=z;//指i到j有路径且边权为ditu[i][j]=z
    }
}

③好处：好写，遍历起来方便

④坏处：不能有重边，0<=N<=3000,数据范围太小，限制太大

⑤使用时候：N数据较小，\left ( 0<=N<=3000\right )，或是在算法Floyed时配套使用

⑥空间复杂度：O\left ( N^2\right )

2.邻接表

①定义：

vector<int>vc[N],vcw[N];//vc[N]是x到y的路径，vcw[M]是它们的边权

for(int i=1;i<=M;i++)//M是路径条数
{
    int x,y;//有两个点联通
    vc[x].push_back(y);//x到y有路径
    vcw[x].push_back(w);//x到y边权为w
}

②遍历

int l = vc[f1].size();//f1为起点
for(int i=0;i<l;i++)
{
    int t = vc[f1].at(i);//t为终点
    int tv = vcw[f1].at(i);//tv为边权
}

③好处：动态数组，比邻接矩阵范围更大

④坏处：受到vector影响，访问需要时间，速度受限

⑤使用时候：基本不用。

⑥空间复杂度：O\left (N \right )

3.链式前向星

①定义：

struct edge 
{
    int to,next,v;
}e[M];//前向星结构体 
int head[N],ei=0;
int add(int x,int y,int v)//建图函数 
{
    ei++;
    e[ei].next=head[x];
    e[ei].to=y;
    e[ei].v=v;
    head[x]=ei;
}

for(int i=1;i<=M;i++)
{
    add(x,y,v);//指起点为x，终点为y，边权为v 
}

②遍历：

for(int i=head[from];i;i=e[i].next)//from为起点 
{
    int to=e[i].to;//寻找它的终点to 
}

③优点：速度快，使用灵活

④坏处：代码长，不好写，常数高

⑤使用时候：几乎所有时候

⑥空间复杂度;O\left ( M+N \right )

二、集合合并

\left (1 \right )并查集

1.定义：（以下摘自维基百科）

在计算机科学中，并查集是一种树型的数据结构，用于处理一些不交集（Disjoint Sets）的合并及查询问题。

个人理解：

因为并查集是一种树型的数据结构，它的原理就是不断寻找父亲，并判断是否是同一个父亲，这就是并查集的本质

2.考点：kruscal算法，判断几个数是否为同一集合。

3.代码实现：

①不初始化+递归（附带路径压缩+Rank合并）

int f[N];//父亲数组
inline int findf(int x)//Find：确定元素属于哪一个子集。它可以被用来确定两个元素是否属于同一子集。
{
    if(f[x]==0)
    {
        return x;
    }
    f[x]=findf(f[x]);
    return f[x];
}
inline int uion(int x,int y)//Union：将两个子集合并成同一个集合。
{
    x=findf(x);
    y=findf(y);
    if(x!=y)
    {
        f[x]=y; 
    } 
}

②初始化+循环（附带路径压缩+Rank合并）

int pre[N];
int find(int x)//查找根节点
{ 
    int r=x;
    while(pre[r]!=r)//返回根节点 r（初始化） 
    {
        r=pre[r];
    }
    int i=x,j;
    while(i!=r)//路径压缩
    {
        j=pre[i];// 在改变上级之前用临时变量  j 记录下他的值 
        pre[i]=r;//把上级改为根节点
        i=j;
    }
    return r;
}
void join(int x,int y)//判断x y是否连通,如果已经连通，就不用管了,如果不连通，就把它们所在的连通分支合并起。 
{
    int fx=find(x),fy=find(y);
    if(fx!=fy)
    {
        pre[fx]=fy;
    }    
}

4.时间复杂度：O\left ( \alpha \left(N \right )\right )

其中 {\displaystyle \alpha (N)} 是{\displaystyle n=f(x)=A(x,x)}的反函数,{\displaystyle A}是急速增加的阿克曼函数。因为{\displaystyle \alpha (N)} 是其反函数，故 {\displaystyle \alpha (N)} 在 {\displaystyle N} 十分巨大时还是小于 5。

因此，平均运行时间是一个极小的常数。

5.空间复杂度：O(N)

未完待续......