图论算法与模型构建

湖南省长沙市第一中学曹利国图论算法与模型构建总览图的基本概念与存储结构图的遍历和染色性图的连通性问题路径问题

拓扑排序流量问题匹配问题

图论中的“图”并不是通常意义下的几何图形或物体的形状图,而是以一种抽象的形式来表达一些确定的事物之间的联系的一个数学系统.

定义1一个有序二元组(V,E)称为一个图,记为G=(V,E),其中

①V称为G的顶点集,V≠,其元素称为顶点或结点,简称点;②

E称为G的边集,其元素称为边,它联结V中的两个点,如果这两个点是无序的,则称该边为无向边,否则,称为有向边.

如果V={v1,v2,…,vn}是有限非空点集,则称G为有限图或n阶图.Sec.1图的基本概念与存储结构

如果E的每一条边都是无向边,则称G为无向图(如图1);

如果E的每一条边都是有向边,则称G为有向图(如图2);

否则,称G为混合图.图1图2并且常记V={v1,v2,…,vn},|V|

=n

;E={e1,e2,…,em}(ek=vivj

),|E|

=m.称点vi,vj为边vivj的端点.在有向图中,称点vi,vj分别为边vivj的始点和终点.

有边联结的两个点称为相邻的点,有一个公共端点的边称为相邻边.边和它的端点称为互相关联.常用d(v)表示图G中与顶点v关联的边的数目,

d(v)称为顶点v的度数.用N(v)表示图G中所有与顶点v相邻的顶点的集合.d(v1)=d(v3)=d(v4)=4,d(v2)=2.我们今后只讨论有限简单图：(1)顶点个数是有限的;(2)任意一条边有且只有两个不同的点与它相互关联;(3)若是无向图,则任意两个顶点最多只有一条边与之相联结;(4)若是有向图,则任意两个顶点最多只有两条边与之相联结.当两个顶点有两条边与之相联结时，这两条边的方向相反.

如果某个有限图不满足(2)(3)(4),可在某条边上增设顶点使之满足.

定义2若将图G的每一条边e都对应一个实数F(e),则称F(e)为该边的权,并称图G为赋权图(网络),记为G=(V,E,F).

定义3设G=(V,E)是一个图,v0,v1,…,vk∈V,且1≤i≤k,vi-1vi∈E,则称v0v1…vk是G的一条通路.如果通路中没有相同的边,则称此通路为道路.始点和终点相同的道路称为圈或回路.

如果通路中既没有相同的边,又没有相同的顶点,则称此通路为路径,简称路.

定义4任意两点均有通路的图称为连通图.

定义5连通而无圈的图称为树,常用T表示树.图的储存结构矩阵邻接表邻接多重表十字链表无向图邻接5|4|3|/2|2|2|3|1|2|4|/5|/4|/5|/邻接链表每一个顶点有一个所有与之相邻的链表每一条边2个（对无向图）要在两个顶点的链表中都加入空间复杂度O(|E|)

对稀疏图这种方式比较好邻接表Pascal语言const

maxv=10000;typeTnode=record//定义顶点类型

c:integer;//顶点编号

next:^Tnode;//此点的邻接链表end;Var//数组g表示每个顶点的邻接链表//的链表头---哨兵g:array[1..maxv]ofTnode;

n,m,i,a,b:integer;

t:^Tnode;C++语言#include<iostream>usingnamespacestd;constint

maxv=10000;struct

Tnode{//定义顶点类型

intc;//顶点编号

Tnode*next;//此点的邻接链表};//数组g表示每个顶点的邻接链表//的链表头---哨兵

Tnode

g[maxv];

int

n,m,i,a,b;

Tnode*t;图G有n个顶点，编号从1到n。有m条有向边，输入时每行两个整数ab，表示边为从顶点a连接到顶点b。下面程序用指针实现图的邻接链表。Pascal语言procedureins(x:integer;var

p:Tnode);Begin//插入链表子过程

new(t);t^.c:=x;

t^.next:=p.next;

p.next:=t;end;begin

readln(n,m);

//初始化邻接链表“哨兵”

fori:=1tondo

g[i].next:=nil;

//读入边，插入邻接链表

fori:=1tomdobegin

readln(a,b);

ins(b,g[a]);{ins(a,g[b]);//无向边时再加入}end;//...C++语言voidins(intx,Tnode&p){//插入链表子过程t=new(Tnode);t->c=x;t->next=p.next;

p.next=t;}intmain(){

cin>>n>>m;

//初始化邻接链表“哨兵”

for(i=1;i<=n;i++)

g[i].next=NULL;

for(i=0;i<m;i++){//读入边，插入邻接链表

cin>>a>>b;

ins(b,g[a]);

//ins(a,g[b]);//无向边时

}//…邻接表的实现A（指针）Pascal语言constmaxV=1000;//最多顶点数

maxE=10000;//最多边数typeTnode=record//定义顶点类型

c:integer;//节点编号

next:integer;//此节点的邻接链表end;vare:array[1..maxE]ofTnode;g:array[1..maxV]ofTnode;

n,m,efree,i,a,b,t:integer;procedureins(x:integer;var

p:Tnode);begin//取一个空元素插入链表p后

e[efree].c:=x;e[efree].next:=p.next;

p.next:=efree;

efree:=efree+1;//新空元素下标end;C++语言constint

maxV=1000,//最多顶点数

maxE=10000;//最多边数struct

Tnode{//定义顶点类型

intc;//顶点编号

intnext;//此点的邻接链表};//数组g表示每个顶点的邻接链表//的链表头---哨兵

Tnode

g[maxV],e[maxE];

intn,m,i,a,b,efree,t;voidins(intx,Tnode&p){//取一个空元素插入链表p后

e[efree].c=x;

e[efree].next=p.next;

p.next=efree;

efree++;//新空元素下标}邻接表的实现B（数组）Pascal语言

begin

readln(n,m);

//初始化邻接链表“哨兵”

fori:=1tondo

g[i].next:=-1;

efree:=1;

//读入边，插入邻接链表

fori:=1tomdobegin

readln(a,b);

ins(b,g[a]);

{ins(a,g[b]);//无向边时}end;...C++语言

intmain(){

cin>>n>>m;efree=0;

//初始化邻接链表“哨兵”

for(i=1;i<=n;i++)

g[i].next=-1;

//读入边，插入邻接链表

for(i=0;i<m;i++){

cin>>a>>b;

ins(b,g[a]);

//ins(a,g[b]);//无向边时

}…邻接表的实现B（数组）带权图的邻接表存储方法TypeLink=^Node;Node=Recordv,w:Longint;{顶点和费用}Next:Link;End;Map:Array[1..Maxn]ofLink;{用邻接表记录的图}

Read(n,m);Fori:=1tomdoBegin

Read(a,b,c);

New(p);

p^.v:=b;p^.w:=c;

p^.Next:=Map[a];

Map[a]:=p;End;Sec.2图的遍历和染色性图的遍历和染色性是解决一切图论问题的根基，例如判断图的联通性，判断图是否有环，判断图是否为二分图，等等一些基本问题都要通过图的遍历和染色来进行。这一步骤虽然很不起眼，但是在编程解题过程中往往都是一些最基本的步骤，整个问题的求解往往都是由它开始的。图的遍历

从图中某一顶点出发，按某种搜索方法访遍其余顶点，且使每一顶点仅被访问一次。这一过程称为图的遍历。遍历图的基本搜索方法有两种：深度优先搜索DFS和广度优先搜索BFS。这两种方法都适用于有向图和无向图。图的深度优先搜索遍历

图的深度优先遍历DFS算法是每次在访问完当前顶点后，首先访问当前顶点的一个未被访问过的邻接顶点，然后去访问这个邻接点的一个未被访问过的邻接点，这样的算法是一个递归算法。

连通图的深度优先遍历算法思想。（1）访问初始顶点v并标记顶点v已访问。（2）查找顶点v的第一个邻接顶点w。（3）若顶点v的邻接顶点w存在，则继续执行；否则回溯到v，再找v的另外一个未访问过的邻接点。（4）若顶点w尚未被访问，则访问顶点w并标记顶点w为已访问。（5）继续查找顶点w的下一个邻接顶点wi，如果v取值wi转到步骤（3）。直到连通图中所有顶点全部访问过为止。深度优先遍历的程序实现：（邻接表、Pascal）//图的一般结构

typegraph_node=record…end;typeAdjList=recordid:integer;next:^AdjList;end;

var

n_nodes,S_i:integer;nodes:array[1..maxN]ofgraph_node;visited:array[1..maxN]ofinteger;adj:array[1..maxN]of^AdjList;标识项点有没有访问过每个顶点都有邻接链表邻接链表的节点数据结构深度优先遍历的程序实现：（邻接表、Pascal）置每个点标识为“未访问”从所有未被访问的点k出发，调用DFS(k)proceduresearch();begink:integer;fork:=1ton_nodesdovisited[k]:=0;

fork:=1ton_nodesdoifvisited[k]<>0thenDFS(k);end;置被访问节点的“时间”---次序访问k的所有相邻的节点

procedureDFS(k:integer);begin

//从k出发搜索

var

j:^AdjList;begininc(S_i);visited[k]:=S_i;j:=adj[k];while(j<>NULL)dobeginifvisited[j^.id]<>0thenDFS(j^.id);j:=j^.next;end;end;图的广度优先搜索遍历

图的广度优先遍历BFS算法是一个分层搜索的过程，和树的层序遍历算法类同，它也需要一个队列以保持遍历过的顶点顺序，以便按出队的顺序再去访问这些顶点的邻接顶点。

连通图的广度优先遍历算法思想。

（1）顶点v入队列。

（2）当队列非空时则继续执行，否则算法结束。

（3）出队列取得队头顶点v；访问顶点v并标记顶点v已被访问。

（4）查找顶点v的第一个邻接顶点col。

（5）若v的邻接顶点col未被访问过的，则col入队列。

（6）继续查找顶点v的另一个新的邻接顶点col，转到步骤（5）。直到顶点v的所有未被访问过的邻接点处理完。转到步骤（2）。广度优先遍历的程序实现：（邻接表、C++）//图的一般结构

struct

graph_node{…};

struct

AdjList{

intid;

AdjList*next;};

int

n_nodes,S_index=0;

graph_nodenodes[maxN];

intvisited[maxN];

AdjList*adj[maxN];标识项点有没有访问过每个顶点都有邻接链表邻接链表的节点数据结构广度优先遍历的程序实现:（邻接表、C++）置每个点标识为“未访问”从所有未被访问的点k出发，调用BFS(k)voidsearch(){

intk;

for(k=0;k<n_nodes;k++)visited[k]=0;

for(k=0;k<n_nodes;k++)if(!visited[k])BFS(k);}宽度优先遍历的程序实现：（邻接表、C++）intq[maxN];voidBFS(intk){

int

front,back;q[0]=k;front=back=0;

for(;fron<=back;fron++){k=q[front];

visited[k]=++search_index;

for(Adjlist*j=adj[k];j!=NULL;j=j->next){if(!visited[j->id]){

q[++back]=j->id;

visited[j->id]=++S_index;}}}}BFS用的队列，一般全局Front<=back,队列不空访问k的所有相邻的节点

例1、双栈排序(NOIP2008提高组)给出N(1<=n<=1000)个未排序的数，要求用两个栈将它排好序。有4种操作：1、入栈12、出栈13、入栈24、出栈2必须满足栈的先进后出的性质。不能排序则输出-1可以排序则输出字典序最小的操作序列。这道题的关键还是在于构图和染色。首先是构图：将所有数都看成点，两个点ai和aj之间连一条边的条件为ai和aj不能进入同一个栈。而不能进入同一个栈又如何判断呢？如果存在k使得i<j<k且ak<ai<aj则ai和aj不能进入同一个栈。构图完毕，问题就渐渐明朗了，如果图中存在奇环则问题必然无解。然后按照输入的顺序对图进行二染色，染到1的入1栈，染到2的入2栈。这样每个数字进哪个栈都知道，剩下的就是模拟了。图的连通分量最小生成树问题（MST）桥和割顶Sec3.图的连通性问题生成树问题无向图的最小生成树（贪心思想）Prim算法，适用于点少的图Kruskal算法，适用于边少的图有向图的最小树形图局域网(net)某局域网内有n(n<=100)台计算机，由于建网时工作人员的疏忽，现在网内存在回路，造成网络卡的现象。我们用f(i,j)表示i,j之间连接的畅通程度(f(i,j)<=1000)，f(i,j)值越小表示i,j之间连接越通畅，f(i,j)为0表示i,j之间无网线连接。现在我们需要除去一些连线，使得网络中没有回路，并且被除去网线的Σf(i,j)最大，请求出这个最大值。实际问题生成树：一个|V|个点的图，取其中|V|-1条边，并连接所有的顶点，则组成原图的一个生成树。属性：|v|-1条边、连通、无环。最小生成树：加权图的最小生成树是一棵生成树，其所有边的权值之和不会大于其它任何生成树。简单讲：找出连接所有点的最低成本路线最小生成树(MST）红边连接了所有顶点,所以构成一棵生成树权和=1+2+4+4+7+8+9环属性：一棵生成树上，增加一条边e，再删除e所在环上的最大边，会得到另一棵“更好”的生成树(如果e不是最大边)最小生成树(MST)-----算法原理94剪切属性：在图中，剪切将顶点划分成两个不相交集合。交叉边为这些顶点在两个不同集合的边。对于任何一个剪切，各条最小的交叉边都属于某个MST，且每个MST中都包含一条最小交叉边。最小生成树(MST)-----算法原理749最小边原则：图中权值最小的边(如果唯一的话)一定在最小生成树上。唯一性：一棵生成树上，如果各边的权都不相同，则最小生成树是唯一的。反之不然。最小生成树(MST)-----算法原理Prim算法构建MST的过程将1号节点置入集合S中。找到所有连接S中的节点和非S中的节点的边中的权值最小的那一条，并标记这条边，同时将连接的非S中的节点加入S集合。重复2步骤，直到所有节点都在S中了。1243561231231212算法描述1：(1)将G剪切成两个集合A、B，A中只有一个点r

(2)取最小权的交叉边(x,y)，x∈A,y∈B(3)将y加入A

(4)如果已经加了n-1条边，结束。否则，转(3)最小生成树(MST)-----Prim算法算法描述2：MST_Prim(G,r)//从任意点r出发，生长成一MSTfori=1tondo

dis[i]∞//初始化每点到A集合的最小值

inA[i]false//设顶点不在A中dis[r]0

//将r设为0（或-∞），准备取出fori=1tondovget-min()//取dis[?]中最小的值c和顶点v,

inA[v]true//v放入A中

sumsum+c

//c加入MST的总和中

updata(v)//枚举交叉边(v,B),改进dis[]最小生成树(MST)-----Prim算法算法要点：每次求最小权交叉边时，如果都重新计算，则显然要枚举(x,y)---x∈A,y∈B。O(n^2)时间复杂度。其实每次A中只是增加一个新顶点v，最多有交叉边(v,y)，修改量只有与v有边的顶点，为O(n)。只需记录下B中的每个元素y与A所有元素中最小权边，则求最小值最多为O(n)---有时可以用“堆”优化。

最小生成树(MST)-----Prim算法

Kruskal算法同样是常用的求最小生成树的算法之一，其算法思想如下：

Kruskal算法每次选择n-1条边，所使用的贪婪准则是：从剩下的边中选择一条不会产生环路的具有最小耗费的边加入已选择的边的集合中。注意到所选取的边若产生环路则不可能形成一棵生成树。Kruskal算法分e步，其中e是网络中边的数目。按耗费递增的顺序来考虑这e条边，每次考虑一条边。当考虑某条边时，若将其加入到已选边的集合中会出现环路，则将其抛弃，否则，将它选入。

这个算法可以用并叉集优化到o(e*ɑ(e))的时间复杂度。(ɑ表示阿克曼反函数)

最小生成树(MST)-----Kruskal算法找到连接两个不同连通分量（由已标记的边构成的）的边中，权值最小的那一条，标记这条边。重复1步骤，直到所有节点都在同一连通分量中。1243561231231212最小生成树(MST)-----Prim算法MST_Kruskal(G)(1)将G所有条边按权从小到大排序；图mst开始为空

(2)从小到大次序取边(x,y)(3)若加入边(x,y)，mst就有环，则放弃此边，转(2)

(4)将边(x,y)加入mst，如果已经加了n-1条边，结束。否则，转(2)最小生成树(MST)-----Kruskal算法算法要点：

Kruskal算法的最难点在于怎样判断加入边(x,y)后是否形成了环。问题可化为：判断边(x,y)的两个顶点x,y在图（实际是森林）mst中是否已经连通。如果已经连通，加入边将形成环；否则，不形成环。

并查集：连通点集之类问题，有高效算法---并查集。最小生成树(MST)-----Kruskal算法算法描述：MST_Kruskal(G)

fori=1tondof[i]i;//初始化并查集

sort(e,e+m);//边按大小排序c0;//取边的计数器fori=1tomdo

//从小到大取边vfind_set(e[i].v);//左端点所在连通块“根”ufind_set(e[i].u);//右端点所在连通块“根

if(u,v

不在同一连通块上)//如果不在同一连通块

union(v,u);//合并两连通块sum=sum+g[v][u];//加入这条边的权if(++c==n-1)break;//if取了n-1条边，结束最小生成树(MST)-----Kruskal算法时间复杂度分析Prim算法普通的方法

O(|V|2)

Prim算法中用“堆”方法O((|E|+|V|)*log|V|)---对稀疏图较好Kruskal算法O(|E|*log|E|+|N|*A(|V|))---对稀疏图较好最小生成树(MST)-----时间复杂度次小生成树根据kruskal算法，不难证明，任意一棵次小生成树必然是由最小生成树换掉一条边。如何实现?1、先求最小生成树。O((E+V)logE)2、在生成树上DFS求出任意两点间路径上的最大边权F[I][J]。O(V^2)3、穷举所有不在生成树上的边e=<s,t>，求出min{w[e]-F[s][t]}。O(E)时间复杂度：O((E+V)logE)例2、hurdles(USACO)给出一个N(1<=n<=300)个点M(1<=m<=25,000)条边的无向图，给出T(1<=t<=40,000)个询问，询问要求寻找一条从节点s，到节点t的路径使得该路径的边权的最大值最小，只需输出最大值即可。Hurdles.in56212123281352533442483412Hurdles.out48朴素想法：对于每次询问做一遍DFS时间复杂度：O(T*M)标准算法：1、求出原图的最小生成树。2、对于每个询问，在最小生成树上进行DFS找出最大边即可。时间复杂度：O((N+M)*logM+T*N)最小生成树的应用示例（构图）Newstart.pdf最小生成树的动态维护公路建设

与其实说桥和割顶，不如说是图的dfs树的运用。而桥和割顶，只是dfs树的一个比较重要的运用。图的dfs树即对图进行深度优先遍历所形成的一棵树。性质：任何一棵图的dfs树不能可能有横向边而只可能有返祖边。桥和割顶桥和割顶桥：定义：连通图中的一条边，如果删去这一条边，那么整个图就不再连通了。割顶：连通图中的一个点，如果删去这个点和相关的边，那么整个图就不再连通了。（这里只讨论无向图中的桥和割顶）ACBGDFE在左图中，DE之间的边即为这张图中唯一的一个桥。而D,E则分别为这张图中的两个割顶。ACBGDFEABDCEFG在dfs树中，我们不难发现，对于一个桥，必然没有一条返祖边跨越这条边，反之，则必然存在一条返祖边跨越这条边。桥和割顶桥和割顶

考虑到上面的这一个性质，我们就可以引入时间戳来求一个图的桥了。要判断一条边是不是桥，只需要看它的子树中，有没有一条返祖边返回到这条边的上面。因此，我们对于每个节点，维护一个访问时间和它的子树的最早访问时间。由于dfs树没有横向边，这一点很好地保证了，一个节点的子树的最早访问时间比这个节点的访问时间早，那么就存在一条返祖边返回到这个节点的祖先。通过这种方式，我们就能够求出一个图中的桥了。伪代码：Dfs(u){t=t+1;

time[u]=t;

min_time[u]=t

vst[u]=true;

for(u,v)∈Edo{if(vst[v]=false){

dfs(v);

min_time[u]=min(min_time[u],min_time[v]);}elsemin_time[u]=min(min_time[u],time[v]);}if(min_time[u]<time[u])u节点到父亲的边不是桥}桥和割顶桥和割顶思考：如何求一个图的割顶？（与求图的桥非常的相似）只需要考虑一个节点的所有子树（不包括该节点本身）是否有返祖边即可。（计算桥的时候需要考虑该节点本身）Sec4.最短路

最短路，是图论中最基本的问题，也有着广泛的运用。解决这一问题的算法也有很多种。今天，主要就介绍一些较为常见的最短路算法。全局最短路径算法：Floyd单源最短路径算法：Dijkstra Bellman-ford SPFA最短路径：对在权图G=(V,E),从一个源点s到汇点t有很多路径，其中路径上权和最少的路径，称从s到t的最短路径。简单讲：找出连接两个给定点的最低成本路径单源最短路径问题：求从源点s到其它所有点的最短路径问题。最短路径(ShortestPath)-----定义三角形性质设源点s到点x、y的最短路径长度为dis[x]、dis[y]。x与y之间的距离是len[x][y]，则有下面的“三角形定理”：

dis[x]+len[x][y]>=dis[y]

松驰若在处理过程中，有两点x、y出现不符合“三角形定理”，则可改进一下—松驰：

if(dis[x]+len[x][y]<dis[y])

dis[y]=dis[x]+len[x][y];最短路径(ShortestPath)-----属性XYS如果边没有负权的，我们可以用类似Prim算法的贪心算法—Dijkstra算法。算法描述1：SP_Dijkstra(G,s)(1)将G中顶点分成两个集合A、B，A集合中由已经求出最短路径的顶点组成，B集合是其它顶点。开始时A中只有一个点s

(2)从B集合中取一个当前最短的顶点v(3)把v加入A集合，并对v相连的顶点试做“松驰”

(4)如果|A|=|V|，结束。否则转(2)最短路径-----Dijkstra算法Dijkstra算法Dijkstra算法中心——++124331632+∞+∞+∞0Dist值4321节点号32654选择标记扩展算法描述2：SP_Dijkstra(G,s)//求单源s到其它点的最短距离fori=1tondodis[i]∞//初始化每点到s距离

inA[i]false//设顶点不在A中dis[s]0

//将dis[s]设为0，准备取出fori=1tondovget-min()//取dis[?]中最小的值c和顶点v,

inA[v]true//v放入A中

updata(v)//检查(v,B),松驰dis[?]sumsum+c

//c加入MST的总和中最短路径-----Dijkstra算法与prim不相同点如果边有负权的话，Dijkstra算法是错误的。这里需要不断迭代地做“松驰”，直到无“松驰”为止。算法描述3：SP_Bellman(G,s)(1)初始化每点到s点的最短距离为∞

(2)取所有边(x,y)，看x能否对y松驰。(3)如果没有任何松驰，则结束break。

(4)如果松驰次数<N，转(2)(5)否则，图中有“负圈”。最短路径-----Bellman-ford算法算法说明：Bellman-ford算法N次迭代就可以判断图中是否有“负环”。取所有边有两种方法：

(1)扫描每一点的邻接链表

(2)用有序点对(x,y)记录边时，可直接取边。但要请注意对无向图，要注意(y,x)也要松驰。对于求s到某点t的最短距离，可能因为其它地方有“负环”而出现问题，要预处理。最短路径-----Bellman-ford算法算法描述4：SP_Bellman(G,s)//求单源s到其它点的最短距离fori=1tondodis[i]∞//初始化每点到s距离dis[s]0

//将dis[s]设为0fori=1tondo

//最多迭代n

rel=false;//是否有松驰标志

for每条边(x,y)//取图的每一条边if(dis[x]+len[x][y]<dis[y])

//不满足三角形性质

dis[y]=dis[x]+len[x][y];

//松驰dis[y]

rel=true;ifrel=falsereturn0;//没有一次松驰，则结束return-1;//迭代了n次，有负圈最短路径-----Bellman-ford算法对迭代的改进：SPFA算法

Bellman-ford算法中，每次都要检查所有的边。这个看起来比较浪费，对于边(x,y)，如果上一次dis[x]没有改变，则本次的检查显然是多余的。我们每次只要从上次刚被“松驰”过的点x，来看看x能不能松驰其它点即可。

SPFA算法中用BFS中的队列来存放刚被“松驰”过的点。由于顶点个数为|V|，队列如果用数组的话显然要用“循环队列”使用空间。最短路径-----SPFA算法算法描述：SP_SPFA(G,s)//求单源s到其它点的最短距离fori=1tondodis[i]∞;vis[i]false;

//初始化每点到s距离,不在队列dis[s]0;//将dis[s]设为0vis[s]true;count1;

//s放入队列head0;tail

0;q[0]=s;

//队列头尾指针while(count>0)dovq[head];//队头节点vfor每条边(v,i)//与v相连的每一条边if(dis[v]+len[v][i]<dis[i])

//不满足三角形性质

dis[i]

dis[v]+len[v][i];

//松驰dis[i]

if(vis[i]=false)//不在队列，则加入队列

vis[i]true;count+1;tail+1;q[tail]=i;

vis[v]false;head+1;count-1;//v出队列最短路径-----SPFA算法求每对节点之间最短距离问题：例如，求一个图的直径，即所有最短路径中最长的。如果多次调用单源最短路径算法，效果并不好。特别是对有负边的图。如果无负环，则有简单的Floyd-warshell算法。这是动态规划算法。最短路径-----Floyd算法动态规划算法定义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]=len[i][j]（不存在的边权可为∞）最短路径-----Floyd算法算法描述6：SP_Floyd(G)//求每对节点的最短距离fori=1tondo

forj=1tondo

dis[i,j]len[i][j];

//初始化边界条件fork=1tondo//K放在最外层，数组少一维

fori=1tondoforj=1tondoif(dis[i,k]+dis[k][j]<dis[i,j])

//状态转移

dis[i,j]

dis[i][k]+dis[k][j];

最短路径-----Floyd算法Floyd算法主要用于解决一类全局最短路的问题。优点：常数小，编程复杂度低缺点：时间复杂度高，往往无法解决一类单源最短路的问题Fori=1ton1.取V-S中的一顶点u使dis[u]=min{dis[v]|v∈V-S}2.S=S+{u}3.ForV-S中每个顶点vdoRelax(u,v,W)Dijkstra算法优化：

1.用临接表存边

2.用二叉堆（最小堆）维护V-S集合中节点当前dis值算法复杂度从O(V^2)降到O((V㏒V+E)

Dijkstra算法最为经典的解决单源最短路径的算法不优化：优点：编程复杂度低缺点：时间复杂度不是很理想，所有边权必须非负

优化后：有点：时间复杂度理想缺点：编程复杂度略高（如果用c++选手用优先队列，可能空间复杂度较高），所有边权必须非负

Bellman-ford算法基本流程：对每一条边，都进行V次松弛操作。如果不存在负权环，可以证明，任意一条最短路都至多经过V个点，这一点保证了算法的正确性。此外，Bellman-ford算法还可以用于判断一个图中是否有负权环，经过V次操作后，再进行一次松弛操作，如果还有边可以松弛，则说明该图存在负权环。伪代码：fori=1to|V|-1do

for(u,v)∈Edo

relax(u,v,w);判断负权环

for(u,v)∈Edo

Ifdis[u]+w<dis[v]returnfalse时间复杂度太高！！！优化：SPFA算法

在Bellman-ford算法的实现过程中，实际上我们进行了大量的冗余计算。尤其是在后面的松弛过程中，枚举每一条边事实上浪费了大量的时间。由此，我们引入了SPFA算法。SPFA算法的本质还是Bellman-ford，但是它通过一个队列，去掉了大量的冗余计算，大大加速了算法。While(Q!=empty){u=Q.top;for(u,v)∈Edoif(relax(u,v,W)and(v∈V-Q)) Q=Q+v;Q=Q-u;}时间复杂度O(K*E)Dijkstra单源非负

O(|V|2)对稠密图好可用“堆”优化

O(|E|*log|V|)对稀疏图较好Bellman-Ford单源无负环

O(|V|*|E|)可先用Dijkstra预处理优化SPFA用更新队列优化,时间复杂度平均好，但不确定。Floyd全源无负环

O(|V|3)最短路径-----算法比较例3、phoneline(USACO)

有N(1<=n<=1000)个点，M(1<=m<=10000)条边，寻找一条从结点1到结点N的路径，使得其中各边长度的最大值最小。并且给定一个整数K(0<=k<=300)，可以使路径中的K条边长度变为零。求最小的那个最大值。乍看和最短路没有关系，因为要求最大值最小。二分答案？1、对边按照长度排序。2、二分要输出的最小的最大值P。3、把所有边长小于等于P的边长度标为0，大于P的边长度标为1。4、做一次单源最短路径，求出1到N的最短路径，看是否小于K。时间复杂度：Dijkstra:N^2*logM悬！Dijkstra

堆优化:(NlogN+M)logM可行！SPFA:由于边权有许多0，松弛次数不会很多可行！例4、block(USACO)Bessie来到一个小农场，有时她想回老家看看她的一位好友。她不想太早地回到老家，因为她喜欢途中的美丽风景。她决定选择次短路径，而不是最短路径。农村有R(1<=R<=100,000)条双向的路，每条路连接N(1<=N<=5000)个结点中的两个。结点的编号是1..N。Bessie从结点1出发，她的朋友(目的地)在结点N。次短路径可以使用最短路径上的路，而且允许退回，即到达一个结点超过一次。次短路径是一种长度大于最短路径的路径(如果存在两条或多条最短路径存在，次短路径就是比它们长，且不比其他任何的路径长的路径)。典型的次短路径算法并不复杂在记录最短路径的Dist[i]数组中同时存放到i点的最短路径和次短路径，记作Dist[i][1]和Dist[i][2]，在做松弛操作的时候同时更新最短路径和次短路径。第一遍每次都选取Dist[i][1]最小的进行松弛，在Dist[i][1]全部都松弛一遍后再选取Dist[i][2]最小的进行松弛。时间复杂度同最短路径拓扑排序在图论中有着重要的地位，在历届NOIP中，对这方面的内容也有所考察，比如03年的神经网络等等。拓扑排序是针对有向无环图而言的。拓扑排序后形成的序列满足这样一个条件：不存在两个点u,v，u在序列中在v之前并且v在图中是u的前驱。1243657对于右图，一个满足条件的拓扑序列是1234567。然而1235764则不满足条件，因为7在序列中在4之前，但是4是7的前驱。Sec.5拓扑排序拓扑排序

我们可以通过一个队列来解决这一类问题。我们每次把入度为0的点入队，然后依次处理这些点，将这些点的出边删除，删除时，顺便将新造成的入度为0的点入队，处理完某个点后，这个点出队。如此操作，直到队列为空。如果还存在某个点没有入过队，这说明这个有向图存在环。伪代码：While(Q!=empty){u=Q.top;for(u,v)∈Edo{

dec(cnt[v])if(cnt[v]=0)Q=Q+v;}Q=Q-u;

}拓扑排序算法寻找入度为0的节点将找到的节点放入队列中，删除所有这个节点引出的边重复1，直至没有度为0的节点如果有节点不在队列中，则说明原图中有环，否则无环。1253647求关键路径算法对给定的图进行拓扑排序按照拓扑排序的结果扩展和标记12345687964511247924Sec6.网络流与匹配问题网络最大流最小费用最大流二分图的最大匹配二分图的最佳匹配网络流算法寻找增广链，并根据增广链修改流量。重复这一步骤，直到不再存在增广链。如果需要在此基础上求最小费用最大流，只需从增广链的选择上着手。二分图与匹配算法二分图的匹配算法又称匈牙利算法匈牙利算法的中心——可增广轨不断寻找可增广轨，并根据可增广轨修改匹配最佳匹配只是在选择可增广轨时，将匹配的权值作为选择的条件图的应用(模型构建)

例题1:(TRAVEL)

一个城市中有N个车站，已知M条连接这些车站的公共汽车单向路线，设计算法求出从第一号车站到第N号车站的最少换车次数.分析这道题粗看起来似乎不太简单，但我们仔细分析一下题目就会发现，这道题实际上可以转化为最短路径问题来进行求解。考虑经过的所有路线中，每条路线都只保留一头一尾两个车站，则经过的车站数目再减2实际上就是所求的换车次数了。要使换车次数最少，也就是要找从1到N的一条最短路径。而图中的边也需要重新设计。在每一条路线中，任两个结点均由其中的前者向后者连一条边，然后将每条边的长度都定为1。利用图论模型进行构造例题2：圆桌吃饭问题

n个人围着一张圆桌吃饭，每个人都不愿意两天与同一人为邻，问最多能坐多少天，并给出一种排列方案？转化为图论模型

设G=(V,E)为一完全图，|V|=n。图中的每个顶点代表一个人，连结顶点的边表示人之间的相邻关系。因此，每种围绕圆桌的吃饭方案就成为图中的一条哈密尔顿回路。设L=<v1,v2,…,vn>为G中的一条哈密尔顿回路，其中所含的边的集合记为e(L)。问题转化为：求m与L1,L2,…,Lm，使得e(Li)∩e(Lj)=φ，并且m达到最大值。构造方法

作一圆，把圆周分成n-1等分，标上n-1个刻度，将顶点1至n-1依次排列在圆周上，顶点n放在圆心。先从圆心出发，向任意点连一条线，再从这点出发，沿圆周向左右两个方向迂回连线，直到连完圆周上所有的点，再连回圆心。这样就构造出一条哈密尔顿回路。保持所有的顶点位置不变，把所有连线围绕圆心逆时针方向旋转一个刻度，得到一条新的哈密尔顿回路。这样连续旋转(n-1)div2次，就得到了(n-1)div2条回路。N=5当n=5时构造图象，充分展示各变量之间的关系

【例3】01串问题(NOI)

给定N,L0,A0,B0,L1,A1,B1，设计一个长度为N的01串，使得对于任何连续的长度为L0的子串，0的个数大于等于A0,且小于等于B0,对于任何连续的长度为L1的子串，1的个数大于等于A1且小于B1。【解题分析】模式1分析不等式

设hi为01子串s0..si(1<=I<=n)中1的个数，其中s0=0,h0=0。显然，由hi的定义可以得出不等式0<=hi-1<=hi,hi<=hi-1+1,移项即得：

0<=hi-hi-1

-1<=hi-1-hiL0-b0<=hi-hi-l0

当I>=L0时，根据条件，Si-L0+1…Si中0的个数(L0-(hi-hi-L0))在a0～b0之间，即a0<=L0-(hi-hi-L0)<=b0

a0-L0<=hi-L0-hi-b1<=hi-l1-hi

当I>=L1时，根据条件，Si-L1+1…

Si中1的个数(hi-hi-L1)在a1～b1之间，即a1<=hi-hi-L1<=b1。a1<=hi-hi-L1

一旦有了h序列，我们可以由左至右构造s串：如果hi-1=hi，则说明si=0；否则si=1(1<=I<=n)。由此看来，问题的关键是如何计算h序列。

仔细观察上述推论条件，发现有以下特点：（1）除h0=0外，其余的条件都是由“<=”连接的不等式

（2）

每个不等式都是含两个h未知数、一个常数的一次不等式；可见，所有不等式都整理成了k<=hi-hj

它给我们启示，上述不等式类似于连接两点的一条有向边。因此，我们联想到信息学解题中常用的图论知识。

模型2构造有向图G

我们构造有向图G，如图：

其中vi代表s串中的第I位。若k<=vi-vj,则vi向vj引出一条权为k的有向边<vi,vj>,表明si…sj中至少需增加k个1（k为正值）或减少k个1(k为负值)。由此得出构造有向图G的方法：

0<=hi-hi-1

-1<=hi-1-hi

a0-L0<=hi-L0-hi

L0-b0<=hi-hi-l0a1<=hi-hi-L1-b1<=hi-l1-hi

计算图G的最长路径：我们已构造了一个有n+1个顶点的有向图G。

（1）图G中无环令D[I]表示从顶点0到顶点I的最长路径长度。对于图中每条从点I指向点J的权为C[I,J]的边，有性质

D[I]+C[I,J]<=D[J]（注意：这与上述不等式的形式相似）这样，令hi=D[I]，h完全符合所有限制条件，即为原不等式组的一组解。

（2）G中含有环可用反证法证明无解。从s1出发，顺序确定每位二进制数。当hi=hi-1时，说明s1…si-1中1的个数与s1…si中1的个数相同，即si为0；否则si为1。

最短路例题4：求第一、第二、