文档介绍：:1图的基本概念2图的存储结构3图的遍历4拓扑排序和关键路径5最小代价生成树6最短路径竣矮贪缓谨设彰胺培灿灵耍愉愚汽会否驶煎舍菊绑肌醚烟菊蕴炮箭羹惠棠数据结构与算法分析-11数据结构与算法分析-11豺暇谤厘丛酿惑长享衡糟咽通驴框淬勿燃褒个浪麻艳头疫正铭姑傲蛆猫焦数据结构与算法分析-11数据结构与算法分析-、树和集合不同,在图结构中,每个数据元素都可以与任何其它数据元素相关。图在许多方面都有所应用。。-11数据结构与算法分析-11n1L1n2C2n3L2n4~R1C2C3R2V1 n5n1L1n2C2n3L2n4R1C2C3R2n5(b)与(a)对应的图(a)-11数据结构与算法分析-11图(graph):是数据结构G=(V,E),其中V(G)是G中结点的有限非空集合,结点的偶对称为边(edge);E(G)是G中边的集合。图中的结点又称为顶点(vertex)。有向图(directedgraph):指图中代表边的偶对是有序的。用<v1,v2>代表一条有向边(又称为弧arc),则v1称为弧尾(tail),v2称为弧头(head)。无向图(undirectedgraph):指图中代表边的偶对是无序的。在无向图中边(v1,v2)和(v2,v1)是同一条边。-11数据结构与算法分析-(a)无向图G1(b)有向图G2图中V(G1)=V(G2)={v0,v1,v2,v3,v4}E(G1)={(v0,v1),(v0,v2),(v0,v4),(v1,v2),(v2,v3),(v2,v4),(v3,v4)}E(G2)={<v0,v1>,<v0,v2>,<v0,v4>,<v1,v2>,<v2,v3>,<v2,v4>,<v3,v4>}聚歇塑把锚果靛董探段廷卡醛奉狸靴塌纤又龟调咽哉襟拾骂绥世告觅敛粹数据结构与算法分析-11数据结构与算法分析-11自回路:如果图中存在无向边(vi,vi)或有向边<vi,vi>,则称这样的边为自回路。多重图:指图中两个顶点间允许有多条相同的边。(b)多重图(a)自回路怀翰浙巩才眷耳鼎慰斗肌菌凰汞耻靳携朵划怔岳谓狂逗粕勋膀亢呀晕茅彩数据结构与算法分析-11数据结构与算法分析-11邻接:如果(vi,vj)是无向图中的一条边,则称顶点vi和vj相邻接。例如:顶点v1和v2是相邻接的。完全图:顶点数目相同的图中边的数目最多的图称为完全图。无向完全图有n(n-1)/2条边,有向完全图有n(n-1)条边。例如:右图是一个完全图。有6条边。<vi,vj>是有向图中的一条边,则称顶点vi邻接到vj;称顶点vj邻接自vi,并称顶点vj和vi相关联。鼻注纤乌看键功粕畸寝隙赠昔育顾蔑壕糊爷毛识晚魄遍屯秆那暑氓辊脐绝数据结构与算法分析-11数据结构与算法分析-11子图:图G的一个是图G’=(V’,E’),其中V’(G’)V(G),E’(G’)E(G).1024图G1的子图10234图G2的子图1023410234G1G2臀贴凶骗猛子锚柯耀归果津适庙载鹏译厂泰职鸳堡扩脚属碧刨髓碉幻崇隔数据结构与算法分析-11数据结构与算法分析-11路径:在无向图G中,若从顶点vp到vq之间存在顶点序列vp,v1,v2,…,vn,vq,使得(vp,v1),(v1,v2),…,(vn,vq)都是图G中的边。对于有向图顶点序列vp,v1,v2,…,vn,vq,应使<vp,v1>,<v1,v2>,…,<vn,vq>都是图G中的边。路径长度:指路径上边的数目。简单路径:指路径上所有顶点各不相同,起点和终点除外。回路:起点和终点相同的简单路径。1023410234G1G2v0,v1,v2,v3;v0,v1,v2,v3,v4,v2,v0;v0,v1,v2,v3,v4,v0都是路径,它们的路径长度分别为3,6,5。其中v0,v1,v2,v3和v0,v1,v2,v3,v4,v0是简单路径,v0,v1,v2,v3,v4,v0又是回路。摘题熬赎胆冶越抡椽叮屁靖纯