链式前向星

一种存储图的数据结构 。

建立一个结构体和一个数组加一个变量，这里的to代表边 \((u,v)\) 中的 \(v\) 结点，而 \(edge\) 数组的索引 \(idx\) 代表 \(u\) ，其中 \(w\) 代表权值， \(next\) 代表以 \(u\) 为起始点的上一个边。 \(head\) 代表这个 \(x\) 结点在 \(edge\) 数组中的最后一个边的下标索引， \(cnt\) 用于记录边时当 \(edge\) 的下标索引用.

                        
                          struct {
  int to, w, next;
} edge[MAX_N];
int head[MAX_N], cnt = 0;

                        
                      

为链式前向星添加边 。

1. ++cnt 为新添加的边选择一个空变量
2. edge[++cnt].next=head[u] 代表让 \(edge[cnt]\) 中的 \(next\) 变量指向 \(u\) 结点的上一个边
3. \(head[u]=cnt\) 代表更新结点 \(u\) 的最后一条边在 \(edge\) 中的下标

                        
                          edge[++cnt].next=head[u];
edge[cnt].w=w;
edge[cnt].to=v;
head[u]=cnt;

                        
                      

遍历 。

首先获取结点 \(x\) 的最后一条边，经过数据处理后，将i移向结点 \(x\) 的上一条边 。

                        
                          for(int i=head[x];i;i=edge[i].next)

                        
                      

SPFA算法

求最小单源路径 。

1. 将源点放入队列中，并标志源点 \(s\) 已经在队列之中 \(vis[s]=true\)
2. 进入一个循环，当队列为空，各节点的最短路径便求出来了
3. 从队列中取出一个结点，并更新标志，遍历该结点的边，对符合条件的各边 \(dis[edge[i].to]>dis[v]+edge[i].w\) 进行松弛，然后如果符合条件的松弛边目标结点如果未在队列中，则放入，更改标志。

松弛：对于每个顶点v∈V，都设置一个属性 \(d[v]\) ，用来描述从源点s到v的最短路径上权值的上界，称为最短路径估计。就是这个操作 \(dis[edge[i].to] = dis[v] + edge[i].w;\) 。

                        
                            queue<int> que;
  que.emplace(s);
  vis[s] = true;
  while (!que.empty()) {
    int v = que.front();
    que.pop();
    vis[v] = false;
    for (int i = head[v]; i; i = edge[i].next) {
      if (dis[v] + edge[i].w < dis[edge[i].to]) {
        dis[edge[i].to] = dis[v] + edge[i].w;
        if (!vis[edge[i].to]) {
          que.emplace(edge[i].to);
          vis[edge[i].to] = true;
        }
      }
    }
  }

                        
                      

求是否存在负环 。

如果一个图存在负环，那么其的最短路径一定会存在一个无限循环，经过负环后，路径越来越小，那么一定有一些结点，一直入队出队，判断是否有结点入队次数大于 \(n\) 次 。

                        
                            queue<int> que;
  que.emplace(1);
  vis[1]=true,dis[1]=0;
  while (!que.empty()) {
    int v = que.front();
    que.pop();
    vis[v] = false;
    fe(ver, G[v]) if (dis[ver.to] > dis[v] + ver.cost) {
      dis[ver.to] = dis[v] + ver.cost;
      if (!vis[ver.to]) {
        if (++cnt[ver.to] >= n) {
            //存在负环
        }
        que.emplace(ver.to);
        vis[ver.to] = true;
      }
    }
  }

                        
                      

最后此篇关于SPFA和链式前向星的文章就讲到这里了,如果你想了解更多关于SPFA和链式前向星的内容请搜索CFSDN的文章或继续浏览相关文章，希望大家以后支持我的博客！ 。