数据结构与算法 第六章 图

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

1、数据结构与算法第六章图张铭赵海燕王腾蛟http://db.pku.edu.cn/mzhang/DS/北京大学信息科学与技术学院“数据结构与算法”教学小组©版权所有，转载或翻印必究主要内容¢6.1图的基本概念¢6.2图的抽象数据类型¢6.3图的存储结构¢6.4图的周游（深度、广度、拓扑）¢6.5最短路径问题¢6.6最小支撑树北京大学信息学院©版权所有，转载或翻印必究Page26.1图的基本概念¢习惯上，常用G=（V，E）代表一个图¢V是顶点（vertex）集合¢E是边（edge）的集合¢边的始点¢边的终点¢稀疏图（sparsegraph）¢密集图（densegraph）¢完全图（co

2、mpletegraph）北京大学信息学院©版权所有，转载或翻印必究Page36.1图的基本概念（续）¢无向图（undirectedgraph）¢图中代表一条边的顶点的偶对无方向性，也即无序¢有向图（directedgraph或digraph）¢图中代表一条边的顶点的偶对是有序的北京大学信息学院©版权所有，转载或翻印必究Page46.1图的基本概念（续）无向图示例有向图示例北京大学信息学院©版权所有，转载或翻印必究Page56.1图的基本概念（续）¢标号图（labeledgraph）¢带权图（weightedgraph）北京大学信息学院©版权所有，转载或翻印必究Page66.1图的基

3、本概念（续）¢顶点的度（degree）¢与该顶点相关联的边的数目¢入度(indegree)¢出度(outdegree)¢子图（subgraph）¢图G=(V，E)，G’=(V’，E’)中，若V’≤V，E’≤E，并且E’中的边所关联的顶点都在V’中，则称图G’是图G的子图北京大学信息学院©版权所有，转载或翻印必究Page76.1图的基本概念（续）¢路径（path）¢在图G=(V，E)中，如果存在顶点序列V，pV，V，…，V，V，使得（V，V），i1i2inqpi1(V，V)，…，(V，V)（若对有向图，i1i2inq则使得，，…，pi1i1i2）都在E中

4、，则称从顶点Vp到顶inq点Vq存在一条路径。¢简单路径（simplepath）¢路径长度（length）北京大学信息学院©版权所有，转载或翻印必究Page86.1图的基本概念（续）¢回路（cycle，也称为环）¢无向图中，如果两个结点之间有平行边，容易让人误看作“环”）路径长度大于等于3¢有向图两条边可以构成环，例如和构成环。10¢简单回路（simplecycle）¢无环图（acyclicgraph）¢有向无环图（directedacyclicgraph，简写为DAG）北京大学信息学院©版权所有，转载或翻印必究Page96.1图的基本概念（续）¢有根的图¢

5、一个有向图中，若存在一个顶点V0，从此顶点有路径可以到达图中其它所有顶点，则称此有向图为有根的图，V称作图的根。0¢树、森林¢连通的（connected）¢对无向图G=（V，E）而言，如果从V1到V2有一条路径（从V到V也一定有一条路径），则21称V和V是连通的（connected）。12¢强连通北京大学信息学院©版权所有，转载或翻印必究Page106.1图的基本概念（续）¢连通分支或者连通分量（connectedcomponent）¢无向图的最大连通子图¢强连通分支（强连通分量）¢网络¢带权的连通图¢自由树（freetree）¢不带有简单回路的无向图，它是连通的，并且具有

6、V

7、-

8、1条边北京大学信息学院©版权所有，转载或翻印必究Page116.2图的抽象数据类型¢结点、边怎么表示？¢结点：增？、删、查?、改¢边：增、删、查?、改北京大学信息学院©版权所有，转载或翻印必究Page126.2图的抽象数据类型classGraph{//图的ADTpublic:intVerticesNum();//返回图的顶点个数intEdgesNum();//返回图的边数//返回与顶点oneVertex相关联的第一条边EdgeFirstEdge(intoneVertex);//返回与边PreEdge有相同关联顶点oneVertex的//下一条边EdgeNextEdge(Edgepr

9、eEdge);北京大学信息学院©版权所有，转载或翻印必究Page13//添加一条边boolsetEdge(intfromVertex,inttoVertex,intweight);//删一条边booldelEdge(intfromVertex,inttoVertex);//如果oneEdge是边则返回TRUE，否则返回FALSEboolIsEdge(EdgeoneEdge);//返回边oneEdge的始点intFromVertex(EdgeoneEdge);//返回边