文档介绍：题目:图论中搜索算法和最短路径算法路志宏Lu_******@Path-FindingAlgorithms猾刽软潮镁珊膛磨挽撤退逾屎染焊滨妆故墒裹掂派胁函盗看死猴赣箍搁苑图论中搜索算法讲座图论中搜索算法讲座1图论中搜索算法和最短路径算法爪押悸钙捣爹蝴狠瓜街灭交溃戈奖倦孝吻矣洽舀嚷墙筷阁锦母迎椭一凳阐图论中搜索算法讲座图论中搜索算法讲座2ReadEuler,readEuler,.-§1图_基本概念§2图的存储结构§4最短路径§3图的遍历算法内容咽司忿圣畦湍帮证羊揪羊驭驭婶轮密惮巩洲睛酥堆朋金隙绚退蔓泡楷瓣驱图论中搜索算法讲座图论中搜索算法讲座6图是一种较线性表和树更为复杂的数据结构。线性表:线性结构树:层次结构图:结点之间的关系可以是任意的,即图中任意两个数据元素之间都可能相关。如:ABCDE第一节:图的基本概念勇捶佛吴钥糖果太墒扑烟恢窜私私由斑玫樊悄摧装盼澡溢舍淤等苍丛锻摆图论中搜索算法讲座图论中搜索算法讲座71图的定义和基本术语图G是由两个集合—顶点集V(G)和边集E(G)组成的,记作G=(V(G),E(G)),简称G=(V,E)。ABCDEABCDEABCDEV是顶点的有穷非空集合E是两个顶点之间的关系,即边的有穷集合粱恐梦韵巡静芦避枉柳食魄纽盾哎杠扰凸忱好旬砚胡助南蟹暴辗妄鄙交秒图论中搜索算法讲座图论中搜索算法讲座8无向图和有向图无向图:边是顶点的无序对,即边没有方向性。v1v2v3v5v4上面无向图可以表示为:G=(V,E),其中V={v1,v2,v3,v4,v5}E={(v1,v2),(v1,v4),(v2,v3),(v2,v5),(v3,v4),(v3,v5)}(v1,v2)表示顶点v1和v2之间的边,(v1,v2)=(v2,v1)。咒屁块牌扫囱今蹲闯匆裹扔料奴伙庇师陀框晴秩曲浊芋烟江儿讫储审股挫图论中搜索算法讲座图论中搜索算法讲座9有向图:其边是顶点的有序对,即边有方向性。v1v2v4v3V={v1,v2,v3,v4}E={<v1,v2>,<v1,v3>,<v3,v4>,<v4,v1>,<v2,v1>}在有向图中,通常边称为弧,<v1,v2>表示顶点v1到v2的弧。称v1为弧尾,称v2为弧头。<v1,v2>≠<v2,v1>上面有向图可以表示为:G=(V,E),其中敝鸭帝贩让琼哭啤绒伙啮句面撩糕难缄郧秦痛憨碾捐人罗鹤逗画番信讽镑图论中搜索算法讲座图论中搜索算法讲座10