[工学]基本数据结构-图

《[工学]基本数据结构-图》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、ACM/ICPC程序设计基本数据结构及其在程序设计中的应用张淑平非线性结构树、二叉树图数据结构课程中所要求的图掌握图模型中数据的存储方式：图的邻接矩阵存储和邻接表存储结构。掌握图的两种遍历方法：深度优先遍历和广度优先遍历算法。理解求最小生成树、拓扑排序、求关键路径、求最短路径等算法。图的示例00000010100010001000000100010000001000100000010001110000000012345678910123456789100010000001100100001000001010011000010000v3v4v2v7v1v9v8v5v6v10图结构基

2、本概念图是顶点集和边集组成的二元组G=(V,E),E中每条边是V中一对顶点(u,v)间的联系,如果是无序对，那么称该图为无向图，否则为有向图。顶点u,v间有边，u,v互为邻接点。边(u,v)，和顶点u和v相关联。顶点v的度是和v相关联的边的数目.有向图中,以v为头的弧的数目称为出度;以v为尾的弧的数目称为入度。连通图、强连通子图(分量)无向图的生成树......无向图及其生成树V3V2V4V1V6V5V3V2V4V1V6V5V3V2V4V1V6V5无向图G有向图及其强连通子图54613241510215203041010132415220546图2图2的强连通子图图的邻接矩阵表示

3、8273496221V32V2V4V1V6V5∞8∞7498∞21∞∞∞2∞3∞2713∞∞24∞2∞∞69∞226∞123456123456图1图1的邻接矩阵图的邻接链表表示8273496221V32V2V4V1V6V5表头顶点的邻接顶点编号和边相关的信息指向下一个邻接顶点的指针(a)表结点结构(b)图1的邻接链表12345628546947∧183241∧22526243∧17213362∧146632∧19425632∧V1V2V3V4V5V6图1图的算法基本算法遍历算法求最小生成树的算法求最短路径的算法拓扑排序算法关键路径求解算法......其他算法连通性问题及求解算法匹

4、配问题及算法网络流问题及算法…例3：Isitatree?Atreeisawell-knowndatastructurethatiseitherempty(null,void,nothing)orisasetofoneormorenodesconnectedbydirectededgesbetweennodessatisfyingthefollowingproperties.Thereisexactlyonenode,calledtheroot,towhichnodirectededgespoint.//入度为0Everynodeexcepttheroothasexactlyone

5、edgepointingtoit.//除根之外结点的入度为1Thereisauniquesequenceofdirectededgesfromtheroottoeachnode.//根到每个结点有唯一路径例3：Isitatree?7345681928345623412189375264(a)(b)(c)例4：学校网络Anumberofschoolsareconnectedtoacomputernetwork.Agreementshavebeendevelopedamongthoseschools:eachschoolmaintainsalistofschoolstowhichit

6、distributessoftware(the"receivingschools").NotethatifBisinthedistributionlistofschoolA,thenAdoesnotnecessarilyappearinthelistofschoolB.54231Youaretowriteaprogramthatcomputestheminimalnumberofschoolsthatmustreceiveacopyofthenewsoftwareinorderforthesoftwaretoreachallschoolsinthenetworkaccording

7、totheagreement(SubtaskA).431每个强连通分量抽象为一个顶点例4：学校网络(续)431Asafurthertask,wewanttoensurethatbysendingthecopyofnewsoftwaretoanarbitraryschool,thissoftwarewillreachallschoolsinthenetwork.Toachievethisgoalwemayhavetoextendthelistsofreceiversbynewmem