资源描述：
《数据结构（C语言描述） 马秋菊 第7章图》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、7.1图的基本概念7.2图的存储表示7.3图的遍历7.4图的生成树7.5最短路径7.6拓扑排序7.7关键路径小结第七章图1本章主要内容《数据结构》主要包括三种基本结构：线性结构，树型结构，图型结构。本章将学习图型结构知识。在图结构中，每个结点都可以和其它任何结点相连接。通过本章内容学习，应该掌握的知识如下：图的定义和相关术语图的存储存储图的遍历最小生成树拓扑排序最短路径关键路径27.1图的基本概念1．图的定义图G(Graph)是由非空的顶点集合V（G）和描述顶点之间关系的边集合E（G）构成，其形式定义为：G＝(V(G)，E(G))。
2、简写为G＝(V，E)。G表示一个图，V是图G中非空顶点的集合，E是图G中边的集合。V2V0V3V1有向图G2无向图G1V0V3V2V132．图的相关概念向图：图中，如果某两个顶点构成的(vi,vj)∈E是无序偶，即顶点之间的连线是没有方向区分的，则称这样的边是无向边，简称边。用（vi,vj）来表示，称vi,和vj互为邻接点。如果某图全部是由无向边构成，则称该图为无向图。有向图：在一个图中，如果两个顶点构成的∈E是序偶，则称这样的边是有向边，简称弧。用来表示。如果某图全部是由有向边构成，则称该图为有向图。顶
3、点（或结点）：图中，数据元素vi称为顶点(vertex)或结点。V2V0V3V1V0V3V2V14无向完全图：在一个无向图中，设V是包含n个结点的集合，且对于任意两个不相同的顶点之间都有一条边将它们连接，则称该图为无向完全图。结论：在一个含有n个顶点的无向完全图中，有n(n-1)/2条边。有向完全图：在一个有向图中，设V是包含n个结点的集合，且对任意两个不同结点之间都有方向相反的两条弧相连，则称该图为有向完全图。结论：在一个含有n个顶点的有向完全图中，有n(n-1)条弧。V2V0V3V1V0V3V2V15顶点的度：顶点的度（degr
4、ee）是指和该顶点相关联的边的数目，通常记为D(v)。在有向图中，将从该顶点出发的弧的数目称为该顶点的出度，用OD(v)表示；对应的，将以该顶点结束的弧的数目称为该顶点的入度，用ID(v)表示；有向图顶点的度为出度和入度之和：D(v)=ID(v)＋OD(v)。V2V0V3V1V0V3V2V1结论：对于具有n个顶点、e条边的图，顶点vi的度D(vi)与边的数目满足如下关系：2e=（D(vi))n∑i=16网络：若图的每条边(弧)都被赋予了具体含义，这种与图的边(弧)相关的数据称为权，称这样的图为加权图或网络。路径：在无向图中，若存在一
5、个顶点序列vi,vi1,vi2,…,vim,vj，使得（vi,vi1），(vi1,vi2)，…，(vim,vj)均属于E(G)，则称顶点vi到vj存在一条路径。对于有向图，路径由弧组成， 即，，…,均属于E(G)。V2V0V3V146527无向加权图路径上边的数目称为路径长度。7回路：假设从vi到vj存在一条路径，且vi=vj，则称该路径为回路。顶点不重复出现的路径称为简单路径。子图：设G(V,E)，G’(V’,E’)是两个图，假设V’⊆V且E’⊆E，称G’为G的子图。当满足V’=V
6、且E’⊆E，称G’为G的生成子图。图G1和G2的子图V1V0V2V3V2V1V0V2V0V3V1有向图G2无向图G1V0V3V2V18连通、强连通若从顶点vi到顶点vj（i≠j）之间有路径存在，则称该两个顶点是连通的。 对于无向图，其中任意两顶点都是连通的，则称该无向图是连通图。无向图中的极大连通子图称为连通分量。无向图G3及连通分量V4V5V2V3V0V1V2V3V0V1V4V59在有向图中，若任意两个顶点vi和vj都连通，则称该有向图为强连通图。有向图的极大强连通子图称为强连通分量。V0V1V3V2G4的强连通分量生成树：连通图
7、G的生成树，是G中包含其全部n个顶点的一个极小连通子图。即由n个顶点，n-1条边构成的连通图。生成森林：在非连通图中，由每个连通分量都可得到一个极小连通子图，即一棵生成树。这些连通分量的生成树就组成了一个非连通图的生成森林。V1V0有向图G4V2V3107.2图的存储表示——邻接矩阵、邻接表等7.2.1邻接矩阵用二维数组来描述图中结点之间相邻关系的存储结构。假设有图G＝(V，E)，其中V＝{v0,v1,…,vn-1}，用一个n×n的矩阵来表示G中各顶点相邻的关系，则矩阵的表示如下：3V1V3V2V011邻接矩阵的说明： ①无向图的邻
8、接矩阵是一个对称矩阵。 ②无向图邻接矩阵第i行（或第i列）中非零元素的个数表示第i个顶点的度。 ③有向图邻接矩阵第i行（或第i列）中非零元素的个数表示第i个顶点的出度（或入度）。 ④用邻接矩阵方法存储图，很容易确定图中任意两个顶点之间
