离散数学中的图论是专门研究图性质的一个数学分支

第七章图第一节图的类型定义1第七章图离散数学中的图论是专门研究图性质的一个数学分支，但图论注重研究图的纯数学性质，而数据结构中对图的讨论则侧重于在计算机中如何表示图以及如何实现图的操作和应用等。图是较线性表和树更为复杂的数据结构，因此和线性表、树不同，虽然在遍历图的同时可以对顶点或弧进行各种操作，但更多图的应用问题如求最小生成树和最短路径等在图论的研究中都早已有了特定算法，在本章中主要是介绍它们在计算机中的具体实现。这些算法乍一看都比较难，应多对照具体图例的存储结构进行学习。而图遍历的两种搜索路径和树遍历的两种搜索路径极为相似，应将两者的算法对照学习以便提高学习的效益。第一节图的类型定义图由一个顶点集和弧集构成，通常写作：Graph=(V,VR)V是具有相同特性的数据元素的集合，称为顶点集。VR＝{v,w|v,w∈V，v,w表示从v到w的弧}v,w表示从顶点v到顶点w的一条弧，其中顶点v被称为弧尾，顶点w被称作弧头。由于弧是有方向的，故称有向图。(有向图G1)例如下列定义的有向图如上图所示。G1=(V1,VR1)其中：V1={A,B,C,D,E}VR1={A,B,A,E,B,C,C,D,D,B,D,A,E,C}若v,w∈R必有w,v∈R，则称(v,w)为顶点v和顶点w之间存在一条边。由顶点集和边集构成的图称作无向图。(无向图G2)第七章图第一节图的类型定义2例如下列定义的无向图如上所示。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)}由于空的图在实际应用中没有意义，因此一般不讨论空的图，即V是顶点的有穷非空集合。图的抽象数据类型定义如下：ADTGraph{数据对象：V是具有相同特性的数据元素的集合，称为顶点集。数据关系：VR＝{v,w|v,w∈V且P(v,w)，v,w表示从v到w的弧，谓词P(v,w)定义了弧v,w的意义或信息}基本操作P：{结构初始化}CreateGraph(&G,V,VR);初始条件：V是图的顶点集，VR是图中弧的集合。操作结果：按V和VR的定义构造图G。{销毁结构}DestroyGraph(&G);初始条件：图G存在。操作结果：销毁图G。{引用型操作}LocateVex(G,u);初始条件：图G存在，u和G中顶点有相同特征。操作结果：若G中存在和u相同的顶点，则返回该顶点在图中位置；否则返回其它信息。顶点在图中的位置指的是，在图的存储结构中顶点之间自然形成的相对位置。GetVex(G,v);初始条件：图G存在，v是G中某个顶点。操作结果：返回v的值。FirstAdjVex(G,v);初始条件：图G存在，v是G中某个顶点。操作结果：返回v的第一个邻接点。若该顶点在G中没有邻接点，则返回空。第七章图第一节图的类型定义3若v,w∈G，则称w为v的邻接点，若(v,w)∈G，则称w和v互为邻接点。NextAdjVex(G,v,w);初始条件：图G存在，v是G中某个顶点，w是v的邻接顶点。操作结果：返回v的（相对于w的）下一个邻接点。若w是v的最后一个邻接点，则返回空。若v有多个邻接点，则在图的存储结构建立之后，其邻接点之间的相对次序也就自然形成了。{加工型操作}PutVex(&G,v,value);初始条件：图G存在，v是G中某个顶点。操作结果：对v赋值value。InsertVex(&G,v);初始条件：图G存在，v和图中顶点有相同特征。操作结果：在图G中增添新顶点v。DeleteVex(&G,v);初始条件：图G存在，v是G中某个顶点。操作结果：删除G中顶点v及其相关的弧。InsertArc(&G,v,w);初始条件：图G存在，v和w是G中两个顶点。操作结果：在G中增添弧v,w，若G是无向的，则还增添对称弧w,v。DeleteArc(&G,v,w);初始条件：图G存在，v和w是G中两个顶点。操作结果：在G中删除弧v,w，若G是无向的，则还删除对称弧w,v。DFSTraverse(G,Visit());初始条件：图G存在，Visit是顶点的应用函数。操作结果：对图G进行深度优先遍历。遍历过程中对每个顶点调用函数Visit一次且仅一次。一旦visit()失败，则操作失败。BFSTraverse(G,Visit());初始条件：图G存在，Visit是顶点的应用函数。操作结果：对图G进行广度优先遍历。遍历过程中对每个顶点调用函数Visit一次且仅一次。一旦visit()失败，则操作失败。}ADTGraph第七章图第一节图的类型定义4介绍几个有关图的常用术语。顶点的度对无向图而言，邻接点的个数定义为顶点的度。例如(无向图G2)中顶点B的度为3，顶点C的度为2。对有向图而言，顶点的度为其出度和入度之和，其中出度定义为以该顶点为弧尾的弧的个数，入度定义为以该顶点为弧头的弧的个数。例如(有向图G1)中顶点D的度为3，其中出度为2，入度为1，顶点B的度为3，其中出度为1，入度为2。子图假设有两个图G=(V,{E})和G'=(V',{E'})，如果V'V且E'E，则称G'为G的子图(subgraph)。例如，(有向图G1)的子图的一些例子。路径和回路若有向图G中k+1个顶点之间都有弧存在（即0v,1v,1v,2v，…1kv,kv是图G中的弧），则这个顶点的序列{0v,1v,…,kv}为从顶点0v到顶点kv的一条有向路径，路径中弧的数目定义为路径长度，若序列中的顶点都不相同，则为简单路径。对无向图，相邻顶点之间存在边的k+1个顶点序列构成一条长度为k的无向路径。如果和是同一个顶点，则是一条由某个顶点出发又回到自身的路径，称这种路径为回路或环。例如(有向图G1)中顶点序列{A,E,C,D}是一条路径长度为3的简单路径，顶点序列{A,B,C,D,A}是一条长度为4的简单回路。(无向图G2)中顶点序列{A,B,F,C,D}是一条长度为4的无向路径。连通图和连通分量、强连通图和强连通分量若无向图中任意两个顶点之间都存在一条无向路径，则称该无向图为连通图，否则称为非连通图。若有向图中任意两个顶点之间都存在一条有向路径，则称该有向图为强连通图。例如(无向图G2)和(有向图G1)分别为连通图和强连通图。非连通图中各个极大连通子图称作该图的连通分量。如下图为由两个连通分量构成的非连通图。第七章图第一节图的类型定义5非强连通的有向图中的极大强连通子图称作有向图的强连通分量。例如下图中的有向图含有三个强连通分量。生成树和生成森林一个含n个顶点的连通图的生成树是该图中的一个极小连通子图，它包含图中n个顶点和足以构成一棵树的n-1条边。如下图所示。若在无向图G2中删除边(B,F)，则成为一个非连通图，对于非连通图，对其每个连通分量可以构造一棵生成树，合成起来就是一个生成森林。如下图所示。无向网和有向网在实际应用中，图的弧或边往往与具有一定意义的数相关，称这些数为权，分别称带权的有向图和无向图为有向网和无向网。