资源描述：
《图的基本概念和基本操作》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第8章图8.1图的基本概念和基本操作8.2图的邻接矩阵存储结构8.3图的邻接表存储结构8.4图的其他存储结构8.5最小生成树8.6最短路径8.1图的基本概念和基本操作8.1.1图的基本概念图（Graph）是由顶点集合及顶点间的关系集合组成的一种数据结构。图G的定义是：G=（V，E）式中：V={x
2、x∈某个数据对象}E={（x，y）
3、x，y∈V}或E={〈x，y〉
4、x，y∈V并且Path（x，y）}图8―1带自身环的图和多重图（a）带自身环的图；（b）多重图这样，在图G中，V是顶点的有穷非空集合，E是顶点之间关系
5、的有穷集合，E也叫做边的集合。图有许多复杂结构，本教材只讨论最基本的图，因此，本书讨论的图中不包括图8―1所示两种形式的图。图8―1（a） 中有从顶点A到自身的边存在，称为带自身环的图;图8―1（b）中从顶点B到顶点D有两条无向边，称为多重图。下面我们给出图的基本概念：（1）有向图和无向图：在有向图中，顶点对〈x,y〉是有序的，顶点对〈x,y〉称为从顶点x到顶点y的一条有向边，因此，〈x,y〉与〈y,x〉是两条不同的边。有向图中的顶点对〈x,y〉用一对尖括号括起来，x是有向边的始点，y是有向边的终点，有向图中的
6、边也称作弧。在无向图中，顶点对（x,y）是无序的，顶点对（x,y）称为与顶点x和顶点y相关联的一条边，这条边没有特定的方向，（x,y）与（y,x）是同一条边。图8―２给出了四个图例。其中，图G1和G2是无向图。G1的顶点集合为V（G1）={0,1,2,3}，边集合为E（G1）={(0,1),(0,2),(0,3),(1,2),(1,3),(2,3)}；图G3和G4是有向图，G3的顶点集合为V（G3）={0,1,2}，边集合为E（G3）={〈0,1〉,〈1,0〉,〈1,2〉}。对于有向边，边的方向用箭头画出，箭头
7、从有向边的始点指向有向边的终点。图8―２四个图例（a）G1；（b）G2；（c）G3；（d）G4(2)完全图：在有n个结点的无向图中，若有n(n-1)/2条边，则称此图为无向完全图。图8―２的G1就是无向完全图。在有n个结点的有向图中，若有n(n-1)条边，则称此图为有向完全图。图8―２的G4就是有向完全图。完全图中的顶点个数和边的个数都达到最大值。(3)邻接顶点：在无向图G1，G2中，若（u,v）是E(G)中的一条边，则称u和v互为邻接顶点，并称边（u,v）依附于顶点u和v。在图8―２的无向图G1中，顶点0的邻
8、接顶点有顶点1,2和3；在有向图G3，G4中，若〈u,v〉是E(G)中的一条边，则称顶点u邻接到顶点v，顶点v邻接自顶点u，并称边〈u,v〉与顶点u和顶点v相关联。在图8―２的有向图G3中，顶点1因边〈1,2〉邻接到顶点2。(4)顶点的度：顶点v的度是与它相关联的边的条数，记作TD(v)。在有向图中，顶点的度等于该顶点的入度和出度之和，即TD(v)=ID(v)+OD(v)。顶点v的入度ID(v)是以v为终点的有向边的条数；顶点v的出度OD(v)是以v为始点的有向边的条数。在图8―２的有向图G3中，顶点1的入度I
9、D(1)=1，顶点1的出度OD(1)=2，所以，顶点1的度TD(v)=ID(v)+OD(v)=1+2=3。可以证明，在一个有n个顶点、e条有向边（或无向边）的图中，恒有下列关系式：(5)路径：在图G=(V,E)中，若从顶点vi出发有一组边使可到达顶点vj，则称顶点vi到顶点vj的顶点序列为从顶点vi到顶点vj的路径。在图8―２的图G2中，从顶点0到顶点3的路径为0,1,3。(6)权：有些图的边附带有数据信息，这些附带的数据信息称为权。权可以表示实际问题中从一个顶点到另一个顶点的距离、花费的代价、所需的时间，等等
10、。带权的图称作网络。图8―3就是带权图。其中，图8―3（a）是一个工程的施工进度图，图8-3（b）是一个交通网络图。图8―3带权图（a）施工进度图；（b）交通网络图（7）路径长度：对于不带权的图，一条路径的路径长度是指该路径上的边的条数；对于带权的图，一条路径的路径长度是指该路径上各个边权值的总和。在图8―２的无向图G2中，路径0,1,3的路径长度为2；在图8―3（a）的有向图中，路径1,3,6,7的路径长度为16，路径1,4,7的路径长度为31。(8)子图：设有图G1={V1,E1}和图G2={V2,E2}，
11、若V2V1且E2E1，则称图G2是图G1的子图。(9)连通图和连通分量：在无向图中，若从顶点vi到顶点vj有路径，则称顶点vi和顶点vj是连通的。如果图中任意一对顶点都是连通的，则称该图是连通图。非连通图的极大连通子图称作连通分量。图8―2的无向图G1和G2都是连通图。(10)强连通图和强连通分量：在有向图中，若对于每一对顶点vi和vj都存在一条从vi到vj和从vj到vi的路径，则称该
