提高组精英班 2017清北学堂集训笔记——图论( 五 ) _最小生成树

判断有无负环：
如果某个点进入队列的次数超过N次则存在负环（SPFA无法处理带负环的图）
1 #include 2 #include 3 const int N=100500; 4 const int M=200500; 5 int point[N]={0},to[M]={0},next[M]={0},len[M]={0},cc=0; 6 int dis[N];//最短路长度 7 int queue[N],top,tail;//双向队列queue，队头，队尾8 bool in[N];//记录这个点在不在队列中，1表示在，0表示不在9 int n,m; //n个节点，m条边 10 void AddEdge(int x,int y,int z)//x到y边长为z 11 {12cc++;13next[cc]=point[x];14point[x]=cc;15to[cc]=y;16len[cc]=z;17 }18 int main()19 {20int i,j;21scanf("%d%d",&n,&m);22for(i=1;i<=m;i++)23{24int a,b,c;25scanf("%d%d%d",&a,&b,&c);26AddEdge(a,b,c);//因为是双向队列，左边加一次，右边加一次27AddEdge(b,a,c);28}29memset(dis,0x3f,sizeof dis);//用极大值来初始化30dis[1]=0;//1号节点到自己最短距离为0 31top=0;tail=1;queue[1]=1;in[1]=1;//初始化，只有原点加入 32while(top!=tail)33{34top++;35top%=N;36int now=queue[top];37in[now]=0;38int ed=point[now];39while(ed)40{41int tox=to[ed];42if(dis[tox]>dis[now]+len[ed])43{44dis[tox]=dis[now]+len[ed];45if(!in[tox])46{47tail++;48tail%=N;49queue[tail]=tox;50in[tox]=1;51}52}53ed=next[ed];54}55}56for(i=1;i<=n;i++)57printf("%d\n",dis[i]);58return 0; 59 }
4. Ford算法（有负权边，可能有负圈，能检测负圈并输出）：
单源最短路！
算法描述：
1.初始化：将除源点外的所有顶点的最短距离估计值 d[all]=+∞, d[start]=0;
2.迭代求解：反复对边集E中的每条边进行松弛操作，使得顶点集V中的每个顶点v的最短距离估计值逐步逼近其最短距离；（运行|v|-1次）
3.检验负权回路：判断边集E中的每一条边的两个端点是否收敛。如果存在未收敛的顶点，则算法返回false，表明问题无解；否则算法返回true，并且从源点可达的顶点v的最短距离保存在 d[v]中。
简单的说，如下图所示：

文章插图
松弛计算之前，点B的值是8，但是点A的值加上边上的权重2，得到5，比点B的值（8）小，所以，点B的值减小为5 。这个过程的意义是，找到了一条通向B点更短的路线，且该路线是先经过点A，然后通过权重为2的边，到达点B
如果出现了以下情况：

文章插图
松弛操作后，变为7,7>6，这样就不修改（ Frod算法的高妙之处就在这），保留原来的最短路径就OK，代码实现起来非常简单。
1 int n,m;//n个点，m条边2 struct Edge//定义图类型结构体3 { 4int a,b,c;//a到b长度为c5 }edge[]; 6 int dis[]; 7 memset(dis,0x3f,sizeof dis); 8 dis[1]=0; 9 for(int i=1;idis[edge[j].a]+edge[j].c)14{15dis[edge[j].b]=dis[edge[j].a]+edge[j].c;16}17}18 }
5.A*算法：
这玩意儿我是没看懂，等以后我看懂了再更吧（无奈脸）~
七、拓扑排序：
对一个有向无环图(Graph简称DAG)G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若边(u,v)∈E(G)，则u在线性序列中出现在v之前。通常，这样的线性序列称为满足拓扑次序( Order)的序列，简称拓扑序列。
打个比喻：我们要做好一盘菜名字叫做红烧茄子，那么第一步得买茄子和配料，第二步就是要洗茄子，第三步就是要开始倒油进锅里啊什么七七八八的，第四步…，你不可能先洗茄子再买茄子和配料，这样的一些事件必须是按照顺序进行的，这些依次进行的事件就构成了一个拓扑序列。
算法描述：
我们需要一个栈或者队列，两者都可以无所谓，只是找个容器把入度为0的元素维护起来而已。
①从有向图中选择一个入度为0（无前驱）的顶点，输出它。