第七章图7.1图的定义和基本术语7.2图的存储结构7.2.1数组表示法7.2.2邻接表7.2.3十字链表7.2.4邻接多重表7.3图的遍历7.3.1深度优先搜索7.3.2广度优先搜索7.4图的连通性问题7.4.1无向图的连通分量和生成树7.4.2最小生成树7.5有向无环图及其应用7.5.1拓扑排序7.5.2关键路径7.6最短路径7.6.1从某个源点到其余各顶点的最短路径7.6.2每一对顶点间的最短路径在日常生活中，常用图来表示一些问题或概念，如IC设计、城市间交通道路规划、作业调度等。图和树一样，也是一种非线性数据结构。图和树的最大差异在于：树描述的是数据元素(结点)之间的层次关系，每一层上的数据元素可能和下一层中多个元素(即孩子结点)相关，但只能和上一层中一个元素相关，而图结构研究两顶点之间是否相连的关系，在图中，结点之间的关系是任意的，图中任意两个数据元素之间都有可能相关。图结构提供了简单的方式来描述一个问题、系统或状况等。7.1图的定义和基本术语图是由一个顶点集V和一个弧集VR构成的数据结构。Graph=(V,VR)其中，VR＝{
|v,wV∈且P(v,w)}表示从v到w的一条弧，并称v为弧头，w为弧尾。谓词P(v,w)定义了弧的意义或信息。图的结构定义:由于“弧”是有方向的，因此称由顶点集和弧集构成的图为有向图。ABECD例如:G1=(V1,VR1)其中V1={A,B,C,D,E}VR1={,,,,,,}若VR必有VR,则称(v,w)为顶点v和顶点w之间存在一条边。BCADFE由顶点集和边集构成的图称作无向图。例如:G2=(V2,VR2)V2={A,B,C,D,E,F}VR2={(A,B),(A,E),(B,E),(C,D),(D,F),(B,F),(C,F)}名词和术语网、子图完全图、稀疏图、稠密图邻接点、度、入度、出度路径、路径长度、简单路径、简单回路连通图、连通分量、强连通图、强连通分量生成树、生成森林ABECFAEFBBC设图G=(V,{VR})和图G=(V,{VR}),且VV,VRVR,则称G为G的子图。1597211132弧或边带权的图分别称作有向网或无向网。假设图中有n个顶点，e条边，则含有e=n(n-1)/2条边的无向图称作完全图；含有e=n(n-1)条弧的有向图称作有向完全图；若边或弧的个数e
