数据结构 第7章 图.ppt

7.1图的定义和术语 7.2图的存储结构 7.3图的遍历 7.4图的连通性问题 7.5有向无环图及其应用 7.6最短路径 7.1 图的定义和术语 基本术语 完全图 在具有n 个顶点的有向图中最大弧数为 n(n-1) 在具有n 个顶点的无向图中最大边数为 n(n-1)/2 顶点的度 无向图与该顶点相关的边的数目 有向图 入度ID(v) 以该顶点为头的弧的数目 出度OD(v) 以该顶点为尾头的弧的数目