0467.cC
海量文库 文档专家
当前位置:首页 >> >>

数据结构实用教程第6章 图_图文

数据结构实用教程(C语言版) 第6章 图 本章中介绍下列主要内容: ?图的定义 ?图的存储结构 ?图的遍历操作 ?图的几个典型问题 本章目录 1 6.1 图的基本概念 2 6.2 图的存储结构 3 6.3 图的遍历 4 6.4 最小生成树 5 6.5 拓扑排序 6 6.6 AOE网与关键路径 7 6.7 最短路径问题 8 6.8 本章小结 结束 6.1 图的基本概念 ?6.1.1 图的定义 ?6.1.2 图的基本术语 ?6.1.3 图的基本操作 返回到总目录 6.1.1 图的定义 ? 图是由一个非空的顶点集合和一个描述顶点 之间关系即边(或者弧)的集合组成,它可 以定义为一个二元组: ? G=(V,E) ? 其中,G表示一个图,V表示图G中全部顶点 组成的非空集合,E是图G中全部边组成的 集合。 ? 按照图中边是否有方向性,图分为有向图和 无向图两类。图6-1(a)表示的是无向图, 图6-1(b)表示的是有向图。 返回到本节目录 有向图和无向图的示例 V1 V2 V3 V4 V5 V1 V2 V3 V4 (a)无向图G1 图6-1 图的类型 (b)有向图G2 返回到本节目录 有向图和无向图的边的表示 ? 在无向图中,用圆括号表示两个顶点之间的 边。(vi,vj)表示顶点vi和顶点vj 之间连线 表示的边。 ? 若图中边有方向,则用尖括号表示两个顶点 之间的首尾关系,有向边也称为弧。在有向 边<vi,vj>中,vi称为弧尾,vj称为弧头。 返回到本节目录 6.1.2 图的基本术语 ? 1.无向图(Undigraph) ? 在一个图中,如果每条边都没有方向(如图 6-1(a)所示),则称该图为无向图。 ? 2.有向图(Digraph) ? 在一个图中,如果每条边都有方向(如图6- 1(b)所示),则称该图为有向图。 ? 3.无向完全图 ? 在一个无向图中,如果任意两顶点都有一条 直接边相连接,则称该图为无向完全图。如 图6-2(a),可以证明,在一个含有n个顶 点的无向完全图中,有n(n-1)/2条返边回到。本节目录 6.1.2 图的基本术语 ? 4.有向完全图 ? 在一个有向图中,如果任意两顶点之间都有 方向互为相反的两条弧相连接,则称该图为 有向完全图。如图6-2(b),在一个含有n 个顶点的有向完全图中,有n(n-1)条弧。 ? 5.顶点的度、入度、出度 ? 在无向图中:一个顶点拥有的边数,称为该 顶点的度。记为TD(v)。 返回到本节目录 6.1.2 图的基本术语 ? 在有向图中: ? (a)一个顶点拥有的弧头的数目,称为 该顶点的入度,记为ID(v); ? (b)一个顶点拥有的弧尾的数目,称为 该顶点的出度,记为OD(v); ? (c)一个顶点度等于顶点的入度+出度, 即:TD(v)=ID(v)+OD(v)。 返回到本节目录 6.1.2 图的基本术语 ? 6.权 ? 图的边或弧有时具有与它有关的数据信息, 这个数据信息就称为权(Weight)。 ? 7.网——边(或弧)上带权的图称为网 (Network)。 ? 如果每一条边都有与它相关的数,称为权, 我们将这种带权的图叫做网。 ? 如果图中边是无方向的带权图,则图是一个 无向网;如果图中边是有方向的带权图,则 就是一个有向网。 返回到本节目录 6.1.2 图的基本术语 ? 8.路径、路径长度 ? 顶点vi到顶点vj之间的路径是指顶点序列vi, vk1,vk2,…,vkm,vj.。其中: (vi,vk1),(vk1,vk2),…,(vkm,.vj)分 别为图中的边。路径上边或弧的数目称为路 径长度。 ? 在图6-1(a)的无向图G1中, v1→v3→v4→v5与v1→v2→v5是从顶点v1 到顶点v5 的两条路径,路径长度分别为3和 2。 返回到本节目录 6.1.2 图的基本术语 ? 9.回路或环 ? 在一个路径中,若其第一个顶点和最后一个 顶点是相同的,则称该路径为一个回路或环。 ? 10.简单路径 ? 若表示路径的顶点序列中的顶点各不相同, 则称这样的路径为简单路径。如图6-1(a) 中的v1→v3→v4。 ? 11.简单回路 ? 除了第一个和最后一个顶点外,其余各顶点 均不重复出现的回路为简单回路。 返回到本节目录 6.1.2 图的基本术语 ? 12.稀疏图 ? 对于有很少条边的图(e<nlog2n,e为边数, n为顶点数)称为稀疏图,反之称为稠密图。 ? 13.子图 ? 对于图G=(V,E),G′=(V′,E′),若 存在V′是V的子集 ,E′是E的子集 ,则称图 G′是G的一个子图。 ? 14.连通图、连通分量 ? 在无向图中,如果从一个顶点vi到另一个顶 点vj(i≠j)有路径,则称顶点vi和vj是连通的。 任意两顶点都是连通的图称为连通图。无向 图的极大连通子图称为连通分量。 返回到本节目录 6.1.2 图的基本术语 ? 15.强连通图、强连通分量 ?对于有向图来说,若图中任意一对顶点vi 和 vj(i≠j)均有从一个顶点vi到另一个顶点vj有 路径,也有从vj到vi的路径,则称该有向图 是强连通图。有向图的极大强连通子图称为 强连通分量。 ? 16.生成树 ? 连通图G的一个子图如果是一棵包含G的所 有顶点的树,则该子图称为G的生成树 (Spanning Tree)。在生成树中添加任 意一条属于原图中的边必定会产生回路,n个 顶点的生成树具有n-1条边。 返回到本节目录 6.1.3 图的基本操作 ? 图的基本操作有: ? (1)CreatGraph(G):输入图G的顶点 和边,建立图G的存储。 ? (2)DFSTraverse(G,v):在图G中, 从顶点v出发深度优先遍历图G。 ? (3)BFSTtaverse(G,v):在图G中, 从顶点v出发广度优先遍历图G。 返回到本节目录 6.2 图的存

网站首页 | 网站地图
All rights reserved Powered by 0467资源网 0467.cc
copyright ©right 2014-2019。
文档资料库内容来自网络,如有侵犯请联系客服。liunxqq@126.com