第八章 图 .ppt

1、第八章 图 图的基本概念 图的存储结构 图的遍历与连通性 最小生成树 最短路径 活动网络1图的基本概念 图定义 图是由顶点(vertex)集合以及顶点之间的关系集合组成的一种数据结构：G( V, E ) 其中 V = x | x 某个数据对象 是顶点的有穷非空集合；E = (x, y) | x, y V 或 E = | x, y V 顶点 v 的出度是以 v 为始点的有向边的条数, 记作 outdeg(v)。在有向图中, 顶点的度等于该顶点的入度与出度之和。 路径 在图 G(V, E) 中, 若从顶点 vi 出发, 沿一些边经过若干顶点 vp1, vp2, , vpm，到达顶点vj，则称顶点序

2、列 (vi , vp1 , vp2 , . , vpm , vj) 为从顶点vi 到顶点 vj 的一条路径。它经过的边(vi, vp1)、(vp1, vp2)、.、(vpm, vj) 都是 于E的边。5 路径 度 非带权图的路径 度是 此路径边的条数。带权图的路径 度是 路径 边的权值之和。 单路径 若路径 顶点 v1, v2, ., vm 互相重 , 则称 的路径为 单路径。 路 若路径 第一个顶点 v1 与最 一个顶点vm 重合, 则称 的路径为 路或 。601 2301 2301 23 连通图与连通 在无向图中, 若从顶点v1到顶点v2有路径, 则称顶点v1与v2是连通的。如果图中 一对

3、顶点都是连通的, 则称此图是连通图。非连通图的 连通子图叫做连通 。 连通图与 连通 在有向图中, 若对于 一对顶点vi和vj, 都存在一条从vi到vj和从vj到vi的路径, 则称此图是 连通图。非 连通图的 连通子图叫做 连通 。 生成树(spanning tree) 一个无向连通图的生成树是其 小连通子图，在 n 个顶点的 ，有 n-1 条边。若是有向图，则 到它的由若干有向树组成的生成 。 7图的 象数据 class Graph / 象对 : 由一 非空 点集合和一 集合 成个 顶 个边 构/ 每 由一 点 表示。条边 个顶 对来public:Graph(); / 建立一 空的个 图vo

4、id insertVertex (const T/ 入一 点插 个顶 vertex, 点 有入该顶 暂时没 边void insertEdge (int v1, int v2, int weight);/ 在 中 入一图 插 条边(v1, v2, w)void removeVertex (int v);/ 在 中 除 点图 删 顶 v和所有 到 的关联 它 边 8void removeEdge (int v1, int v2);/ 在 中 去图 删 边(v1,v2)bool IsEmpty();/ 若 中 有 点图 没 顶 , 返回则 true, 否 返回则falseT getWeight (int v1, int v2);/ 函 返回数 边 (v1,v2) 的权值int getFirstNeighbor (int v);/ 出 点 给 顶 v 第一 接 点的位置个邻 顶int getNextNeighbor (int v, int w);/ 出 点 给 顶 v 的某 接 点 邻 顶 w 的下一个接 点邻 顶; 9图的存储表示 图的基 在 定义中的数据 数表 中，T是顶点数据的 ，E是边 数据的 。 个基 是currency1最 的 “带权无向图 定义的，如果fifl 非带权图， 数据 数表 为 。 如果 的是有向图，也 以对序做相的动。 10