6-1知识点：数据结构——图

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了6-1知识点：数据结构——图，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含3118字，纯文字阅读大概需要5分钟。

内容图文

一.基础知识
顶点集V
边集E
|E|边的条数
|V|顶点个数，也称图的阶
可以没有边，但不能没有顶点
二.基本概念
1.无向图
（1）边没有箭头，这些边称为无向边（简称边）
（2）每条边贡献两个度，所以|E|条边贡献了2|E|个度，故所有顶点的度之和=2|E|
（3）(A,B）表示AB之间的边

2.有向图
（1）有箭头的边，这些边称为有向边（也称弧）。
A→B
A叫做弧尾，B叫做弧头
（2）每条边贡献了一个出度和一个入度，故|E|条边贡献了|E|个出度，|E|个入度。故所有顶点的入度之和=所有顶点的出度之和=|E|，所有顶点的度之和=2|E|
（3）<A,B>表示由A指向B的弧

3.简单图
①不存在重复的边
②不存在顶点到自身的边
注：对于有向图，不同方向的弧，视为不同的边

4.度、入度、出度
度：该顶点边（弧）的条数
出度：该顶点指出弧的数量
入度：该顶点指入弧的数量

5.顶点-顶点的关系描述
（1）路径：由顶点A到顶点B经过的顶点序列（含A,B）
?有向图的路径必须沿弧的方向
（2）回路/环：围成圈的路径
（3）简单路径：顶点不重复出现的路径
（4）简单回路：除第一个顶点和最后一个顶点外，其余顶点不重复出现的回路
（5）路径长度：路径上边的数目
（6）点到点的距离：从顶点A出发到顶点B的最短路径若存在，则此路径的长度称为从u到v的距离。
（7）若从u到v根本不存在路径，则记该距离为无穷（∞）

6.连通、连通图（无向图）
（1）若从顶点v到顶点w有路径存在，则称v和w是连通的
（2）任意两个顶点都是连通的（不抛弃每个顶点），则称图G为连通图，否则称为非连通图。
（3）对于n个顶点的无向图G

注：
（1）若G是连通图，则最少有 n-1 条边，若 |E|>n-1，则一定有回路
（2）若G是非连通图，则最多可能有 C(n-1)2条边
（抛开最后一个顶点，其余的连满）

7.强连通、强连通图（有向图）
（1）若从顶点v到顶点w和从顶点w到顶点v之间都有路径（相互有），则称这两个顶点是强连通的。
（2）若图中任何一对顶点都是强连通的，则称此图为
强连通图。
（3）对于n个顶点的有向图G
若G是强连通图，则最少有 n 条边（形成回路）

8.子图、生成子图
（1）子图：包含原图中的部分顶点（也可全部）和边
·注：边必须依附于顶点存在
定义：设有两个图G = (V, E)和G’ = (V’, E’)，若V’是V的子集，且E’是 E的子集，则称G’是G的子图
（2）生成子图：包含原图中的所有顶点和任意的边（边可为0）

9.连通分量（无向图）
连通分量：无向图中的极大连通子图
说明：子图必须连通，且包含尽可能多的顶点和边（但不能超过原图的顶点和边）
解释：必须连通+原图中所有顶点和边

10.强连通分量（有向图）
有向图的强连通分量：有向图中的极大强连通子图
解释：必须强连通+原图中所有顶点和边

11.生成树
连通图的生成树是包含图中全部顶点的一个极小连通子图
解释：全部顶点+必须连通+边最少
·生成树结果可能不唯一

注：顶点数为n，则它的生成树含有 n-1 条边（边最少且连通）。减一条边变为非连通；加一条边产生回路。

12.生成森林
在非连通图中，连通分量的生成树构成了非连通图的生成森林。

13.权、带权图/网、带权路径长度
（1）边的权：在一个图中，每条边都可以标上具有某种含义的数值，该数值称为该边的权值
（2）带权图/网：边上带有权值的图
（3）带权路径长度：当图是带权图时，一条路径上所有边的权值之和

14.完全图
（1）无向完全图：无向图中任意两个顶点之间都存在边（边画满）
注：|E|=C(n)2
其中C(n)2=n(n–1)/2
（2）有向完全图：有向图中任意两个顶点之间都存在方向相反的两条弧（边画满）
注：|E|=2*C(n)2

15.稀疏图、稠密图
（1）稀疏图：边数很少的图
（2）稠密图：边数很多的图
无明显界限

16.特殊的图
（1）树：不存在回路+连通+无向图
注：n个顶点的树，必有n-1条边
（2）有向树：不存在回路+连通+有向图
注：一个顶点的入度为0、其余顶点的入度均为1

---

有错误/补充之处欢迎联系

内容总结

以上是互联网集市为您收集整理的6-1知识点：数据结构——图全部内容，希望文章能够帮你解决6-1知识点：数据结构——图所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---