数据结构与算法第六章图ppt

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

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

2、aph）¢密集图（densegraph）¢完全图（completegraph）北京大学信息学院©版权所有，转载或翻印必究Page3北京大学信息学院©版权所有，转载或翻印必究Page4有向图¢有向图（directedgraph或¢标号图（labeledgraph）digraph）¢带权图（weightedgraph）¢边涉及顶点的偶对是有序的北京大学信息学院©版权所有，转载或翻印必究Page5北京大学信息学院©版权所有，转载或翻印必究Page61顶点的度（degree）子图（subgraph）¢与该顶点相关联的边的数目¢图G=(V，E)，G’=(V’，E’)中，若V’≤V，E’≤E，并

3、且E’中的边所关联的顶点都在V’¢入度(indegree)中，则称图G’是图G的子图¢出度(outdegree)北京大学信息学院©版权所有，转载或翻印必究Page7北京大学信息学院©版权所有，转载或翻印必究Page8路径（path）回路（cycle，也称为环）Vp¢无向图中，如果两个结点之间有平行边，¢从顶点Vp到顶点Vq的路径容易让人误看作“环”）¢顶点序列V，V，V，…，pi1i2V，V，使得（V，V），¢路径长度大于等于3inqpi1(V，V)，…，(V，V)（若i1i2inq¢有向图两条边可以构成环，例如对有向图，则使得构成环V>，

4、，…，10i1i1i2）都在E中V0inq¢简单路径（simplepath）Vq¢路径长度（length）√╳√√V1北京大学信息学院©版权所有，转载或翻印必究Page9北京大学信息学院©版权所有，转载或翻印必究Page10有根图¢简单回路（simplecycle）¢一个有向图中，若存在一个顶点V0，从此顶点有路径可以到达图¢无环图（acyclicgraph）中其它所有顶点，则称此有向图¢有向无环图（directedacyclic为有根的图，V0称作图的根graph，简写为DAG）¢树、森林北京大学信息学院©版权所有，转载或翻印必究Page11北京大学信息学院©版权所有，转

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

6、V

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

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

9、e(intfromVertex,inttoVertex,intweight);6.3图的存储结构//删一条边booldelEdge(intfromVertex,inttoVertex);//如果oneEdge是边则返回TRUE，否则返回FALSE¢6.3.1图的相邻矩阵boolIsEdge(EdgeoneEdge);（adjacencymatrix）表示法//返回边oneEdge的始点intFromVertex(EdgeoneEdge);¢6.3.2图的邻