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

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

网络异常，图片无法展示

|

@TOC

一、图的定义和基本术语

1.图的定义

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

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

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

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

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

2.图的基本术语

2.1子图

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

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

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

N个顶点的完全图:

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

2.3稀疏图和稠密图

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

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无向图的邻接矩阵表示法

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

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

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

1. 有向图的邻接矩阵可能是不对称的；
2. 顶点的出度 = 第i行元素之和
3. 顶点的入度 = 第i列元素之和
4. 顶点的度 = 第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.5采用邻接矩阵表示法创建无向网

1. 输入总顶点数和总边数
2. 依次输入点的信息存入顶点表中
3. 初始化邻接矩阵，使每个权值初始化为最大值
4. 构造邻接矩阵
   网络异常，图片无法展示

   |
   代码实现：
   网络异常，图片无法展示

   |

1.6邻接矩阵好处

1. 直观、简单、好理解
2. 方便检查任意一对顶点间是否存在边
3. 方便找任意一项的所有邻接点
4. 方便计算度
   网络异常，图片无法展示

   |

1.7邻接矩阵坏处

1. 不便于增加和删除顶点
2. 浪费空间，对稀疏图而言
3. 浪费时间
   网络异常，图片无法展示

   |

2.邻接表

2.1邻接表表示法（链式）

• 头结点data：存储顶点
• 表结点 邻接点域adjvex：存储相连的顶点的序号，从0开始
• 表结点 链域nextarc：指示下一条边或者弧
  网络异常，图片无法展示

  |
  无向图：

1. 邻接表不唯一（表结点位置可以互换）
2. 若无向图中有n个顶点、e条边，则其邻接表需n个头结点和2e个表结点。适合存储稀疏图。
3. 无向图中的顶点vi的度为第i个单链表中的结点数。
   网络异常，图片无法展示

   |

有向图： 1.邻接表

• 找出度（vi的出度是第i个单链表中结点的个数）易，找入度（vi的入度为整个单链表中邻接点域值是i-1的结点个数）难；

2.逆邻接表

• 同理 找入度易，找出度难

2.2图的邻接表存储形式

2.3邻接表的操作举例说明

2.4利用邻接表表示法创建无向网

2.5邻接表的特点

• 方便找任一顶点的所有“邻接点”
• 节约稀疏图的空间（·需要N个头指针＋2E个结点(每个结点至少2个域)）
• 方便计算任一顶点的“度”：1.对无向图:是的 2.对有向图:只能计算“出度”;需要构造“逆邻接表”求入度
• 不方便检查任意一对顶点间是否存在边
  网络异常，图片无法展示

  |

2.6邻接矩阵和邻接表表示法的关系

1.联系: 邻接表中每个链表对应于邻接矩阵中的一行，链表中结点个数等于一行中非零元素的个数。 2.区别：

• 对于任一确定的无向图，邻接矩阵是唯一的(行列号与顶点编号一致)，但邻接表不唯一（链接次序与顶点编号无关)。
• 邻接矩阵的空间复杂度为O(n2),而邻接表的空间复杂度为O(n+e)。无向e，有向2e

3.用途: 邻接矩阵多用于稠密图;而邻接表多用于稀疏图

3.十字链表——用于有向图

十字链表(Orthogonal List)是有向图的另一种链式存储结构。 我们也可以把它看成是将有向图的邻接表和逆邻接表结合起来形成的一种链表。 有向图中的每一条弧对应十字链表中的一个弧结点，同时有向图中的每个顶点在十字链表中对应有一个结点，叫做顶点结点。

• firstin：第一条入弧
• firstout：第一条出弧

弧结点：

• tailvex:弧尾位置
• headvex：弧头位置
• hilnk：弧头相同的下一条弧
• tlink：弧尾相同的下一条弧

4.邻接多重表（无向图的另一种链式存储结构）

邻接表优点: 容易求得顶点和边的信息。 缺点: 某些操作不方便（如:删除一条边需找表示此边的两个结点)

结点3：与前面的相关联的 结点5：与后面的相关联的

🌲🌲🌲 好啦，这就是今天要分享给大家的全部内容了 ❤️❤️❤️如果你喜欢的话，就不要吝惜你的一键三连了~