图论初步

想不好名字 · 2021-08-13 09:09:01 · 个人记录

图论

基础概念

1. 有向图：图的边有方向，只能按箭头方向从一点到另一点。(a)就是一个有向图。
2. 无向图：图的边没有方向，可以双向。(b)就是一个无向图。

• 结点的度：无向图中与结点相连的边的数目，称为结点的度。

• 结点的入度：在有向图中，以这个结点为终点的有向边的数目。

• 结点的出度：在有向图中，以这个结点为起点的有向边的数目。

• 权值：边的“费用”，可以形象地理解为边的长度。

• 连通：如果图中结点U，V之间存在一条从U通过若干条边、点到达V的通路，则称U、V 是连通的。

• 回路：起点和终点相同的路径，称为回路，或“环”。

• 完全图：一个n 阶的完全无向图含有n(n-1)/2 条边；一个n 阶的完全有向图含有n(n-1)条边；

• 稠密图：一个边数接近完全图的图。

• 稀疏图：一个边数远远少于完全图的图。 　　　　

• //强连通分量：有向图中任意两点都连通的最大子图。

图的存储和遍历

1. 邻接矩阵（傻子都能看懂，不做解释）

int to[301][301];
void init()
{
    for(int x , y , v , i = 1;i <= n;i ++)
    {
        cin>> x >> y >> v;
        to[x][y] = to[y][x] = v;
    }
}

2. 链式前向星

//ltp表示已存储的边数 
//lk[i]:表示i这个点当前所加入的最后一条边的编号
//nxt[i]:表示编号为j的边的上一条边的编号,to[j]表示j这条边的所达; 

struct edg
{
    int nxt,y;
}e[2021000];
int lk[100001],ltp;
int nd[100001];

void ist(int x,int y)
{
    e[++ltp]={lk[x],y};
    lk[x]=ltp;
    nd[x]++;
}

再写一下链式前向星的遍历，邻接矩阵就不看了，根本就不用遍历

for(int i=lk[now];i;i=e[i].nxt)
{
       //代码部分
 }

原理见链式前向星的存储方式。

拓扑排序

• 按照发生的前后来排序。

• 前提：这个图是一个有向无环图。

• 执行步骤：

  1. 由AOV网构造拓扑序列的拓扑排序算法主要是循环执行以下两步，直到不存在入度为0的顶点为止。
  2. 一个入度为0的顶点并输出之；
  3. 从网中删除此顶点及所有出边。
  4. 循环结束后，若输出的顶点数小于网中的顶点数，则输出“有回路”信息，否则输出的顶点序列就是一种拓扑序列。

代码

#include<iostream>
#include<queue>

using namespace std;

int n,m;

struct edg
{
    int nxt,y;
}e[200010];

int dp[100010];
int lk[100001]; 
int ltp;
int nd[100001];

queue < int > q;

void ist(int x,int y)
{c 
    e[++ltp]=(edg){lk[x],y};
    lk[x]=ltp;
    ++nd[y];
}

void tuopu()
{
    while(!q.empty())
    {
        int now=q.front();q.pop();
        for(int i=lk[now];i;i=e[i].nxt)
        {
            int v=e[i].y;
            nd[v]--;
            if(!nd[v])
            q.push(e[i].y);
        }
    }
}

int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;++i)
    {
        int a,b;
        cin>>a>>b;
        ist(a,b);
    } 
    for(int i=1;i<=n;++i)
    {
        if(!nd[i])
        {
            dp[i]=1;
            q.push(i);
        }
    }
    tuopu();
} 

最短路

dij

SPFA

主要运用队列和BFS，可以用来处理负边权，但处理正边权容易被卡。 时间复杂度O（NK）k一般小于2 ，被卡后变成O（N{2})

int first[MAXN],next[MAXN];//入度，出度
int u[MAXN],v[MAXN],w[MAXN];//边，边，边权
int dis[MAXN];//标记最长距离
int book [MAXN];//标记点
int c[MAXN];//统计次数，处理负边权
int n,m;//顶点，边
int flag;//标记正负
int spfa(int s,int n)
{
    memset(dis,0x3f,sizeof(dis))//初始化
    dis[s]=0;自己到自己最大长度一定是0
    q.push(s);
    memset(book,0,sizeof(book));
    memset(c,0,sizeof(c));
    book[s]=1;//进去之后标记一下
    flag=0;
    while(!q.empty())
    {
        int x=q.front();q.pop();
        book[x]=0;//
        for(int i=first[i];i!=-1;i=next[i]) //邻接表
        {
            int y=v[k];
            if(dis[x]+w[i]<dis[y])
            {
                dis[y]=dis[x]+w[i];
                if(!book[y])
                {
                    book[y]=1;
                    c[y]++;
                    q.push(y);
                    if(c[y]>n)
                    return flag=0;
                }
            }
        }
    }
}
int main()
{
    int x,y,z;
    while(~cin>>n>>m)
    {
        memset(first,-1,sizeof(first));
      for(int i=1;i<=m;++i)
      {
            cin>>x>>y>>z;
            next[i]=first[u[i]];
            first[u[i]]=i;
     }

Floyd