考研数据结构笔记：图的基本概念与存储结构
考研数据结构笔记：图的基本概念与存储结构
图是数据结构中一种重要的非线性结构，广泛应用于各种实际问题的建模。本文将系统地介绍图的基本概念、性质以及常见的存储结构，帮助读者全面理解图这一数据结构。
一、图的基本概念
1.1 基本图术语
有向图：图的边是有向边。记为**<v,w>**：有向边从顶点v和顶点w的弧。表示v弧尾，w为弧头。
无向图：图的边是无向边。记为(v,w)：无向边从顶点v和顶点w的弧。v，w都表示顶点。
简单图：①不存在重复边②不存在顶点到自身的边
完全图：无向图中，每两个顶点之间都得有边。有向图中，每两个顶点之中都存在方向相反的两条弧
子图：就是一个整图的一部分，但是必须子图也是图。且也就是说边和顶点需要一起出现。
1.2 关于度的性质
无向图：几条边就是几个度（全部顶点的度的和等于边数的两倍）d=2e
有向图：某顶点的度=出度数+入度数（全部顶点的度=所有顶点出度+入度）
1.3 关于路径及距离
路径：从一个顶点到另一个顶点之间的一条顶点序列。（经过的点的序列）
路径长度：路径上边的数目。
回路/环：从第一个顶点到最后一个顶点相同的路径。
距离：从一个顶点到另一个顶点若存在最短路径，则称此路径长度为距离。
简单路径：顶点不重复出现的路径。
简单回路：顶点不重复出现的回路。
1.4 关于连通图及连通分量
该概念针对无向图
连通：从顶点v到顶点w有路径存在，则v和w是连通的
连通图：图G中，任意两个顶点是连通的，则称为连通图。边数大于等于n-1。
连通分量：无向图中极大连通子图成为连通分量。
极大连通子图：就是连通分量。子图尽可能多的包含的顶点和边。
极小连通子图：边数最少，图又连通的子图。
非连通图：图中有n个顶点，边数小于n-1，则为非连通图。
1.5 关于强连通图及强连通分量
该概念针对有向图
强连通：从顶点v到顶点w和从顶点w到顶点v之间都有路径。
强连通图：图中任意顶点都是强连通的。
强连通分量：有向图中的极大强连通子图。
1.6 生成树，生成森林
连通图的生成树是包含图中全部顶点的一个极小连通子图。
若图的顶点数为n，则它得生成树含有n-1条边。
若这棵树砍掉一条边，变为非连通图；这棵树加上一条边会变成回路。
非连通图中，连通分量的生成树就成为非连通图的生成森林。
1.7 经典例题
- 务必熟记有向图和无向图的完全图的边数两个公式
二、图的存储
2.1 邻接矩阵法
概念
用一维数组存储图中顶点信息。二维数组存储边的信息（各顶点之间的邻接关系）
#define MaxVertexNum 100 //顶点数目最大值
typedef char VertextType; //顶点的数据类型
typedef int EdgeType; //带权图中权值和数据类型
typedef struct{
VerTexTyoe Vex[MaxVertexNum]; //顶点表
EdgeType Edge[MaxVertexNum][MaxVertexNum];//邻接矩阵，边表
int vexnum,arcnum;//图的当前顶点数和弧数
}MGraph;
性质
邻接矩阵表示法的空间复杂度为O(n²)，n为顶点数}|V|
无向图的邻接矩阵中行或者列表示顶点的度
有向图的邻接矩阵中行表示出度，列表示入度。出度数加入度数才等于有向图的度
邻接矩阵的时间复杂度与顶点数有关。
稠密图适合邻接矩阵，
计算度和找边的关系必须进行遍历
2.2 邻接表法
概念
主要有两个部分组成，顶点表和边表。
边表：某个顶点依附的顶点。即出度
顶点表：某个图中所有的顶点。
#define MaxVertexNum 100
typedef struct ArcNode{ //图中顶点数目的最大值
int adjvex; //边表结点
struct ArcNode *next;//该弧所指向的顶点的位置
}ArcNode;
typedef struct VNode{ //顶点表结点
VerTexTyoe data;//顶点信息
ArcNode *first; //指向第一条依附该顶点的弧的指针
}VNode,AdjList[MaxVertexNum];
typedef struct{
AdjList vertices; //邻接表
int vexnum,arcnum;//图的顶点数和弧数
}ALGraph;
性质
若为无向图，则所存储的空间为O(V +2E)；若为有向图，则所存储空间为O(V+E)。 （无向图需要存储两次边）
邻接表中给定一个顶点，出度很容易找，但是入度非常复杂。花费的时间为O(n)
图的邻接表表示法并不唯一，因为每个顶点对应的单链表，各边结点的链接次序可以任意。
适合稀疏图
2.3 十字链表法（考的少）
- 十字链表是有向图的一种链式存储结构。对于有向图每条弧有一个结点，对于每个顶点都有一个结点。
2.4 邻接多重表（考的少）
- 邻接多重表是无向图的另一种链式存储结构。
三、图的基本概念及存储常见考点
含有n个顶点和e条边的无向图的邻接矩阵中，零元素的个数为n²-2e
一个图的邻接矩阵表示唯一，邻接表表示不唯一
邻接表有奇数个边表结点，则图为有向图
在有向图的邻接表存储结构中，顶点v在边表中出现次数为顶点v的入度
n个顶点的无向图的邻接表最多有n(n-1)个边表结点。一个顶点n个n-1边表
n个顶点，e条边的有向图用邻接表表示，则删除某个顶点v相关的所有边的复杂度为O(n+e)
数据结构是计算机科学的基础，图作为其中的重要组成部分，其概念和存储方式需要深入理解和掌握。通过本文的学习，希望读者能够建立起对图这一数据结构的全面认识，并为后续的算法学习打下坚实的基础。