NOIP图的基础算法

NOIP图的常用算法简介石门中学江涛2009.10.5目录图的表示邻接矩阵、邻接链表、图的遍历最小生成树算法Prim算法、Kruskal算法最短路径算法Dijkstra算法、Bellman_Ford算法及SPFA算法、Floyd算法目录图的表示邻接矩阵、邻接链表、图的遍历最小生成树算法Prim算法、Kruskal算法最短路径算法Dijkstra算法、Bellman_Ford算法及SPFA算法、Floyd算法顶点给点编号为连续的整数把顶点存放在数组中边邻接矩阵布尔值(或边权值)-TRUE–有边FALSE–无边空间复杂度O(|V|2)图的表示-----邻接矩阵边邻接链表每一个顶点有一个所有与之相邻的链表每一条边2个（对无向图）要在两个顶点的链表中都加入空间复杂度O(|E|)对稀疏图这种方式比较好图的表示-----邻接链表图的邻接链表的Pascal和C++实现具体参见《NOIP基础数据结构》ppt图的表示-----C/P语言程序实现图的深度优先(Depth-First)遍历:邻接链表、C++图的表示-----图的遍历//图的一般结构structgraph_node{…};structAdjList{intid;AdjList*next;};intn_nodes,S_index=0;graph_nodenodes[maxN];intvisited[maxN];AdjList*adj[maxN];标识项点有没有访问过每个顶点都有邻接链表邻接链表的节点数据结构图的深度优先(Depth-First)遍历:邻接链表、C++图的表示-----图的遍历置每个点标识为“未访问”从所有未被访问的点k出发，调用DFS(k)voidsearch(){intk;for(k=0;kn_nodes;k++)visited[k]=0;for(k=0;kn_nodes;k++)if(!visited[k])DFS(k);}置被访问节点的“时间”---次序访问k的所有相邻的节点voidDFS(intk){//从k出发搜索AdjList*j;visited[k]=++S_index;for(j=adj[k];j!=NULL;j=j-next){if(!visited[j-id])DFS(j-id);}图的深度优先(Depth-First)遍历:邻接链表、Pascal图的表示-----图的遍历//图的一般结构typegraph_node=record…end;typeAdjList=recordid:integer;next:^AdjList;end;varn_nodes,S_i:integer;nodes:array[1..maxN]ofgraph_node;visited:array[1..maxN]ofinteger;adj:array[1..maxN]of^AdjList;标识项点有没有访问过每个顶点都有邻接链表邻接链表的节点数据结构图的深度优先(Depth-First)遍历:邻接链表、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出发搜索varj:^AdjList;begininc(S_i);visited[k]:=S_i;j:=adj[k];while(jNULL)dobeginifvisited[j^.id]0thenDFS(j^.id);j:=j^.next;end;end;图的宽度优先(Breadth-First)遍历:邻接链表、C++图的表示-----图的遍历//图的一般结构structgraph_node{…};structAdjList{intid;AdjList*next;};intn_nodes,S_index=0;graph_nodenodes[maxN];intvisited[maxN];AdjList*adj[maxN];标识项点有没有访问过每个顶点都有邻接链表邻接链表的节点数据结构图的宽度优先(Breadth-First)遍历:邻接链表、C++图的表示-----图的遍历置每个点标识为“未访问”从所有未被访问的点k出发，调用BFS(k)voidsearch(){intk;for(k=0;kn_nodes;k++)visited[k]=0;for(k=0;kn_nodes;k++)if(!visited[k])BFS(k);}图的宽度优先(Breadth-First)遍历:邻接链表、C++图的表示-----图的遍历intq[maxN];voidBFS(intk){intfront,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的所有相邻的节点图的宽度优先(Breadth-First)遍历实例示意:图的表示-----图的遍历图的遍历:邻接链表时间复杂度分析每一个顶点访问一次每条边访问两次无向图每条边出现在两个链表中O(|V|+|E|)O(|V|2)对稠密图|E|~|V|2O(|V|)对稀疏图|E|~|V|对稀疏图邻接链表的效果非常好！图的表示-----图的遍历目录图的表示邻接矩阵、邻接链表、图的遍历最小生成树算法Prim算法、Kruskal算法最短路径算法Dijkstra算法、Bellman_Ford算法及SPFA算法、Floyd算法生成树：一个|V|个点的图，取其中|V|-1条边，并连接所有的顶点，则组成原图的一个生成树。属性：|v|-1条边、连通、无环。最小生成树：加权图的最小生成树是一棵生成树，其所有边的权值之和不会大于其它任何生成树。简单讲：找出连接所有点的最低成本路线最小生成树(MST)-----定义红边连接了所有顶点,所以构成一棵生成树权和=1+2+4+4+7+8+9局域网(net)[RQNOJ]某局域网内有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)最大，请求出这个最大值。最小生成树(MST)-----实例一环属性：一棵生成树上，增加一条边e，再删除e所在环上的最大边，会得到另一棵“更好”的生成树(如果e不是最大边)最小生成树(MST)-----算法原理94剪切属性：在图中，剪切将顶点划分成两个不相交集合。交叉边为地些顶点在两个不同集合的边。对于任何一个剪切，各条最小的交叉边都属于某个MST，且每个MST中都包含一条最小交叉边。最小生成树(MST)-----算法原理749最小边原则：图中权值最小的边(如果唯一的话)一定在最小生成树上。唯一性：一棵生成树上，如果各边的权都不相同，则最小生成树是唯一的。反之不然。思考：怎样图G判断只有一个MST？最小生成树(MST)-----算法原理算法描述1：MST_Prim(G,r)(1)将G剪切成两个集合A、B，A中只有一个点r(2)取最小权的交叉边(x,y)，x∈A,y∈B(3)将y加入A(4)如果已经加了n-1条边，结束。否则，转(3)算法证明：根据剪切属性图(?)最小生成树(MST)-----Prim算法算法要点：每次求最小权交叉边时，如果都重新计算，则显然要枚举(x,y)---x∈A,y∈B。O(n^2)时间复杂度。其实每次A中只是增加一个新顶点v，最多有交叉边(v,B)，修改量只有与v有边的顶点，为O(n)。只需记录下B中的每个元素y与A所有元素中最小权边，则求最小值最多为O(n)---有时可以用“堆”优化。最小生成树(MST)-----Prim算法算法描述2：MST_Prim(G,r)//从任意点r出发，生长成一MSTfori=1tondodis[i]∞//初始化每点到A集合的最小值inA[i]false//设顶点不在A中dis[r]0//将r设为0（或-∞），准备取出fori=1tondovget-min()//取dis[?]中最小的值c和顶点v,inA[v]true//v放入A中sumsum+c//c加入MST的总和中updata(v)//枚举交叉边(v,B),改进dis[]最小生成树(MST)-----Prim算法算法描述3：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算法并查集：并查集详细内容可参见有关文章。下面是Pascal段：//初始化，使每个集合只一个元素。fori:=1tondof[i]:=i;//查找x所在类的“根”---代表，并压缩路径functionfind_set(x:longint):longint;beginiff[x]xthenf[x]:=find_set(f[x]);exit(f[x]);end;//合并两个集合。x,y为两集合的“根”procedureunion(x,y:longint);beginf[x]:=y;end;最小生成树(MST)-----Kruskal算法并查集：并查集详细内容可参见有关文章。下面是C++片段：//初始化，使每个集合只一个元素。for(i=1;i=n;i++)f[i]=i;//查找x所在类的“根”---代表，并压缩路径intfind_set(intx){if(f[x]!=x)f[x]=find_set(f[x]);return(f[x]);}//合并两个集合。x,y为两集合的“根”voidunion(intx,y){f[x]=y;}最小生成树(MST)-----Kruskal算法算法描述4：MST_Kruskal(G)fori=1tondof[i]i;//初始化并查集sort(e,e+m);//边按大小排序c0;//取边的计数器fori=1tomdo//从小到大取边vfind_set(e[i].v);//左端点所在连通块“根”ufind_set(e[i].u);//右端点所在连通块“根”if(v!=u)//如果不在同一连通块union(v,u);//合并两连通块sum+=g[v][u];//加入这条边的权if(++c==n-1)break;//if取了n-1条边，结束最小生成树(MST)-----Kruskal算法时间复杂度分析Prim算法普通的方法O(|V|2)Prim算法中用“堆”方法O((|E|+|V|)*log|