24/12/271第第77章图章图本章主题：本章主题：图的基本概念、图的存储结构和图的常用算法教学目的：教学目的：教学重点：教学重点：图的各种存储方式及其运算教学难点：教学难点：图结构存储方式的选择，几种经典图算法的实现本章内容本章内容：：图的基本概念图的存储结构图的遍历最小生成树最短路径拓扑排序关键路径24/12/272本章主要介绍图的基本概念、图的存储结构和有关图的一些常用算法。通过本章学习，读者应该：1)了解图的定义和术语2)掌握图的各种存储结构3)掌握图的深度优先搜索和广度优先搜索遍历算法4)理解最小生成树、最短路径、拓扑排序、关键路径等图的常用算法本章学习导读本章学习导读24/12/273图（Graph）是一种较线性表和树更为复杂的非线性结构。是对结点的前趋和后继个数不加限制的数据结构，用来描述元素之间“多对多”的关系。在线性结构中，结点之间的关系是线性关系，除开始结点和终端结点外，每个结点只有一个直接前趋和直接后继。在树形结构中，结点之间的关系实质上是层次关系，同层上的每个结点可以和下一层的零个或多个结点（即孩子）相关，但只能和上一层的一个结点（即双亲）相关（根结点除外）。在图结构中，对结点（图中常称为顶点）的前趋和后继个数不加限制的，即结点之间的关系是任意的。由此，图的应用极为广泛，特别是近年来的迅速发展，已渗透到诸如语言学、逻辑学、物理、化学、电讯工程、计算机科学以及数学的其它分支中。24/12/27477.1.1.1.1图的定义图的定义图图是由一个顶点集是由一个顶点集VV和一个弧集和一个弧集RR构成的数据结构。构成的数据结构。Graph=(V,R)Graph=(V,R)VV={={xx||xx某个数据对象某个数据对象}}，是顶点的有穷非空集合；，是顶点的有穷非空集合；R——R——边的有限集合边的有限集合RR={(={(xx,,yy)|)|xx,,yyVV}}无向图或无向图或RR={<={y>||xx,,yyVV&&&&PathPath((xx,,yy)})}有向图有向图是顶点之间关系的有穷集合，也叫做是顶点之间关系的有穷集合，也叫做边边((edge)edge)集集合合。。PathPath((xx,,yy))表示从表示从xx到到yy的一条单向通路的一条单向通路,,它是有方向的。它是有方向的。xx弧尾，弧尾，yy弧头弧头。。77.1.1图及其基本运算图及其基本运算24/12/275有向图与无向图有向图与无向图有向图中：边用有向图中：边用<x,y>表示，且表示，且xx与与yy是有序的。是有序的。a.a.有向图中的边称为“弧”有向图中的边称为“弧”b.x——b.x——弧尾或初始点弧尾或初始点y——y——弧头或终端点弧头或终端点无向图：边用无向图：边用((x,y)x,y)表示，且顶表示，且顶xx与与yy是无序的。是无序的。完全图完全图在具有在具有nn个顶点的有向图中，最大弧数为个顶点的有向图中，最大弧数为nn((nn-1)-1)在具有在具有nn个顶点的无向图中，最大边数为个顶点的无向图中，最大边数为nn((nn-1)/2-1)/2顶点的度顶点的度无向图：与该顶点相关的边的数目无向图：与该顶点相关的边的数目有向图：有向图：入度入度ID(ID(vv))：：以该顶点为头的弧的数目以该顶点为头的弧的数目出度出度OD(OD(vv))：：以该顶点为尾头的弧的数目以该顶点为尾头的弧的数目在有向图中在有向图中,,顶点的度等于该顶点的入度与出度之和顶点的度等于该顶点的入度与出度之和。。24/12/276（a)G1（b)G2（c)G3（d)G45234112346752222364521图图7-17-1无向图和有向无向图和有向图图24/12/277在图7-1中，图(a)为无向图，其中G1的顶点集合和边集合分别为：V(G1)={1，2，3，4，5，6，7}，E(G1)={(1，2)，(l，3)，(2，3)，(3，4)，(3，5)，(5，6)，(5，7)}。图(c)为有向图，其中G3的顶点集合和弧集合分别为V(G3)={1，2，3，4，5，6}，E(G3)={<1，2>，<1，3>，<1，4>，<3，1>，<4，5>，<5，6>，<6，4>}24/12/2787.1.2图的基本术语1．顶点的度与顶点v相关的边或弧的数目称作顶点v的度。在有向图中，一个顶点依附的弧头数目，称为该顶点的入度。一个顶点依附的弧尾数目，称为该顶点的出度，某个顶点的入度和出度之和称为该顶点的度。例如图7-1中，无向图G1中顶点3的度为4，顶点5的度为3。例如在图7-1中，有向图G3中顶点1的出度OD(1)=3，...
