基本概念基本概念 图的存储结构图的存储结构 图的遍历图的遍历 生成树生成树 最短路径最短路径 拓扑排序拓扑排序第第 77 章 图章 图 7.1 7.1 图的基本概念图的基本概念图定义图定义 图是由顶点集合图是由顶点集合 (vertex) 及顶点间的关系及顶点间的关系集合组成的一种数据结构集合组成的一种数据结构： GraphGraph ＝＝ ( ( VV, , E E )) 其中 其中 VV = { = { xx | | x x 某个数据对象某个数据对象 } } 是顶点的有是顶点的有穷穷非空集合；非空集合； EE = {( = {(xx, , yy) |) | x x, , y y V V }} 是顶点之间关系的有穷集合，也叫做边是顶点之间关系的有穷集合，也叫做边 (edge)(edge) 集集合。合。 有向图与无向图有向图与无向图 若图 若图 GG 中的每条边都是有中的每条边都是有方向的，则称方向的，则称 GG 为有向图。有向边也称为为有向图。有向边也称为弧弧。。若图若图 GG 中的每条边都是没有方向的，则称中的每条边都是没有方向的，则称 GG为无向图。为无向图。 完全图完全图 对有 对有 nn 个顶点的图，若为无向图且个顶点的图，若为无向图且边数为边数为 n(n-1)/2n(n-1)/2 ，则称其为，则称其为无向完全图无向完全图；；若为有向图且边数为若为有向图且边数为 n(n-1) n(n-1) ，则称其为，则称其为有有向完全图。向完全图。 邻接顶点邻接顶点 若（ 若（ vvii,v,vjj ）是一条无向边，则称）是一条无向边，则称顶点顶点 vvii 和和 vvjj 互为邻接点，或称互为邻接点，或称 vvii 和和 vvjj 相邻相邻接，并称边（接，并称边（ vvii,v,vjj ）关联于顶点）关联于顶点 vvii 和和 vvjj ，，或称（或称（ vvii,v,vjj ）与顶点）与顶点 vvii 和和 vvjj 相关联。 相关联。 顶点的度顶点的度 一个顶点 一个顶点 vv 的度是与它相关联的边的的度是与它相关联的边的条数。记作条数。记作 TD(TD(vv)) 。。顶点 顶点 v v 的入度的入度 是以 是以 v v 为终点的有向边的条数为终点的有向边的条数 , , 记作 记作 ID(v); ID(v); 顶点 顶点 v v 的出度的出度是以 是以 v v 为始点的有向边的条为始点的有向边的条数数 ,, 记作 记作 OD(v)OD(v) 。。子图子图 设有两个图 设有两个图 GG ＝＝ (V, E) (V, E) 和 和 G’G’ ＝＝ (V’, E’)(V’, E’) ...
