资源描述：
《数据结构第7章图》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第七章图图状结构是一种比树形结构更复杂的非线性结构。在线性表中，数据元素之间仅有线性关系，每个数据元素只有一个直接前驱和一个直接后继；在树形结构中．数据元素之间有着明显的层次关系，并且每一层的数据元素可能和下一层中多个元素相关，但只能和上一层中一个元素相关；而在图形结构中，结点之间的关系可以是任意的，图中任意两个数据元素之间都可能相关。7.1图的定义和术语一、图的定义：图（Graph）是由非空的顶点集合和一个描述顶点之间关系（边或者弧）的集合组成，其二元组定义为：G＝（V，E）V＝{vi
2、vi∈
3、dataobject}E＝{（vi,vj）
4、vi,vj∈V∧P（vi,vj）}其中，G表示一个图，V是图G中顶点的集合，E是图G中边的集合，集合E中P（vi,vj）表示顶点vi和顶点vj之间有一条直接连线。集合E可以是空集，若E为空，则该图只有顶点而没有边。偶对（vi,vj）表示一条边。二、图的基本术语有向图和无向图在图中，若用箭头标明了边是有方向性的，则称这样的图为有向图，否则称为无向图。如图所示，G1为无向图，G2为有向图。在无向图中，一条边（x,y）与（y,x）表示的结果相同，用圆括号表示
5、，在有向图中，一条边与表示的结果不相同，故用尖括号表示。表示从顶点x出发向顶点y的边，x为始点，y为终点。有向边也称为弧，x为弧尾，y为弧头,则表示为一条弧,而表示y为弧尾、x为弧头的另一条弧。245136G1图G1中：V(G1)={1,2,3,4,5,6}E(G1)={<1,2>,<2,1>,<2,3>,<2,4>,<3,5>,<5,6>,<6,3>}157324G26图G2中：V(G2)={1,2,3,4,5,6,7}E(G1)={(1,2)
6、,(1,3),(2,3),(2,4),(2,5),(5,6),(5,7)}完全图、稠密图、稀疏图具有n个顶点，n(n-1)/2条边的图，称为无向完全图，具有n个顶点，n(n-1)条弧的有向图,称为有向完全图。无向完全图和有向完全图都称为完全图。当一个图接近完全图时，则称它为稠密图，相反地，当一个图中含有较少的边或弧时，则称它为稀疏图。213213有向完全图无向完全图3.度、入度、出度在图中，一个顶点依附的边或弧的数目，称为该顶点的度。在有向图中，一个顶点依附的弧头数目，称为该顶点的入度。一个顶点
7、依附的弧尾数目，称为该顶点的出度，有向图中某个顶点的入度和出度之和称为该顶点的度。另外，若图中有n个顶点，e条边或弧，第i个顶点的度为di，则有e=245136G2顶点2入度：1出度：3顶点4入度：1出度：0G11573246顶点5的度：3顶点2的度：4子图若有两个图G1和G2，G1=(V1,E1)，G2=(V2,E2)，满足如下条件：V2V1，E2E1，即V2为V1的子集，E2为E1的子集，称图G2为图G1的子图。5．权在图的边或弧中给出相关的数，称为权。权可以代表一个顶点到另一个顶点的距
8、离，耗费等，带权图一般称为网。6．连通图和强连通图在无向图中，若从顶点i到顶点j有路径，则称顶点i和顶点j是连通的。若任意两个顶点都是连通的，则称此无向图为连通图，否则称为非连通图。在有向图中，若从顶点i到顶点j有路径，则称从顶点i和顶点j是连通的，若图中任意两个顶点都是连通的，则称此有向图为强连通图，否则称为非强连通图。7．连通分量和强连通分量无向图中，极大的连通子图为该图的连通分量。显然，任何连通图的连通分量只有一个，即它本身，而非连通图有多个连通分量。有向图中，极大的强连通子图为该图的强连
9、通分量。显然，任何强连通图的强连通分量只有一个，即它本身，而非强连通图有多个强连通分量。8．路径、回路在无向图G中，若存在一个顶点序列Vp,Vi1，Vi2，…，Vin，Vq,使得（Vp,Vi1）,(Vi1,Vi2),…..，(Vin,Vq)均属于E（G），则称顶点Vp到Vq存在一条路径。若一条路径上顶点均不相同，则称此路径为简单路径。起点和终点相同的路径称为回路，简单路径组成的回路称为简单回路。路径上经过的边的数目称为该路径的路径长度。9．生成树、生成森林连通图的生成树是一个极小连通子图，它包含
10、图中全部n个顶点和n-1条不构成回路的边。非连通图的生成树则组成一个生成森林。若图中有n个顶点，m个连通分量，则生成森林中有n-m条边。157324G26245136G1路径：1，2，3，5，6，3路径长度：5简单路径：1，2，3，5回路：1，2，3，5，6，3，1简单回路：3，5，6，3路径：1，2，5，7，6，5，2，3路径长度：7简单路径：1，2，5，7，6回路：1，2，5，7，6，5，2，1简单回路：1，2，3，1三、基本操作：1．Creatgraph（g）输入图的顶点和边，建立图G的存
