admin 管理员组文章数量: 1184232
2024年4月22日发(作者：注册微信公众号被骗299)
第5章 图
图的定义
①图由顶点集V和边集E组成，记为G=（V，E），V(G)是图G中顶点的有穷非空集合，E(G)
是图G中顶点之间变得关系集合，|V|表示顶点个数，也称图的阶，|E|表示边数
（线性表和树都可以是空的，但图可以只有一个顶点没有边）
②有向图：弧是顶点的有序对，记为
顶点w的弧。无向图：边是顶点的无序对，记为(v,w)
③简单图：一个图满足：不存在重复边；不存在顶点到自身的边。多重图相对于简单图定义
④完全图：无向图中，任意两顶点之间存在边，称为完全无向图。N个顶点的无向完全图有
n(n-1)/2条边。在有向图中，任意两顶点之间存在方向相反的两条弧，称为有向完全图，N
个顶点的有向完全图有n(n-1)条边。
⑤连通图：在无向图中任意两顶点都是连通的。无向图中的极大连通子图称为连通分量。极
大要求连通子图包含其所有的边和顶点，极小连通子图既要保持图连通，又要保持边数最少
⑥在有向图中任意两顶点v,w，存在从顶点v到顶点w和从顶点w到顶点v两条路径，这种
图称为强连通图。有向图的极大强连通子图称为有向图的强连通分量。
⑦生成树：①包含图中所有顶点n，②生成树有n-1条边, ③任意两点连通。对生成树而言，
砍去一条边变成非连通图，加上一条边形成一个回路。在非连通图中，连通分量的生成树构
成了非连通图的生成森林。
⑧顶点的度：以该顶点为端点的边的数目。
无向图的全部顶点的度之和等于边数的两倍。
有向图的度等于出度和入度之和，入度是以该顶点为终点的有向边的数目，出度是以该顶点
为起点的有向边的数目。有向图的全部顶点的入度之和和出度之和相等且等于边数。
⑨图中每条边可以标上具有某种含义的数值，该数值称为边的权值。带有权值的图称为网。
1○0对于无向图G=(V, {E})，如果边(v，v’)∈E，则称顶点v，v’互为邻接点，即v，v’相邻接。
边(v，v’)依附于顶点v 和v’，或者说边(v, v’)与顶点v 和v’相关联。
对于有向图G=(V, {A})，如果弧
v，或者说弧
设有两个图G=(V,E)和G‘=(V‘,E‘)，若V‘是V的子集，E‘是E的子集，则称G‘是G的子图
图的操作：
CreateGraph(&G,V,VR);
初始条件：V 是图的顶点集，VR 是图中弧的集合。操作结果：按V 和VR 的定义构造图G。
DestroyGraph(&G);
初始条件：图G 存在。操作结果：销毁图G。
LocateVex(G,u);
1
初始条件：图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 的第一个邻接顶点。若顶点在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 及其相关的弧。
InsertAcr(&G,v,w);
初始条件：图G 存在，v 和 w 是 G 中两个顶点。
操作结果：在G 中增添弧
DeleteArc(&G,v,w);
初始条件：图G 存在，v 和 w 是 G 中两个顶点。
操作结果：在G 中删除弧
DFSTraverser(G,Visit());
初始条件：图G 存在，v 是 G 中某个顶点，Visit 是顶点的应用函数。
操作结果：深度优先遍历图G，并对每个顶点调用函数Visit 一次。一旦Visit()失败，则操作
失败。
BFSTRaverse(G,Visit());
初始条件：图G 存在，Visit 是顶点的应用函数。
操作结果：广度优先遍历图 G，并对每个顶点调用函数Visit 一次。 一旦 Visit()失败，则操
作失败。
2
版权声明：本文标题：《数据结构之图》相关知识点总结 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.roclinux.cn/b/1713724023a648611.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论