《数据结构》课程教学资源（PPT课件讲稿）第七章 图 Graph

第七章图( Graph) 2007.9

第七章 图 (Graph) 2007.9

主要内容 71图的基本概念 72图的存储结构 73图的遍历 74生成树和最小生成树

主要内容 7.1 图的基本概念 7.2 图的存储结构 7.3 图的遍历 7.4 生成树和最小生成树

7.1图的基本概念

7.1 图的基本概念

1.图的定义 图G由两个集合构成,记作G=其中 V( vertex)是顶点的非空有限集合 E(edge)是边的有限集合,而边是顶点对的集合。 VO V2 V3 V4 G1= V1={vo,v1,V2,w3,v4 E1={(vo,V1),(vo,vy3),(v1,V2),(v,v4),(v2,v3)(v2,v)}

1. 图的定义 G1= V1={v0 ,v1,v2,v3,v4} E1={(v0,v1),(v0,v3),(v1,v2),(v1,v4),(v2,v3)(v2,v4)} V0 V3 V4 V1 V2 • 图G由两个集合构成，记作G= 其中: • V（vertex）是顶点的非空有限集合 • E（edge）是边的有限集合，而边是顶点对的集合

图的应用举例: 例1交通图(公路、铁路) 顶点:地点 边:连接地点的公路 交通图中的有单行道双行道,分别用有向边、无向边表示; 例2电路图 顶点:元件 边:连接元件之间的线路 例3通讯线路图 顶点:地点 边:地点间的连线 例4各种流程图 如产品的生产流程图 顶点:工序 边:各道工序之间的顺序关系

例1 交通图（公路、铁路） 顶点：地点 边：连接地点的公路 交通图中的有单行道双行道，分别用有向边、无向边表示； 例2 电路图 顶点：元件 边：连接元件之间的线路 例3 通讯线路图 顶点：地点 边：地点间的连线 例4 各种流程图 如产品的生产流程图 顶点：工序 边：各道工序之间的顺序关系 图的应用举例：

2图的基本术语 VO 有向图、无向图 有向边(弧)、弧尾、弧头 无向边(边) V4 ●完全图:总边数 有向完全图、无向完全图 子图 ●路径、路径长度 V3) ●简单路径、简单回路 ●连通图、连通分量、强连通图 网络:带权的图

2. 图的基本术语  有向图、无向图  有向边（弧）、弧尾、弧头  无向边（边）  完全图：总边数  有向完全图、无向完全图：  子图  路径、路径长度  简单路径、简单回路  连通图、连通分量、强连通图  网络：带权的图 V0 V3 V4 V1 V2 V0 V1 V2 V3

●邻接点、相邻接、边与顶点关联 无向图中顶点的度 VO 有向图中顶点的度=入度+出度 ●生成树、生成林 V V4) VO V V3

 邻接点、相邻接、边与顶点关联  无向图中顶点的度  有向图中顶点的度＝入度+出度  生成树、生成林 V0 V3 V4 V1 V2 V0 V1 V2 V3

有向边(弧)、弧尾、弧头;无向边(边) 无向图在图G中,若所有边是无向边 有向图在图G中,若所有边是有向边 混和图:在图G中,即有无向边也有有向边 完全图 无向完全图:任意两顶点间都有边的图。 在一个含有n个顶点的无向完全图中,有n(n-1)/2条边。 有向完全图任意两顶点之间都有方向互为相反的两条弧相连 接的有向图。 。在一个含有n个顶点的有向完全图中,有n(m-1)条弧。 v2)

V0 V3 V4 V1 V2 V0 V1 V2 V3  有向边（弧）、弧尾、弧头；无向边（边）  无向图:在图G中，若所有边是无向边  有向图:在图G中，若所有边是有向边  混和图：在图G中，即有无向边也有有向边  完全图：  无向完全图：任意两顶点间都有边的图。  在一个含有n个顶点的无向完全图中，有n(n-1)/2条边。  有向完全图:任意两顶点之间都有方向互为相反的两条弧相连 接的有向图。  在一个含有n个顶点的有向完全图中，有n(n-1)条弧

邻接点:边的两个顶点 关联边:若边e=(v,u),则称顶点v、u 关联边 顶点的度 在无向图中,顶点V的度=与V相关联的 边的数目,记作TD() 在有向图中,顶点V的度=V的出度+的入 度 顶点V的出度以V为起点有向边数 顶点V的入度=以V为终点有向边数

 邻接点：边的两个顶点  关联边：若边e= (v, u), 则称顶点v、u 关联边  顶点的度  在无向图中,顶点V的度 = 与V相关联的 边的数目，记作TD(V)  在有向图中,顶点V的度= V的出度+V的入 度  顶点V的出度=以V为起点有向边数  顶点V的入度=以V为终点有向边数

V2 v4 V3 顶点度 顶点入度出度度 VO V01 V2 V3 23322 V2 111 2 V3 V4

V0 V3 V4 V1 V2 V0 V1 V2 V3 顶点 入度 出度 度 V0 1 2 3 V1 1 0 1 V2 1 1 2 V3 1 1 2 顶点 度 V0 2 V1 3 V2 3 V3 2 V4 2