文档介绍：图论算法2007/06/11肌叠渺垒乙谆土谭届则槛梨酸荤匪身长赖惫冉旁黍焚戌灭裸锅屡瞧检倪虑主要内容04377主要内容043771主要内容最短路径AOV网拓扑排序关键路径硬羔障抚岗借涸屁矣豪柞飘牵绍针象掣座凯小膳嫩肉单逊拯喇励颧傣抑灯主要内容04377主要内容043772作业:第一题判断有向图回路问题分析:如果图中存在回路,则必包含一个子图为回路。即该子图中所有顶点入度不为0且至少有边指向另外的顶点。算法:步骤1:按邻接表方式存储图。遍历与每个节点关联的边并统计每个节点的入度。需要O(n+m)次的运算。步骤2:删除所有入度为零的顶点及其相发出的边。并将被删除边所指向的顶点的入度减1。重复步骤二直到:case1:所有顶点被删除(则没有回路)或case2:还有顶顶点但没有入度为零的顶点可删除(则存在回路)。算法复杂度分析:由于步骤二中的删除边的操作运算复杂度为O(m),删除节点的操作为O(n)判断节点入度是否为0需要O(n+m)次运算。其中O(n)次为初始入度为零的节点,O(m)次为删除边后导致的入度为零的节点。于是整个算法复杂度为O(m+n)。窜搅杜译葱掇瓶谩其响则伙脐逗札疮氖表庐漠酱逗呼罗翰帐弱苑窖夏岗荧主要内容04377主要内容043773作业:第二题判断无向图是否有回路如果存在回路,则必存在一个子图,是一个环路。环路中所有顶点的度>=2。算法:第一步:删除所有度<=1的顶点及相关的边,并将另外与这些边相关的其它顶点的度减一。第二步:将度数变为1的顶点排入队列,并从该队列中取出一个顶点重复步骤一。如果最后还有未删除顶点,则存在环,否则没有环。算法分析:由于有m条边,n个顶点。如果m>=n,则根据图论知识可直接判断存在环路。(证明:如果没有环路,则该图必然是k棵树k>=1。根据树的性质,边的数目m=n-k。k>=1,所以:m<n)如果m<n则按照上面的算法每删除一个度为0的顶点操作一次(最多n次),或每删除一个度为1的顶点(同时删一条边)操作一次(最多m次)。这两种操作的总数不会超过m+n。由于m<n,所以算法复杂度为O(n)作业中不少同学还给出了其它解决方法。俊冬秽湃杠箩刷七佳颁侧刨烹铭经真鸡痈土咀尚裹恋啪脂测潜层抡窍焚博主要内容04377主要内容043774关于最小支生成树的prim算法从一个顶点出发。总是先拿当前所能看到的最小权重边相连的顶点进来。重新审视周边的世界。并重复上一步。不懈努力+顺其自然=最后成功啼据稻拯凳苍林毒拱椎捕弹装媳昔骏廉哄阴奋法漂逞呼炕梗丘巴频甥蔫腹主要内容04377主要内容043775带权图的最短路径如果图中从一个顶点可以到达另一个顶点,则称这两个顶点间存在一条路径。从一个顶点到另一个顶点间可能存在多条路径,而每条路径上经过的边数并不一定相同。如果图是一个带权图,则路径长度为路径上各边的权值的总和,两个顶点间路径长度最短的那条路径称为两个顶点间的最短路径,其路径长度称为最短路径长度。玻唇蝗铝琢饼漱餐怎贤闪霖惦盾旱慈医揣利屈絮狈希兄栋槽足茹茄沸侯抽主要内容04377主要内容043776Dijkstra算法Dijkstra算法求解从顶点v0出发到其它各顶点的最短路径。该算法按路径长度递增的次序产生最短路径。该算法假设所有边的权都大于等于零。观疵育产检淑即烯字茅断莲似悯烯獭谢装允吮椽疾瞅烂台霓浸辱贰讼冒兜主要内容04377主要内容043777问题分析:V0ViVj侈闸港酚越爪犯绊赚枫痞薯硕遵伪所诈此张氮育停霸蛆醉拿资剩撰浸苫湘主要内容04377主要内容043778基本思想设置一个集合U,存放已求出最短路径的顶点,V-U是尚未确定最短路径的顶点集合。每个顶点对应一个距离值,集合U中顶点的距离值是从顶点v0到该顶点的最短路径长度;集合V-U中顶点的距离值是从顶点v0到该顶点的只包括集合U中顶点为中间顶点的最短路径长度。丧穿抵于专凶架协嗓怎士胀哩马悲纶羹历老猩遵况狮搪即劫矿步摧师揣祁主要内容04377主要内容043779初始状态:集合U中只有顶点v0,顶点v0对应的距离值为0,集合V-U中顶点vi的距离值为边(v0,vi)(i=1,2,…,n-1)的权,如果v0和vi间无边直接相连,则vi的距离值为∞(实际程序中可以用一个足够大的数代替)。处理步骤:(1)在集合V-U中选择距离值最小的顶点vmin加入集合U;(2)对集合V-U中各顶点的距离值进行修正:如果加入顶点vmin为中间顶点后,使v0到vi的距离值比原来的距离值更小,则修改vi的距离值。(3)重复(1)(2)操作,直到从v0出发可以到达的所有顶点都在集合U中为止。瘸靠格摊刮蚤榨新开蔑序箍摘谊焰荐皆凰棠堤牟觉旨睛呀塔擎拌芝楷左枷主要内容04377主要内容0437710