第7章图 7.1 图的基本概念《算法与数据结构（C＆Java）（第2版）》 同步教学（电子工业出版社）

6学科网 WWw.ZXXK.COM 第7章 图 7.1图的基本概念 7.2图的存结构 7.3图的逼历 7.4图的连通性问题 7.5有向无环图及其应用 7.6最短路径 6学科网 第7章 图 WWw.ZXXK.COM 主要内容 1、图的基本概念 2、图的存储结构（邻接矩阵、邻接表）； 3、图的逼历（深度优先搜索、广度优先搜索） 4、最小生成树(kruskul:算法、prim算法) 5、最短路径(dijkstra算法、floyd算法)； 6、AOV网络与拓扑排序； 7、AOE网络与关键路径。 o6学科网 Www.ZXXK 图(Graph)是一种较线性表和树更为复杂的数据结构。在线性 表中，数据元素之间仅有线性关系，即每个数据元素只有一个直 接前驱和一个直接后继；在树形结构中，数据元素之间有着明显 的层次关系，虽然每一层上的数据元素可能和下一层中多个元素 (孩子)相关，但只能和上一层中一个元素（双亲）相关；而在 图形结构中，结点之间的关系可以是任意的， 任意两个 数据元素之间都可能相关。 图在各个领域都有着广泛的应用，如电路网络分析、交通运输、管 理与线路的铺设、印刷电路板与集成电路的布线等众多直接与图 有关的问题，它们必须用图的有关方法进行处理；另外像工作的 分配、工程进度的安排、课程表的制订、关系数据库的设计等许 多实际问题，如果间接地用图来表示，处理起来比较方便。这些 技术领域都是把图作为解决问题的主要数学手段来使用。 6学科网 Www.ZXXK.COM 7.1 图的基本概念 7.1.1 图的定义 图G是由顶点集V和顶点间的关系集合E(边的 集合)组成的一种数据结构，可以用二元组定 义为： G=(V,E) 6学科网 例如，对于图7-1所示的无向图G1和有向图G2, 它们的数据结 构可以描述为：G1=(V1,E1)以及G2=(V2,E2)。 其中V1={a,b,c,d},E1={(a,b),(a,c),(a,d),(b,d),(c,d)} 其中V2={1,2,33,E2={<1,2>,<1,3>,<2,3>,<3,1>} 。 2 a d (a) 无向图G1 (b)有向图G2 图7-1 无向图和有向图 学科网 7.1.2 图的基本术语 WWw.ZXXK.COM 1.有向图和无向图 在图中，若用箭头标明了边是有方向性的，则称这样的图为有向 图，否则称为无向图。在无向图中，一条边（X,y)与(y,x)表 示的结果相同，用圆括号表示，在有向图中，一条边<X,y>与 <y,x>表示的结果不相同，故用尖括号表示。<X,y>表示从顶点x 发向顶点y的边，为始点，y为终点。有向边也称为弧，x为弧 尾，y为弧头，则<Xy>表示为一条弧，而<y,x>表示y为弧尾，为弧 头的另一条弧。 2. 完全图、稠密图、稀疏图 具有n个顶点，n(n-1)/2条边的图， 称为完全无向图，具有n个 顶点，n(n-1)条弧的有向图，称为完全有向图。完全无向图和完 全有向图都称为完全图。 对于一般无向图，顶点数为n,边数为e, 则响科网 n(m-1)/2。 对于一般有向图，顶点数为n, 弧数为e,则0≤e≤n(n-1) 当一个图接近完全图时，则称它为稠密图，相反地，当一个图中 含有较虔的边裘划驻度则称它为稀疏图。 在图中，一个顶点依附的边或孤的数目，称为该顶点的度。在 有向图中，一个顶点依附的孤头数目，称为该顶点的入度。一个 顶点依附的弧尾数目，称为该顶点的出度，某个顶点的入度和 出度之和称为该顶点的度。则一定有以下公式 a片=ac 为入度，c为出度 1 1 另外，若图中有n个顶点，e条边或弧，第i个顶点的度为d,则 有：e= i- 6学科网 WWw.ZXXK.COM 端点和邻接点 在一个无向图中，若存在一条边(vi),则称vi和j为此边的 两个端点，并称它们互为邻接点(adjacent)。 在一个有向图中，若存在一条边<vi,Vj>,则称vi和vj为此边 的起始端点和终止端点，称它们互为邻接点(adjacent),称vj 为Vi得出边邻接点，vi为Vj的入边邻接点。 6学科网 4.子图 WWw.ZXXK.COM 若有两个图G1和G2,G1=(V1,E1),> G2=V2,E2). 满足如下条件：V2V1，E2E1,即V2为V1的子集， E2为E1的子集，称图G2为图G1的子图。 图和子图的示例具体见图7-2。 3 3 (a)图G (b)图G的两个子图 图7-2 图与子图示意 6学科网 5.权 WWw.ZXXK.COM 在图的边或弧中给出相关的数， 称为权。权可以代表一个顶点 到另一个顶点的距离，耗费等，带权图一般称为网。 带权图的示例具体见图7-3。 2 A 3 7 (a)无向网 (b)有向网 图7-3无向带权图和有向带权图