2022/2/8 6:12:42

本文主要是介绍图,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

目录

  • 第六章 图

第六章 图

6.1 图的定义与基本术语

图(Graph) G由两个集合V和E组成,记为G=(V,E) , 其中V是顶点的有穷非空集合, E是V中顶点偶对的有穷集合,这些顶点偶对称为边。

图的基本术语(用n表示图中顶点数目,用e表示边的数目)

对于图G,若边集E(G)为有向边的集合,则称该图为有向图;若边集E(G)为无向边的集合, 则称该图为无向图

  • 无向完全图和有向完全图:对于无向图,若具有 n(n- 1)/2 条边,则称为无向完全图。 对于有向图,若具有n(n- l)条弧,则称为有向完全图。

  • 稀疏图和稠密图:有很少条边或弧(如 e<nlog2(n))的图称为稀疏图, 反之称为稠密图。

  • 权和网:在实际应用中,每条边可以标上具有某种含义的数值,该数值称为该边上的权。 这些权可以表示从一个顶点到另一个顶点的距离或耗费。这种带权的图通常称为网。

  • 邻接点:对于无向图 G, 如果图的边 (v, v')EE, 则称顶点 v 和 v'互为邻接点, 即 v 和 v' 相邻接。边 (v, v')依附于顶点 v 和 v', 或者说边 (v, v')与顶点 v 和 v'相关联。

  • 度、入度和出度:顶知的度是指和v相关联的边的数目,记为 TD(v)。对于有向图,顶点v的度分为入度和出度。入度是以顶点v为头的弧的数目,记 为ID(v); 出度是以顶点 v 为尾的弧的数目,记为OD(v)。

  • 路径和路径长度:在无向图 G 中,从 顶点 v 到顶点 v'的 路径是一个顶点序列。路径长度是一条路径上经过的边或弧的数目。

  • 回路或环:第一个顶点和最后一个顶点相同的路径称为回路或环。

  • 简单路径、 简单回路或简单环:序列中顶点不重复出现的路径称为简单路径。除了第一 个顶点和最后一个顶点之外,其余顶点不重复出现的回路,称为简单回路或简单环。
  • 连通、连通图和连通分量:在无向图 G 中,如果从顶点 v 到顶点 v'有路径,则称 v 和 v' 是连通的。如果对千图中任意两个顶点 vi,vj∈V, vi和 vj 都是连通的,则称 G 是连通图。连通分量, 指的是无向图中的极大连通子图。
  • 强连通图:在有向图 G 中,如果对于每一对 vi,vj∈V,从vi到vj, 和 从 vj到vi都存在路径,则称G是强连通图。
  • 连通图的生成树: 一个极小连通子图,它含有图中全部 顶点,但只有足以构成一棵树的 n-1条边,这样的连通子图称为 连通图的生成树。
  • 有向树和生成森林:有一个顶点的入度为 0, 其余顶点的入度均为 l 的有向图称为有向树。

6.3 图的类型定义

图是一种数据结构,加上一组基本操作,就构成了抽象数据类型。

ADTGraph{

  数据对象: V是具有相同特性的数据元素的集合,称为顶点集。

  数据关系: R = {VR} VR = {lv, w∈V且P (v, w) 表示从v到w的弧 , 谓词P (v, w)定义了弧的意义或信息)}

基本操作:

CreateGraph{&G,V,VR} 初始条件:V是图的顶点集,VR是图中弧的集合。 操作结果:按V和VR的定义构造图G

DestroyGraph { &G} 初始条件:图G存在。 操作结果:销毁图G。

Locat eVex{G,u} 初始条件:图G存在,u和G中顶点有相同特征。 操作结果:若G中存在顶点 u, 则返回该顶点在图中的位置;否则返回其他信息。

GetVex{G,v} 初始条件:图G存在,v是G中某个顶点。 操作结果:返回v的值。 PutVex(&G,v,value); 初始条件:图G存在,v是G中某个顶点。 操作结果:对 v赋值value。

FirstAdjVex(G,v) 初始条件:图G存在,v是G中某个顶点。 操作结果:返回 v的第一 个邻接顶点。若v在G中没有邻接顶点,则返回 “空 ” 。

NextAdjVex(G,v,w) 初始条件:图G存在,v是G中某个顶点,w是v的邻接顶点。操作结果:返回v的(相对千w的)下一 个邻接顶点。若w是v的最后一 个邻接点,则返回 “空 ” 。

InsertVex(&G,v) 初始条件:图G存在,v和图中顶点有相同特征。 操作结果:在图G中增添新顶点v。

DeleteVex(&G,v) 初始条件:图G存在,v是G中某个顶点。 操作结果:删除 G中顶点v及其相关的弧。

InsertArc(&G,v,w) 初始条件:图G存在,v和w是G中两个顶点。 操作结果:在G中增添弧, 若G是无向图,则还增添对称弧。

DeleteArc(&G,v,w) 初始条件:图G存在,v和w是G中两个顶点。 操作结果:在G中删除弧, 若G是无向图,则还删除对称弧。

DFSTraverse(G) 初始条件:图G存在。 操作结果:对图进行深度优先遍历,在遍历过程中对每个顶点访问一次。

BFSTraverse(G) 初始条件:图G存在。 操作结果:对图进行广度优先遍历,在遍历过程中对每个顶点访问一次。 }ADT Graph



这篇关于图的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程