- 微信
- 微博
  
  分享文章到微博
- 复制链接
  
  复制链接到剪贴板

化解数据结构----图的基础知识（万字系列，必备知识）

是Dream呀发表于 2022/05/11 23:25:00 2022/05/11

【摘要】 📢📢📢📣📣📣 🌻🌻🌻Hello，大家好我叫是Dream呀，一个有趣的Python博主，多多关照😜😜😜 🏅🏅🏅Python领域优质创作者，欢迎大家找我合作学习（文末有...

📢📢📢📣📣📣
🌻🌻🌻Hello，大家好我叫是Dream呀，一个有趣的Python博主，多多关照😜😜😜
🏅🏅🏅Python领域优质创作者，欢迎大家找我合作学习（文末有名片欢迎+++）
💕 入门须知：这片乐园从不缺乏天才，努力才是你的最终入场券！🚀🚀🚀
💓最后，愿我们都能在看不到的地方闪闪发光，一起加油进步🍺🍺🍺
🍉🍉🍉“一万次悲伤，依然会有Dream，我一直在最温暖的地方等你”，唱的就是我！哈哈哈~🌈🌈🌈
🌟🌟🌟✨✨✨

前言：💡💡💡在这个[有趣的的数据结构和算法]专栏中，Dream将带大家以手写笔记和知识梳理的形式带大家讲解每一个知识点，将数据结构轻松化解！
💗 💗 💗每周一篇，喜欢的话欢迎订阅起来吧~ ps：这是C语言版的嗷
图知识框架：

一、图的定义和基本术语

1.图的定义

图：简单的说，图是一个用线或边连接在一起的顶点或节点的集合，严格的说，图是有限顶点V和边E的有序对。
图的表示：一般使用圆圈表示顶点，使用线段表示边，一条边连接两个不同的顶点。有些边是带方向的称为有向边，当顶点v到u含有一条有向边，就画一个箭头从v指向u，使用元组<v，u>表示；而没有方向的边称为无向边，当顶点v到u含有一条有向边，就画一条线段从v指向u，使用元组（v，u）表示。例如下面分别是有向图和无向图。

图根据边的分类分为有向图和无向图：

有向图的边是有向边，它就像公路的单行道一样，只能从一个方向到另一个方向。
无向图的边是无向边，当然它就像双向车道一样可以互相到达，而且两个顶点是没有区别的。

当且仅当（u，v）是图的边，称顶点v和u是邻接的。边（u，v）关联于顶点u和v。
对于无向图这种邻接和关联是对等的，而有向图是单向的，它仅仅从u到v。

无向边用小括号（）表示，有向边用尖括号<>表示。

  
 
  1

2.图的基本术语

2.1子图

如果图H的顶点和边的集合是图G的子集，那么称图H是图G的子图。

2.2 无向完全图和有向完全图

任意两点间都存在边使其相连的无向图或任意两点间都存在两条不同边的有向图称作完全图

N个顶点的完全图:

有向有n(n-1)条边
无向有n(n-1)/2条边

2.3稀疏图和稠密图

顾名思义，就是讨论多少的问题，注意分界点，这个依据是大家默认的一个依据，而不是必须的分界依据！

数据结构中对于稀疏图的定义为：有很少条边或弧（边的条数|E|远小于|V|²）的图称为稀疏图（sparse graph），反之边的条数|E|接近|V|²，称为稠密图（dense graph）。此定义来自百度百科，实际上是一种朴素的理解，简单来说边越多，图就越稠密

2.4权和网

权：在图的一些应用中，可能要为每条边赋予一个表示大小的值，这个值就称为权。例如从城市A到城市B存在一条公路，而可以使用权表示这条公路的距离。
那我们把**带权的图称为网**。

2.5邻接点

2.6度、入度、出度

顶点的度为以该顶点为一个端点的边的数目。
对于无向图，顶点的边数为度，度数之和是顶点边数的两倍。
对于有向图，入度是以顶点为终点，出度相反。有向图的全部顶点入度之和等于出度之和且等于边数。顶点的度等于入度与出度之和。

注意：入度与出度是针对有向图来说的。

2.7路径和路径长度

两顶点之间的路径指顶点之间经过的顶点序列，经过路径上边的数目称为路径长度。

2.8回路和环

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

2.9简单路径、简单回路和简单环

顶点不重复出现的路径称为简单路径。
除第一个顶点和最后一个顶点外，其余顶点不重复出现的回路称为简单回路或者简单环。

2.10连通、连通图和连通分量

在无向图中，两顶点有路径存在，就称为连通的。若图中任意两顶点都连通，同此图为连通图。无向图中的极大连通子图称为连通分量。

2.11强连通图和强连通分量

在有向图中，两顶点两个方向都有路径，两顶点称为强连通。若任一顶点都是强连通的，称为强连通。
有向图中极大强连通子图为有向图的强连通分量。

2.12连通图的生成树

连通图的生成树是包含图中全部顶点的一个极小连通子图，若图中有n个顶点，则生成树有n-1条边。所以对于生成树而言，若砍去一条边，就会变成非连通图。
一颗有n个顶点的生成树有且仅有n-1条边。
如果一个图n个顶点，边数多于n-1则说明其一定有环
n-1条边的图却不一定是生成树。

2.13有向树和生成森林

一个有向图的生成森林是由若干颗有向树组成的，含有图中的全部顶点，但只有足以构成若干棵不相交的有向树的弧。

二、图的类型定义

emmmm，😍😍😍你在期待哪种图呢😍😍😍…………………………………………

1.CreateGraph(*G,V,VR) //按照顶点集V合边弧集VR定义构造图G
2. DestroyGraph(*G) //销毁图G
3. LocateVex(G,u) //返回图G中顶点u的位置，若不存在，则返回其他信息
4.GetVex(G,v) //返回图G中顶点v的值
5.PutVex(G,v,value) //将图G中顶点v赋值value
6.FirstAdjVex(G,*v) //返回顶点v的一个邻接顶点，若无则返回空
7.NextAdjVex(G,v,w) //顶点w是顶点v的邻接顶点，返回顶点v相对于顶点w的下一个邻接顶点；若顶点w是顶点v的最后一个邻接顶点，则返回空
8.InsertVex(*G,v) //在图G种添加顶点v
9.DeleteVex(*G,v) //删除图G中顶点v及其相关的弧
10.InsertArc(*G,v,w) //在图G中添加弧<v,w>,如果是无向图，还要添加对称弧<w,v>
11.DeleteArc(*G,v,w) //在图G中删除弧<v,w>,如果是无向图，还要删除对称弧<w,v>
12.DFSTraverse(G) //对图G进行深度优先遍历
13.HFSTraverse(G) //对图G进行广度优先遍历

三、图的存储结构

1.邻接矩阵

所谓邻接矩阵存储结构就每个顶点用一个一维数组存储边的信息，这样所有点合起来就是用矩阵表示图中各顶点之间的邻接关系。所谓矩阵其实就是二维数组。

1.1无向图的邻接矩阵表示法

无向图的邻接矩阵是对称的；
顶点i的度 = 第i行（列）中1的个数

注意： 完全图的邻接矩阵中，对角元素为0，其余的为1

1.2有向图的邻接矩阵表示法

有向图的邻接矩阵可能是不对称的；
顶点的出度 = 第i行元素之和
顶点的入度 = 第i列元素之和
顶点的度 = 第i行元素之和+第i列元素之和

1.3网的邻接矩阵表示法

网就是有权的图（路径上有数值，即有权重）

有边或者有弧：权
无边或者无弧：无穷

1.4邻接矩阵存储表示

用两个数组分别存储顶点表和邻接矩阵！
C语言版：

int g[N][N];
int main() {
	int n, m; //n个点 m条边 
	scanf("%d%d", &n, &m);
	int u, v; //从u到v
	for (int i = 0; i < m; ++i) {
		scanf("%d%d", &u, &v);
		g[u][v] = 1; 
		//g[v][u] = 1;//无向图要建双边 
		//g[u][v] = w; //带权图
	} 
}

  
 
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12