高中信息技术 竞赛班数据结构专项培训教程 08图教案-人教版高中全册信息技术教案VIP免费

§8图§8.1图的基本概念图：图是数据结构G＝(V，E)，其中V是结点的有穷非空集合，结点的偶对为边，E是边的集合。图中的结点又称为顶点。无向图与有向图：如果图中每条边都是没有方向的，则称为无向图；无向图中的边表示图中顶点的无序对，即（u,v）和（v,u）表示同一条边。如图8.1.1为一个无向图，它的顶点集和边集分别为：V（G1）＝{1,2,3,4,5}E（G1）＝{(1,2),(1,4),(2,3),(2,5),(3,4),(3,5)}如果图中每条边都是有方向的，则称其为有向图；有向图的边表示图中顶点的有序偶对；在有向图中，箭头表示边的方向。如图8.1.2为一个有向图，该图的顶点集和边集分别为：V（G2）＝{1,2,3,4}E（G2）＝{(1,2),(1,3),(2,4),(3,2),(4,3)}度、入度、出度：在一个有向图中，把以结点V为终点的弧的数目称为V的入度；把以结点V为始点的弧的数目称为V的出度。入度和出度之和为该的结点的度。如图8.1.2中，顶点V3的入度为2，出度为1，度为3。路径、路径长度：图中从VS到VP的一条路径是指一串由顶点所成的连续序列VS,Vi1,Vi2,……,Vin,VP，且其中(VP,Vi1),(Vi1,Vi2),……,(Vin,VP)都是E上的边。路径上所包含边的数目称为路径长度。1234图8.1.212345图8.1.1简单路径、简单回路：如果一条路径的顶点序列中，顶点不重复出现，则称此路径为简单路径。起点和终点相同的路径称为回路或环。除了第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路称为简单回路。连通图、强连通图：在无向图G1中，若从顶点Vt到Vs有路径，则称Vt和Vs是连通的。如果对于图中任意两个顶点都是连通的，则称G1为连通图。在有向图G2中，如果每一对顶点Vi,Vj，从Vi到Vj和从Vj到Vi都存在路径，则称G2为强连通图。子图、生成子图：在图G＝（V，E）和图G'=（V',E'）中，若VV'，EE'，则称图G'是图G的子图。若V＝V'，EE'，则子图G'=（V',E'）是图G的一个生成子图。如图8.1.3所示。连通分量、强连通分量：所谓连通分量是指一个无向图中的极大连通子图。有向图中的极大强连通分量称作强连通分量。这里“极大”的含义是：对该子图中再加入其它结点，它便不再是连通的。12345123412345图G的一个子图图G的一个生成子图【图8.1.3】无向图G1G1的三个连通分量【图8.1.4】V3V4V2V1有向图G2V3V4V2V1G2的两个强连通分量生成树、生成森林：一个连通图的生成树是含有图中所有顶点的一个极小连通生成子图，首先它是原连通图的生成子图，其次它是连通的并且有最少的边数。一棵含n个顶点的生成树有且仅有n－1条边，因为一个有n个顶点的图，如果少于n－1条边则为非连通图，如果多于n－1条边则一定有环。但有n－1条边的图不一定是生成树。一个有向图的生成森林是这样一个生成子图，它由若干棵互不相交的有根有向树组成。有根有向树是这样一个有向图，它恰有一个结点的入度为零，其余结点的入度为1，并且如果略去此图中边的方向，处理成无向图后，图是连通的。网络：若图的每条边都带有一个权，则称这种带权图为网络。通常权是具有某种实际意义的数，比如，它们可以表示两个顶点之间的距离、耗费等。§8.2图的存储结构§8.2.1邻接矩阵G3的一棵生成树【图8.1.5】G3ABFECDAFEBDC【图8.1.6】一个有向图及其生成森林ABCD359116邻接矩阵是表示结点间相邻关系的矩阵。若G是一个具有n个结点的图，则G的邻接矩阵是如下定义的n×n矩阵：A[i,j]=例如，图8.2.1的G1的邻接矩阵为A1：无向图的邻接矩阵为对称矩阵！带权的图，其邻接矩阵中值为1的元素可以用边上的权来代替。有时还可根据需要，将网的邻接矩阵中的所有的0用∞代替。如图8.2.2。在实际编程中，∞如何表示？§8.2.2邻接表邻接表是图的一种链式存储结构。为图中每一个顶点建立一个单链表，该顶点为表头，后面连接与表头结点有边相连的结点。如图8.2.3，G1、G2的邻接表分别为：1顶点i和j之间有边（或弧）相连0反之0111110010100011100110110A1＝13245【图8.2.1】G1∞5∞7∞∞∞∞4∞∞∞8∞∞∞∞9∞∞5∞∞6∞∞∞5∞∞3∞∞∞1∞A2＝1423563548155679【图8.2.2】G213245G12345141525134112345§8.3图的遍历图的遍历就是从图中某一顶点出发访遍图中其余顶点，且使每一个顶点仅被访问一次。图的遍历使...