图论的基本算法

图论基本算法长沙市雅礼中学朱全民图图的概念

G=(V,E)图的基本概念有向图、顶点、入度、出度、弧、环无向图、边、路径、顶点的度、邻接简单图、完全图平面图、二分图过河一摆渡人欲将一只狼,一头羊,一篮菜从河西渡过河到河东.由于船小,一次只能带一物过河，并且狼与羊,羊与菜不能独处.给出渡河方法.

解：用四维0-1向量表示(人,狼,羊,菜)在河西岸的状态(在河西岸则分量取1,否则取0),共有24=16种状态.在河东岸的状态类似记作.

由题设,状态(0,1,1,0),(0,0,1,1),(0,1,1,1)是不允许的,从而对应状态(1,0,0,1),(1,1,0,0),(1,0,0,0)也是不允许的.

以可允许的10个状态向量作为顶点,将可能互相转移的状态用线段连接起来构成一个图.

根据此图便可找到渡河方法.(1,1,1,1)

(1,1,1,0)

(1,1,0,1)

(1,0,1,1)

(1,0,1,0)(0,0,0,0)

(0,0,0,1)

(0,0,1,0)

(0,1,0,0)

(0,1,0,1)(0,1,0,1)

(0,1,0,0)

(0,0,1,0)

(0,0,0,1)

(0,0,0,0)(1,0,1,0)

(1,0,1,1)

(1,1,0,1)

(1,1,1,0)

(1,1,1,1)河西=(人,狼,羊,菜)河东=(人,狼,羊,菜)将10个顶点分别记为A1,A2,…,A10,则渡河问题化为在该图中求一条从A1到A10的路.从图中易得到两条路：A1A6A3A7A2A8A5A10;A1A6A3A9A4A8A5A10.图的矩阵表示

权矩阵

无向图G的权矩阵A是一个对称矩阵.

关联矩阵若vi是ej的始点;若vi是ej的终点;若vi与ej不关联.

有向图的关联矩阵每列的元素中有且仅有一个1,有且仅有一个

-

1.邻接表表节点

typearcptr=^arcnode;arcnode=recordadjvex:vtxptr;nextarc:arcptr;info:…{和弧有关的其他信息}end;vex=Recordvexdata:…{和顶点有关的其他信息}firstarc:arcptr;end;adjlist=array[vtxptr]ofvexnode;邻接表123456234^135^136^236^345^12456^拓扑排序

按照有向图给出的次序关系，将图中顶点排成一个线性序列，对于有向图中没有限定次序关系的顶点，则可以人为加上任意的次序关系。由此所得顶点的线性序列称之为拓扑有序序列例如：对于有向图BDAC可求得拓扑有序序列：

ABCD或ACBDBDAC对于下列有向图不能求得它的拓扑有序序列。因为图中存在一个回路

{B,C,D}FUNCtoporder(vardig:adjlisttp):boolean;init(top2);m:=0;ve[1..n]:=0whileNotempty(top1)do[j:=pop(top1);push(top2,j);m:=m+1;k:=firstadj(dig,j);whilek<>0do[入度(k):=入度(k)-1;if入度(k)=0thenpush(top1,k);ifve[j]+dut(<j,k>)>ve[k]thenve[k]:=ve[j]+dut(<j,k>);k:=nextadj(dig,j,k)]]ifm<nthenreturn(false)elsereturn(true);endF;求拓扑序列拓扑排序核心问题：给一些序关系，排出全序！一个一个排先排最大然后第二大…具体实现？每次取0出度点枚举所有点吗？0出度只可能是1出度变来的！O(n+m)神经网络

在兰兰的模型中，神经网络就是一张有向图，图中的节点称为神经元，而且两个神经元之间至多有一条边相连，下图是一个神经元的例子：

图中，X1—X3是信息输入渠道，Y1－Y2是信息输出渠道，C1表示神经元目前的状态，Ui是阈值，可视为神经元的一个内在参数。神经元按一定的顺序排列，构成整个神经网络。在兰兰的模型之中，神经网络中的神经无分为几层；称为输入层、输出层，和若干个中间层。每层神经元只向下一层的神经元输出信息，只从上一层神经元接受信息。

神经网络兰兰规定，Ci服从公式：（其中n是网络中所有神经元的数目）

公式中的Wji（可能为负值）表示连接j号神经元和i号神经元的边的权值。当Ci大于0时，该神经元处于兴奋状态，否则就处于平静状态。当神经元处于兴奋状态时，下一秒它会向其他神经元传送信号，信号的强度为Ci。如此．在输入层神经元被激发之后，整个网络系统就在信息传输的推动下进行运作。现在，给定一个神经网络，及当前输入层神经元的状态（Ci），要求你的程序运算出最后网络输出层的状态。

【输入格式】

第一行是两个整数n（1≤n≤20）和p。接下来n行，每行两个整数，第i＋1行是神经元i最初状态和其阈值（Ui），非输入层的神经元开始时状态必然为0。再下面P行，每行由两个整数i，j及一个整数Wij，表示连接神经元i、j的边权值为Wij。【输出格式】

输出包含若干行，每行有两个整数，分别对应一个神经元的编号，及其最后的状态，两个整数间以空格分隔。仅输出最后状态非零的输出层神经元状态，并且按照编号由小到大顺序输出！若输出层的神经元最后状态均为0，则输出NULL。分析

理解问题的第一步就是认真“读题”。那么我们先来看一看这个题目涉及的问题。研究一下题目中所给的图的一些性质，可以发现如下特点：1．图中所有的节点都有一个确定的等级，我们记作Level(i)2．图中所有的边都是有向的，并且从Level值为i-1的节点指向Level值为i的节点我们不妨将其抽象为“阶段图”。更一般地，我们可以发现所有的阶段图都是有向无环的，这样我们可以通过拓扑排序来得到期望的处理节点的顺序。可行算法

由于阶段图的性质使得该图的所有边所连接节点的等级都是相邻的，因此就可以设计出一个基于宽度优先搜索的算法：1．初始时将所有输入层的节点放入队列；2．取出队列中的一个元素，不重复地扩展并处理该节点所发出的边的目标节点；3．如果队列非空，则转向2；4．输出输出层中所有满足条件的节点。但是由于本题在问题描述中并没有明确的给出判断一个节点是否是输入节点，因此需要在算法进行的过程当中额外地考虑一些边界情况的数据（这个过程即便是真实数据没有这样出也是要有的），下面给出的更一般的算法可能会更好的跳过这些边界情况。1．对原图中所有的节点进行一次拓扑排序；2．按照拓扑顺序处理每一个节点；3．输出输出层中所有满足条件的节点。欧拉道路和回路经过每条边一次且仅一次先看回路必要条件：所有点度为偶数充分条件：还是“所有点度为偶数”证明！把欧拉回路构造出来“圈套圈”可能套不出来吗？想一想欧拉道路和回路有向的情形入度=出度如何套圈？道路有两个奇度点正好是起点和终点哪个是起点，哪个是终点？有向+无向怎么办？网络流！不要求掌握幼儿园的粉刷幼儿园里有很多房屋房屋与房屋之间连以走廊走廊与房屋之间有一扇门幼儿园长想把门漆成绿色或者黄色，使得任意一条走廊两头门的颜色不同任意一间房屋上的门，绿色门的数量与黄色门的数量相差不超过1。如何实现？每个房屋的门都是偶数个…把奇数改造成偶数！另一个例子考古学家发现了一块布，布上做有针线活，叫做“十字绣”交替地在布的两面穿线布是一个n×m的网格线只能在网格的顶点处才能从布的一面穿到另一面。每一段线都覆盖一个单位网格的两条对角线之一而在绣的过程中，一针中连续的两段线必须分处布的两面给出布两面的图案（实线代表有线，虚线代表背面有线）最少需要几针才能绣出来？一针是指针不离开布的一次绣花过程。例如图(b)的图案最少需要4针。

分析抽象成图正面的线：正边背面的线：负边有边相连：连通块每个连通块分别求对于某个顶点I|正边数-负边数|=K>0时以该顶点为开始或结束的针数>=K可以恰好为K针所有K值加起来，除以2（每一针有两个端点）最小生成树问题求一个连通子图，使得边权和最小Prim算法任意时刻的中间结果都是一棵树从一个点开始每次都花最小的代价，用一条加进一个新点问题：这样做是对的吗？如何快速找到这个“最小代价”？Prim算法的正确性换一种说法如果存在一个MST，包含当前所有边则也存在一个MST,它包含最小代价边(u,v)反证法！假设存在这样的MST当前结点集为S，剩下的结点集为T由于在MST中S-T连通一定有跨越S-T的某边(u’,v’)它不是最小代价边(u,v)删除(u’,v’)，加入(u,v)，S和T分别连通，且S-T通过(u,v)连通得到了一个更小的MST！快速找到最小代价需要借助数据结构！我们的算法要求快速取/删除最小值（边权）允许插入边（加入新点时插入它的关接边）抽象数据类型：优先队列！经典实现：堆！Prim算法框架初始化，树仅含一个任意一点v0把v0的邻边插入堆fori:=1ton-1dobegin

从堆中取出最小值，设边为(u’,v’)，v’为新点

(u’,v’)加入生成树中

v’和它所有不在树中的邻居组成的边插入堆end;每次取最小值为O(logm)总时间复杂度为O(nlogm)Kruskal算法任意时刻的中间结果是一个森林从n个点的集合开始每次选不产生圈的前提下权最小的边加入问题：这样做是对的吗？如何快速的判断是否产生圈Kruskal算法的正确性把一个二元组(E,I)叫做一个子集系统，如果满足：1．E是一个非空集合2．I是E的一个子集族，它在包含运算下封闭，即I的每个元素a都是E的一个子集，并对于a的任何子集a’，a’一定也是I的元素。3．给E中每个元素e赋予一个正权w(e)。考虑至少有一条边的带权无向连通图G它的边集为E它的所有生成森林的集合为I则(E,I)是一个子集系统，称为生成森林子集系统E非空，所以满足条件1生成森林是E的一个边集，而且其生成子图仍是生成森林，满足2G是带权的，所以满足3。

子集优化问题极大独立集把I中的元素都称为独立集对于I中的元素a，如果不存在I中的另一个元素a’使得a是a’的真子集，则称a是极大独立集。该极大独立集的基数为它包含的元素个数在刚才介绍的子集系统中，G的所有生成树就是所有的极大独立集。所有极大独立集具有相同的基数|V|-1。其中|V|为G的顶点数。子集优化问题在子集系统(E,I)中选取一个元素S∈I，使得w(S)最大（定义w(S)为S中所有元素的权和）子集优化问题的贪心算法贪心算法先把E中元素按照权值从大到小排序为e1,e2,…令集合S=空集然后每次尝试着把e1,e2,…，添加到S里面如果添加之后S仍是独立集，则添加成功如果S不是独立集，则由定义知以后无论怎样继续添加元素，得到的集合都不可能重新成为独立集，因此撤消此添加操作。Kruskal算法是生成森林子集系统的贪心算法！贪心算法在什么子集系统下是的对的呢？定理贪心算法正确，当且仅当这个系统的极大独立集具有相同的基数满足条件的子集系统称为“矩阵胚(matroid)”快速判断是否产生圈需要借助数据结构！我们的算法要求判断两个点是否在同一棵树中产生圈当且仅当此边连接同一树中的点！快速把两棵树合并加边意味着两棵树合为一棵抽象数据类型：并查集！经典实现：森林并查集的森林实现森林中的每棵树表示不同的集合树的形态并不重要，有意义的只是“哪些元素在树中”并查集的操作查找用树根作为集合的标识不断的找父亲，最终将找到树根要找多少次父亲？和树的高度有关！怎样减少树的高度？找到树根后沿途把路径上的结点的父亲设为根专门名称：路径压缩两元素所在的树根相同，则二者属于同一集合合并其中一棵树成为另一棵树树根的子树谁成为谁的子树？注意树的高度！启发式合并时间复杂度：几乎都为常数！并查集的实现回忆刚才用到了什么信息？查找：“不断的找父亲”…“沿途设置结点的父亲为树根”合并：“把一棵树的父亲设置为另一棵树的树根”只有“父亲”信息！父亲表示法！father:array[1..maxn]ofinteger;根结点root满足father[root]:=root查找：whilefather[p]<>pdop:=father[p];……?合并：ifheight(p1)<height(p2)thenfather[p1]:=p2Kruskal算法框架把所有边按照权值从小到大排序为e1,e2,…初始化n个集合，Si={i}size:=0;fori:=1tomdoifei的两个端点u,v不在同一个集合thenbegin

合并Su和Svinc(size);ifsize=n–1thenbreak;end;最坏情况循环执行m次，判断约O(1)如果输入已经排序好，则总时间复杂度为O(m)，否则为O(mlogm)最短路问题问题描述：给加权图GSSSP：求给定起点s到其他所有点的最短路APSP：求每两对点的最短路算法标号设定类：dijkstra标号修正类：bellman-ford动态规划类：floyd-warshall变形与应用举例SSSP(Dijkstra算法)核心思想：按路径递增的次序产生最短路径的算法

1)找到图中最短的路径，设为（v,vj）,将j设为已标号的点

2)找下一条次短的路径，假设终点为k,将k设为已标号的点,那么要么是（v,vk）要么是（v,vj,vk）,若经过vj,将j设为已检查的点,放入集合.3)以次短路径出发找第三短的路径,类似第二步的方法.4)按上述方法一直到所有的顶点被检查过,则从v到其他顶点的最短路径求出.Dijkstra算法令d’(u)=min{d[v]+w(v,u)|v存在}，设中最小的元素为i，则令（即求出了i的最短路长度），并根据d[i]来对进行更新。每次求出一个d值，重复n次就可以得到所有点的最短路径长度。下面是Dijkstra算法的伪代码：ProcSSSP_Dijkstra(start:integer);Fori:=1tondod’(i):=∞;d’(start):=0;Fork:=1TonDo【i:=GetMin(ProcSSSP_Dijkstra(start:integer);Fori:=1tondod’(i):=∞;d’(start):=0;Fork:=1TonDo【i:=GetMin();{取出d’中值最小的结点i}d[i]:=d’(i);Delete(i,d’);{令d[i]等于d’(i)，并将i从d’中删除}Foreachnodeuexistedge(i,u)【{对每条从i连出的边进行检查}Ifd’(u)<d[i]+w(i,u)Thend’(u):=d[i]+w(i,u);】{根据d[i]对d’(u)进行更新}】End;Dijkstra算法适用条件:所有边的权值非负定理2每当结点u插入集合S时，有d[u]=w(s,u)成立。效率:用一维数组来实现优先队列Q，O(V2)，适用于中等规模的稠密图二叉堆来实现优先队列Q，O((E+V)logV)，适用于稀疏图用Fibonacci堆来实现优先队列Q的话，O(VlogV)，可惜编程复杂度过高，理论价值远大于实用价值Bellman-Ford算法Bellman-Ford算法流程分为三个阶段：(1)初始化：将除源点外的所有顶点的最短距离估计值

d[v]←+∞,d[s]←0;(2)迭代求解：反复对边集E中的每条边进行松弛操作，使得顶点集V中的每个顶点的最短距离估计值逐步逼近其最短距离；（运行|v|-1次）(3)检验负权回路：判断边集E中的每一条边的两个端点是否收敛。如果存在未收敛的顶点，则算法返回false，表明问题无解；否则算法返回true，并且从源点可达的顶点v的最短距离保存在

d[v]中。Bellman-Ford算法Bellman-Ford算法运用了松弛技术，对每一结点v∈V，逐步减小从源s到v的最短路径的估计值d[v]直至其达到实际最短路径的权w(s,v)，如果图中存在负权回路，算法将会报告最短路不存在。Bellman-Ford(G,w,s)：boolean//图G，边集函数

w，s为源点

foreachvertexv∈V（G）

do//初始化

1阶段

d[v]←+∞

d[s]←0;//1阶段结束

fori=1to|v|-1do//2阶段开始，双重循环。

foreachedge（u,v）∈E(G)do//边集数组要用到，穷举每条边。

Ifd[v]>d[u]+w(u,v)then//松弛判断

d[v]=d[u]+w(u,v)//松弛操作

2阶段结束

foreachedge（u,v）∈E(G)do

Ifd[v]>d[u]+w(u,v)then

Exitfalse

ExittrueBellman-Ford算法适用条件:任意边权为实数的图Bellman-Ford算法的思想基于以下事实：“两点间如果有最短路，那么每个结点最多经过一次。也就是说，这条路不超过n-1条边。”（如果一个结点经过了两次，那么我们走了一个圈。如果这个圈的权为正，显然不划算；如果是负圈，那么最短路不存在；如果是零圈，去掉不影响最优值）Bellman-Ford算法的运行时间为O(VE)。很多时候，我们的算法并不需要运行|V|-1次就能得到最优值。对于一次完整的第3-4行操作，要是一个结点的最短路径估计值也没能更新，就可以退出了。经过优化后，对于多数情况而言，程序的实际运行效率将远离O(VE)而变为O(kE)，其中k是一个比|V|小很多的数。SPFA(ShortestPathFasterAlgorithm)SPFA对Bellman-Ford算法优化的关键之处在于意识到：只有那些在前一遍松弛中改变了距离估计值的点，才可能引起他们的邻接点的距离估计值的改变。因此，用一个先进先出的队列来存放被成功松弛的顶点。初始时，源点s入队。当队列不为空时，取出对首顶点，对它的邻接点进行松弛。如果某个邻接点松弛成功，且该邻接点不在队列中，则将其入队。经过有限次的松弛操作后，队列将为空，算法结束。SPFA算法的实现，需要用到一个先进先出的队列

queue和一个指示顶点是否在队列中的标记数组

mark。定理4在平均情况下，SPFA算法的期望时间复杂度为O(E)。证明：上述算法每次取出队首结点u，并访问u的所有临结点的复杂度为O(d)，其中d为点u的出度。运用均摊分析的思想，对于|V|个点|E|条边的图，点的平均出度为E/V，所以每处理一个点的复杂度为O(E/V)。假设结点入队次数为h，显然h随图的不同而不同。但它仅与边权值分布有关。我们设h=kV，则算法SPFA的时间复杂度为在平均的情况下，可以将k看成一个比较小的常数，所以SPFA算法在一般情况下的时间复杂度为O(E)。（证毕）SPFA算法适用条件任意边权为实数的图定理3只要最短路径存在，上述SPFA算法必定能求出最小值。证明：每次将点放入队尾，都是经过松弛操作达到的。换言之，每次的优化将会有某个点v的最短路径估计值d[v]变小。所以算法的执行会使d越来越小。由于我们假定图中不存在负权回路，所以每个结点都有最短路径值。因此，算法不会无限执行下去，随着d值的逐渐变小，直到到达最短路径值时，算法结束，这时的最短路径估计值就是对应结点的最短路径值。（证毕）SPFA算法

设立一个先进先出的队列用来保存待优化的结点，优化时每次取出队首结点u，并且用u点当前的最短路径估计值对离开u点所指向的结点v进行松弛操作，如果v点的最短路径估计值有所调整，且v点不在当前的队列中，就将v点放入队尾。这样不断从队列中取出结点来进行松弛操作，直至队列空为止。SPFA(G,w,s)1.INITIALIZE-SINGLE-SOURCE(G,s)2.INITIALIZE-QUEUE(Q)3.ENQUEUE(Q,s)4.WhileNotEMPTY(Q)5.Dou←DLQUEUE(Q)6.For每条边(u,v)E[G]7.Dotmp←d[v]8.Relax(u,v,w)9.If(d[v]<tmp)and(v不在Q中)10.ENQUEUE(Q,v)

我们用数组d记录每个结点的最短路径估计值，而且用邻接表来存储图G。我们采取的方法是动态逼近法：Car的旅行路线又到暑假了，住在城市A的Car想和朋友一起去城市B旅游。她知道每个城市都有四个飞机场，分别位于一个矩形的四个顶点上，同一个城市中两个机场之间有一条笔直的高速铁路，第i个城市中高速铁路的单位里程价格为Ti，任意两个不同城市的机场之间均有航线，所有航线单位里程的价格均为t。那么Car应如何安排到城市B的路线才能尽可能的节省花费昵？她发现这并不是一个简单的问题，于是她来向你请教。约束条件输入第一行为一个正整数n(0≤n≤10)，表示有n组测试数据。 每组的第一行有四个正整数s，t，A，B。s（0＜S≤100）表示城市的个数，t表示飞机单位里程的价格，A，B分别为城市A，B的序号，（1≤A，B≤S）。 接下来有s行，其中第i行均有7个正整数xi1，yi1，xi2，yi2，xi3，yi3，Ti，这当中的(xi1，yi1­)，(xi2，yi2)，(xi3，yi3)分别是第I个城市中任意三个机场的坐标，Ti为第i个城市高速铁路单位里程的价格。输出 共有n行，每行一个数据对应测试数据。分析1、计算两点间的欧氏距离2、计算每个机场的坐标序列3、使用Dijkstra算法计算最小费用SSSP：权非负的情形求1到所有点的距离d[1]=0d[2]<=3,d[4]<=4d[2]=3.为什么？每次固定d的最小值标号设定！怎样取最小值？堆！名称：dijkstra和Prim算法很类似Prim:边最小值dijkstra:d最小值中间结果：最短路树！时间复杂度O((m+n)logm)一个例子给出一个带权无向图G边权为1…1000的整数对于v0到v1的任意一条简单路p定义s(p)为p上所有边权的最大公约数考虑v0到v1的所有路p1,p2,…求所有s(p1),s(p2),…的最小公倍数模型？最短路？路径长度定义不再是权和，而是…dijkstra算法还能用吗？SSSP：权任意的情形最短路有可能不存在！什么时候不存在？有负圈！标号设定标号修正仍然有标号d[i]<=k但是标号d[i]无法固定，只能不断更新新算法如有最短路，则每个顶点最多经过一次即：这条路不超过n-1条边迭代！依次考虑1,2,3…n-1条边的情形SSSP：bellman-ford算法依次考虑边长度不超过1,2…n-1的路考虑长度不超过1,2,3…k-1的路后，标号为d[]长度为k的路可以由不超过1,2,…k-1的路增加一条边得到：fork:=1ton-1dofor每条边(u,v)doif(d[u]<∞)and(d[v]>d[u]+w(u,v))thend[v]:=d[u]+w(u,v)核心：标号修正过程（松弛操作）时间复杂度：O(nm)改进的终止条件：d都不改变加速：用dijkstra得到初始d[]APSP:基本分析设d[i，j，k]是在只允许经过结点[1…k]的情况下i到j的最短路长度则它有两种情况（想一想，为什么）：如果最短路经过点k，那么d[i，j，k]应该等于d[i，k，k-1]+d[k，j，k-1]；如果最短路不经过点k，那么d[i，j，k]应该等于d[i，j，k-1]。综合起来d[i，j，k]=min{d[i，k，k-1]+d[k，j，k-1]，d[i，j，k-1]}边界条件是d[i，j，0]=w(i，j)（不存在的边权为∞）floyd-warshall算法基本的动态规划把k放外层循环，可以节省内存对于每个k，计算每两点的目前最短路fork:=1tondofori:=1tondoforj:=1tondoif(d[i,k]<∞)and(d[k,j]<∞)and(d[i,k]+d[k,j]<d[i,j])thend[i,j]:=d[i,k]+d[k,j]一定要背下来！时间复杂度：O(n3)用途：预处理！选址问题--中心问题某城市要建立一个消防站，为该市所属的七个区服务，如图所示．问应设在那个区，才能使它至最远区的路径最短．解析求出距离矩阵D=．

关键工程在大型工程的施工前，我们把整个工程划分为若干个子工程，并把这些子工程编号为1、2、……、N；这样划分之后，子工程之间就会有一些依赖关系，即一些子工程必须在某些子工程完成之后才能施工。由于子工程之间有相互依赖关系，因此有两个任务需要我们去完成：首先，我们需要计算整个工程最少的完成时间；同时，由于一些不可预测的客观因素会使某些子工程延期，因此我们必须知道哪些子工程的延期会影响整个工程的延期，我们把有这种特征的子工程称为关键子工程，因此第二个任务就是找出所有的关键子工程，以便集中精力管理好这些子工程，尽量避免这些子工程延期，达到用最快的速度完成整个工程。为了便于编程，现在我们假设：（1）根据预算，每一个子工程都有一个完成时间。（2）子工程之间的依赖关系是：部分子工程必须在一些子工程完成之后才开工。（3）只要满足子工程间的依赖关系，在任何时刻可以有任何多个子工程同时在施工，也既同时施工的子工程个数不受限制。（4）整个工程的完成是指：所有子工程的完成。示例1序号完成时间子工程1子工程2子工程3子工程4子工程5子工程150000子工程240000子工程3120000子工程471100子工程521111约束条件输入：第1行为N，N是子工程的总个