数据结构与算法第六章图

《数据结构与算法第六章图》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、数据结构与算法第六章图任课教员：张铭http://db.pku.edu.cn/mzhang/DS/mzhang@db.pku.edu.cn北京大学信息科学与技术学院网络与信息系统研究所©版权所有，转载或翻印必究主要内容¢6.1图的基本概念¢6.2图的抽象数据类型¢6.3图的存储结构¢6.4图的周游（深度、广度、拓扑）¢6.5最短路径问题¢6.6最小支撑树北京大学信息学院©版权所有，转载或翻印必究Page26.1图的基本概念¢G=（V，E）表示¢V是顶点（vertex）集合¢E是边（edge）的集合¢边的始点¢边的终点¢稀疏图（sparsegraph）¢密集图（densegraph）¢

2、完全图（completegraph）北京大学信息学院©版权所有，转载或翻印必究Page3无向图¢边涉及顶点的偶对无序¢实际上是双通北京大学信息学院©版权所有，转载或翻印必究Page4有向图¢有向图（directedgraph或digraph）¢边涉及顶点的偶对是有序的北京大学信息学院©版权所有，转载或翻印必究Page5¢标号图（labeledgraph）¢带权图（weightedgraph）北京大学信息学院©版权所有，转载或翻印必究Page6顶点的度（degree）¢与该顶点相关联的边的数目¢入度(indegree)¢出度(outdegree)北京大学信息学院©版权所有，转载或翻印必

3、究Page7子图（subgraph）¢图G=(V，E)，G’=(V’，E’)中，若V’≤V，E’≤E，并且E’中的边所关联的顶点都在V’中，则称图G’是图G的子图北京大学信息学院©版权所有，转载或翻印必究Page8路径（path）Vp¢从顶点Vp到顶点Vq的路径¢顶点序列V，V，V，…，pi1i2V，V，使得（V，V），inqpi1(V，V)，…，(V，V)（若i1i2inq对有向图，则使得，，…，i1i1i2）都在E中inq¢简单路径（simplepath）Vq¢路径长度（length）北京大学信息学院©版权所有，转载或翻印必究Page9回路（cyc

4、le，也称为环）¢无向图中，如果两个结点之间有平行边，容易让人误看作“环”）¢路径长度大于等于3¢有向图两条边可以构成环，例如01和构成环10V0√╳√√V1北京大学信息学院©版权所有，转载或翻印必究Page10¢简单回路（simplecycle）¢无环图（acyclicgraph）¢有向无环图（directedacyclicgraph，简写为DAG）北京大学信息学院©版权所有，转载或翻印必究Page11有根图¢一个有向图中，若存在一个顶点V，从此顶点有路径可以到达图0中其它所有顶点，则称此有向图为有根的图，V称作图的根0¢树、森林北京大学信息学院©版权所有，转载

5、或翻印必究Page12连通图¢对无向图G=（V，E）而言，如果从V到V有一条路径（从V122到V也一定有一条路径），则称1V和V是连通的12（connected）¢强连通北京大学信息学院©版权所有，转载或翻印必究Page13连通分支或者连通分量¢无向图的最大连通子图¢强连通分支（强连通分量）v0v5北京大学信息学院©版权所有，转载或翻印必究Page14网络¢带权的连通图北京大学信息学院©版权所有，转载或翻印必究Page15自由树（freetree）¢不带有简单回路的无向图，它是连通的，并且具有

6、V

7、-1条边北京大学信息学院©版权所有，转载或翻印必究Page166.2图的抽象数据类型¢

8、结点、边怎么表示？¢结点：增？、删、查?、改¢边：增、删、查?、改北京大学信息学院©版权所有，转载或翻印必究Page17classGraph{//图的ADTpublic:intVerticesNum();//返回图的顶点个数intEdgesNum();//返回图的边数//返回与顶点oneVertex相关联的第一条边EdgeFirstEdge(intoneVertex);//返回与边PreEdge有相同关联顶点oneVertex的//下一条边EdgeNextEdge(EdgepreEdge);北京大学信息学院©版权所有，转载或翻印必究Page18//添加一条边boolsetEdge(i

9、ntfromVertex,inttoVertex,intweight);//删一条边booldelEdge(intfromVertex,inttoVertex);//如果oneEdge是边则返回TRUE，否则返回FALSEboolIsEdge(EdgeoneEdge);//返回边oneEdge的始点intFromVertex(EdgeoneEdge);//返回边oneEdge的终点intToVertex(EdgeoneEdge);//返回边oneEdge的