图的基本概念1

本篇参考了王道及b站懒猫老师，王卓老师的课程，进行归纳总结，本文使用的语言是c语言，部分代码

没有实现或使用伪代码方式，文章内容共包含了以下几个部分：



那么接下来就从图的基本概念进行学习：

图的基本概念

图G由顶点集V和边集E组成，记为G=(V,E)，其中VG)表示图G中顶点的有限非空集;E(G)表示图G中顶点之

间的关系(边）集合。若V={v1,v2,v3,…… }，则用|V表示图G中顶点的个数。

E={(u, v)| u∈v,v∈V}，用|E表示图G中边的条数。

若E是无向边（简称边）的有限集合时，则图G为无向图。边是顶点的无序对，记为(vy, w)或(w, v)。可以

说w和v互为邻接点。边(v, w)依附于w和v，或称边(v, w)和v, w相关联。

如下图：边集合为E={(A,B),(E,A),(C,A),(B,C),(C,D),(D,E),(C,E)}

筒单图、多重图

一个图G如果满足:①不存在重复边;②不存在顶点到自身的边，那么称图G为简单图。图6.1中G,和 G均

为简单图。若图中某两个顶点之间的边数大于1条，又允许顶点通过一条边和自身关联，则称图G为多重

图。多重图和简单图的定义是相对的。数据结构中仅讨论简单图。

完全图（也称简单完全图)

对于无向图，E的取值范围为О到n(n -1)/2，有n(n -1)/2条边的无向图称为完全图，在完全图中任意两个

的顶点可能不在这个V的子集中。

连通、连通图和连通分量

在无向图中，若从顶点v到顶点w有路径存在，则称v和w是连通的。,若图G中任意两个顶点都是连通

的，则称图G为连通图，否则称为非连通图。无向图中的极大连通子图称为连通分量。

强连通图、强连通分量

在有向图中，如果有-一对顶点v和w，从v到w和从w到v之间都有路径，则称这两个顶点是强连通的。若

图中任何一对顶点都是强连通的，则称此图为强连通图。有向图中的极大强连通子图称为有向图的强连

通分量,

生成树、生成森林

连通图的生成树是包含图中全部顶点的一个极小连通子图。若图中顶点数为n，则它的生成树含有n-1条

在一-个图中，每条边都可以标上具有某种含义的数值，该数值称为该边的权值。这种边上带

有权值的图称为带权图，也称网。

稠密图、稀疏图

边数很少的图称为稀疏图，反之称为稠密图。稀疏和稠密本身是模糊的概念，稀疏图和稠密图常常是相

对而言的。

路径、路径长度和回路

顶点v,到顶点v之间的一条路径是指顶点序列当然关联的边也可理解为路径的构成要素。路径上边的数目

称为路径长度。第一个顶点和最后一个顶点相同的路径称为回路或环。若一个图有n个顶点，并且有大于

n-1条边，则此图一定有环。

各顶点之间的邻接关系)，存储顶点之间邻接关系的二维数组称为邻接矩阵。

如下图所示的表格，将顶点作为横纵坐标，交叉处为权值，此图为无向网即没有方向且有权值，当两个

顶点之间无边时用无穷大来表示。如图可以发现规律，各数值按照对角线对称

这里的图和下面创建的是一样的，可以将代码和图一起进行剖析

邻接矩阵结构体成员



邻接矩阵创建