【★★★★★ 第6章 图总结笔记 2022 9.13】

1. 图的概念

1. 图的概念：图G由顶点V和边集E组成，记为G=(V,E) ;|V|表示图G中顶点的个数，E={（u,v）|u，v都属于V} ，|E|为图中G的条数； 线性表是可以是空表，树可以是空树，但是图不能是空图图中不能一个顶点也没有，图的顶点V一定非空，但是边E可以为空
2. 有向图，若E为有向边(也称为“弧”)的有限集合时，则G为有向图，弧是顶点的有序对，记为 v是弧尾，w称为弧头；可以记为 G1=(V1,E1); V1,={1,2,3} ;E={<1,2>,<2,1>,<2,3>}
3. 无向图：E是无向边简称为边的有限集合时，G称为无向图，边是顶点的无序对，表示为;E={（1,2）,（2,1）,（2,3）}
4. 简单图与多重图：
   简单图 - 不存在重复边
   - 不存在顶点到自身的边 就是简单图
   多重图 - G中某两个顶点之间的边数大于1，且允许顶点通过一条边和自身关联
5. 完全图 对于无向图 |E|的取值为0- (n(n-1))/2条边的无向图就是完全图，任意顶点之间都存在边； 对于有向图，|E| 的取值为0-n(n-1),任意两个顶点之间都存在方向相反的两条弧
6. 子图 G2是G1的子图就是说，G2中顶点是G1顶点的子集，G2中E为G1中边的自己，则称为G2是G1的子图； 不是V和E的任何子集都可以构成G的子图，因为子集可能不是图，就是说E的子集这种某些边关联的顶点可能不在V的子集中
7. 连通和连通图 连通分量（无向图） 图G中任意两个顶点都是连通的，则称为连通图，否则就是非连通图，无向图中的极大联通子图称为连通分量； 如果一个图有n个顶点，边数小于n-1，一定是非连通图
8. 强连通图、强连通分量(有向图) 有一对顶点w,v,从w到v和从w到v之间都有路径，则称为这两个顶点是强连通的，如果任何一对顶点都是强连通图，则称为强连通图； 有向图中的极大强连通子图称为强连通分量； 【==考点：对于n个顶点的无向图，如果G是连通图，则最少有n-1条边，如果是非连通图，则最多可能有 C n-1 ² ==】 【考点对于n个顶点的有向图，如果G强连通图，则最少有n条边】
9. 顶点的度 入度和出度 对于无向图，每个顶点的度就是依附于该顶点的边的条数|| 全部顶点的度的和等于边数的二倍； 对于有向图，顶点的度分为入度和出度， 顶点的度等于入度+出度； 有向图的全部顶点的入度之和=出度之和=边数
10. 稠密图和稀疏图 边数很少的就是稀疏图，反之就是稠密图，一般情况下图G满足|E|<|V|log|V|时，G就被视为稀疏图
11. 简单路径和简单回路 简单路径就是：路径序列中，顶点不重复出现的路径称为简单路径； 简单回路：除第一个顶点和最后一个顶点外，其余顶点都不重复出现的回路称为简单回路
12. 连通图的生成树是包含图中全部顶点的极小连通子图
    13.
13. 非连通图中，连通分量的生成树构成了非连通图的生成森林。
14. 一个顶点的入度为0，其余顶点的入度均为1的有向图称为有向树
    做题总结：

• 图的路径是 由顶点和相邻顶点的序偶构成的边所形成的序列
• 一个n个顶点n条边的无向图一定是 有环的
• 从无向图的任意顶点出发进行一次dfs就可以访问所有顶点，该图一定为 连通图
• 图和树的区别在于 图和树的区别是逻辑结构的区别，
• 如果图非连通，则从某一顶点出发无法访问其他全部顶点
• 无向图的极大连通子图称为连通分量
• 强连通有向图的任何顶点到其他所有顶点都有路径，不一定有弧度(意思就是说 顶点之间可以有路径一个点到另一个点，A可以A->B，B但是B不一定能B->A)
• 无向图n个顶点e条边，则全部顶点的度为边数的二倍 TD(v)和等于2e，有向图是全部顶点的入度之和=出度之和；
• 有向完全图一定是强连通有向图
• 一个有28条边的非连通无向图至少有多少个顶点； 思路：最少为一个完全图加一个独立的点构成， 28=[n*(n-1)]/2 ->n=8 8+1等于9个顶点最少
• 灵活运用无向图TD(v)的和等于2e；
• n个顶点的有向图，顶点的度等于入度+出度， 任意一个顶点最多还可以与其他n-1个顶i但有一对相反边相连 即 2*(n-1)
• 一个连通图的生成树是一个极小连通子图(包含全部的顶点)，则肯定是无环的， 极大连通子图（包含全部的边）称为连通分量
• n个顶点的生成树具有n-1条边是极小连通子图，因为n个顶点构成的环有n条边，去掉任意一个边就是一棵生成树，所以共有n棵不同的树
• 求n个顶点e条边的无向图是一棵森林，问森林中有多少棵树 ， 假设有x棵树，那么用x-1条边就能把所有的树连成一棵树了，此时 顶点数=边数+1 则e+x-1+1=n ,则x等于n-e；
• 无向连通图的特性：所有顶点的度之和为偶数 因为所有顶点的度之和等于边数的2倍
• 简单回路是简单路径，回路是路径
• 存储稀疏表应该用邻接表； 有向图中存在拓扑序列，则该图不存在回路

2.图的存储结构

邻接矩阵法(存储稠密图)

邻接矩阵存储指的是用一个以为数组存储图中顶点的信息，用一个二维数组存储图边的信息，存储顶点之间邻接关系的二维数组称为邻接矩阵；
邻接矩阵存储结构定义如下：

#define MaxVertexNum 100
typedef char VertexType;
typedef int EdgeType;
typedef sturct MGraph{
   VertexType Vex[MaxVertexNum];
   EdgeType Edge[MaxVertexNum ][MaxVertexNum ];
   int vexnum,archnum;
}MGraph;
1
2
3
4
5
6
7
8

邻接矩阵的特点：

1. 无向图的邻接矩阵是对称矩阵，并且唯一因此实际存储邻接矩阵只需要存储上或下三角矩阵的元素；
2. 对于无向图，第i行或者第i列的非零元素个数正好是顶点的度
3. 对于有向图第i行非零元素是顶点的出度，第i列非零元素的个数是顶点的入度
4. 邻接矩阵存储图，很容易确定图中任意两个顶点之间是否有边，但是确定图中有多少边，必须按行、按列对每个元素进行检测，费时；
5. 稠密图适合用邻接矩阵表示

邻接表法(存储稀疏图)

图为稀疏图时，用邻接矩阵会浪费大量的空间，图的邻接表法结合了顺序存储和链式存储方法，会减少浪费；

邻接表存储的特点：

• G为无向图所需要的存储空间为O(|V|+2|E|);有向图所存储的空间为O(|V|+|E|)；因为无向图中每条边在邻接表中出现了两次
• 存储稀疏图用邻接表
• 在邻接表中给定一个顶点可以很快的找到他的邻边，因为只需要读取他的邻接表，时间为O(n)；而确定给定的两个顶点上是否有边，在邻接矩阵中很快可以查到，而在邻接表中要在相应的结点对应的边表查找另一个结点； 简而言之，因为存储结构不同，所以邻接矩阵可以很快的查找两个顶点之间是否有边，但是不能确定图中有多少条边； 而邻接表可以很容易查找到一个顶点所连接的所有边，但是要查两个顶点之间有没有边，则要查找对应的结点的边表中是否有另一个结点
• 在有向图邻接表中，求一个给定顶点的出度只需要计算邻接表中的结点个数即可； 但是要求其顶点的入度，要遍历所有邻接表，
• 图的邻接表表示不唯一，因为各边的结点的链表次序可以是任意的，它取决于建立邻接边的算法和边的输入次序；

十字链表

十字链表是有向图的一种链式存储结构。

在十字链表中，既然容易找到Vi为尾的弧，又容易找到Vi为头的弧，容易得出顶点的出度和入度； 十字链表的表示不唯一，但是十字链表表示确定一个图

邻接多重表

邻接多重表是无向图的另一种存储结构
在邻接多重表中容易求得顶点和边的各种信息，但是在邻接表中求两个顶点之间是否存在边而对边执行删除等操作时，需要分别在两个顶点的边表中遍历，效率较低
邻接多重表和邻接表的差别在于：同一条边在邻接表中用两个结点表示，在邻接多重表只有一个结点