图论基础图的概念定义 一个图G是指一个二元组(V(G),E(G)其中:是非空有限集，称为顶点集，其中元素称 为图G的顶点E(G)是顶点集V(G)中的无序或有序的元素 对 组成的集合，即称为边集,其中元 素称为边赋权图定义 若图 的每一条边e 都赋 以一个实数w(e)，称w(e)为边e的权，G 连 同边上的权称为赋权图。图论算法所研究的往往和权值有关图的顶点度定义 在无向图G中，与顶点v关联的边的数目,称 为顶点v的度或次数，记为d(v)在有向图中，从顶点v引出的边的数目称为 顶点v的出度，记为d+(v)，从顶点v引入的边 的数目称为v的入度，记为d -(v). 称d(v)= d+(v)+d -(v)为顶点v的度或次数图的矩阵表示 对无向图 ，其邻接矩阵 ，其中 ：对有向赋权图 , 其邻接矩阵图的邻接表表示图的邻接表表示如图如图G2G2的的邻接表邻接表为：为：2534154353341221212345G2 邻接表实现邻接表实现链表？ 没有必要！vector? 可行！动态花销较大！数组模拟？ 灵活！效率高！ 邻接表邻接表-vector-vectorvector eN;初始化：For(int i=0;ib，权值为cea.push_back(make_pair(b,c);优点：方便数组模拟typedef struct int v,next,val; edge;edge eMAXM;int pMAXN,eid; void init()memset(p,-1,sizeof(p);eid=0; void insert(int from,int to,int val)eeid.v=to;eeid.val=val;eeid.next=pfrom;pfrom=eid+;最短路问题单源点：求赋权图中从给定点到其余顶点 的最短路多源点：求赋权图中任意两点间的最短路.多源最短路Floyd 从任意一条单边路径开始。所有两点之 间的距离是边的权，如果两点之间没有边 相连，则权为无穷大。 对于每一对顶点 u 和 v，看看是否存在一 个顶点 w 使得从 u 到 w 再到 v 比己知的路 径更短。如果是更新它。 for(k=1;k=n;k+)for(i=1;i=n;i+)for(j=1;j=n;j+)if(mapik+map kjmapij)mapij=mapik+mapkj;mapi,j:=minmapi,k+mapk,j,mapi,j熟悉的式子!Floyd是一种动态规划算法!c i, j, k表示从i 到j 的最短路径的长度，其 中k 表示该路径中的最大顶点中间顶点不超过k 的i 到j 的最短路径有两种 可能：该路径含或不含中间顶点k。若不含 ，则该路径长度应为ci, j, k-1，否则长度为 ci, k, k-1 +c k, j, k-1。ci, j, k可取两者中 的最小值。状态转移：ci, j, k=minci, j, k-1, c i, k, k- 1+c k, j, k-1zoj 1082要在N个人中传播谣言，每个人传播谣言给 他可以联系的人都有个时间，求从哪个人 开始传播谣言并使谣言传遍所有人的时间 最短。单源最短路DijkstraSPFADijkstra+堆优 化 复杂度O(n2)O(km)O(nlgn)处理负边不能能不能适用稠密图稀疏图稠密图单源最短路SPFA 初始时将源加入队列。 每次从队列中取出一 个元素，并对所有与他相邻的点进行松弛，若 某个相邻的点松弛成功，则将其入队。 直到 队列为空时算法结束。SPFA 在形式上和宽度优先搜索非常类似，不 同的是宽度优先搜索中一个点出了队列就不可 能重新进入队列，但是SPFA中一个点可能在 出队列之后再次被放入队列，也 就是一个点 改进过其它的点之后，过了一段时间可能本身 被改进，于是再次用来改进其它的点，这样反 复迭代下去。图的生成树在一个连通图G中，如果取它的全部顶点和 一部分边构成一个子图G，即： V(G)=V(G);E(G) E(G)若边集E(G)中的边既将图中的所有顶点连 通又不形成回路，则称子图G是原图G的一 棵生成树。一棵含有n个点的生成树，必含有n-1条边 。最小生成树对于一个连通网（连通带权图，假定每条 边上的权均为大于零的实数）来说，每棵 树的权（即树中所有边的权值总和）也可 能不同具有权最小的生成树称为最小生成树。Kruskal贪心思想将图G中的边按权值从小到大依次选取，若 选取的边使生成树不形成回路，则把它并 入TE中，若形成回路则将其舍弃，直到TE 中包含N-1条边为止，此时T为最小生成树 。从小到大选取 排序！判断形成回路 并查集！hdu 1233某省调查乡村交通状况，得到的统计表中列出 了任意两村庄间的距离。省政府“畅通工程”的 目标是使全省任何两个村庄间都可以实现公路 交通（但不一定有直接的公路相连，只要能间 接通过公路可达即可），并要求铺设的公路总 长度为最小。请计算最小的公路总长度。prim.假设G=(V,E)是一个具有n个顶点的连通网， T=(U,TE)是G的最小生成树，U,TE初值均为空集。首先从V中任取一个顶点（假定取v1），将它并入 U中，此时U=v1，然后只要U是V的真子集(UV) ，就从那些一个端点已在T中，另一个端点仍在T外 的所有边中，找一条最短边，设为(vi,vj),其中 viU,vjV-U，并把该边(vi,vj)和顶点vj分别并入T的 边集TE和顶点集U，如此进行下去，每次往生成树 里并入一个顶点和一条边，直到n-1次后得到最小生 成树。关键问题每次如何从连接T中和T外顶点的所有边中 ，找到一条最短的