64.《oj-图绪论》

简单的分为四大点内容

1 概念

有向图和无向图

完全图 无向图 n(n-1)/2条边 有向图 n(n-1)条边 注意要和后面的连通区别开

连通图(无向图)和强连通图(有向图)及其分量 注意 连通即指两点之间可以连通 如2和3通过1可以连通 区别不同于完全图 整体就是一个连通分量

还有一些小概念：
1.连通图的生成树是一个极小连通图(连通且边数最少的子图) 顶点数n 则生成树含有n-1条边
2.无向图的全部顶点度之和等于边数的2倍
3.有向图顶点的度为出度和入度之和 全部顶点的出度和入度之和相等
4.稠密图(邻接矩阵法 Prim算法) 稀疏图(邻接表法 Kruskal算法)
5.若一个图有n个顶点且有大于n-1条边 此图一定有环
6.顶点不重复出现的路径称为简单路径

看一些考题：

一个有28条边的非连通无向图至少有几个顶点

具有6个顶点的无向图 当有几条边时可以确保为一个连通图
同上面一个题一样就是反过来了

无向图有23条边 度4的顶点5个 度3的4个 其余都是度2的顶点 则含有多少个顶点
这个利用的就是第2条知识点：无向图的全部顶点度之和等于边数的2倍
23x2-4x5+3x4=14 14/2=7 7+5+4=16个

如下图有向图 有几个强连通分量
强连通分量即有向图的极大强连通子图

2 邻接矩阵法(二维数组存储)和邻接表法(链式存储)

两张图搞定：

总结的一些小技巧：
1.对于无向图邻接矩阵 顶点的度为一行非0元素的个数 即相关边的个数
2.对于无向图邻接表 顶点的度对应一行边表结点数
3.对于有向图邻接矩阵 顶点的度为一行一列非0元素之和
4.对于有向图邻接矩阵 顶点出度为一行非0元素之和 入度为一列非0元素之和
5.对于有向图邻接表 容易算出顶点的出度
6.无向图的邻接矩阵一定是一个对称矩阵
7.无论有向图还是无向图 邻接矩阵都唯一
8.无向图 存储空间为O(|V|+2|E|)  V顶点集 E边集
9.无向图 存储空间为O(|V|+|E|)
10.不太考察的 十字链表(有向图) 邻接多重表(无向图)

很抽象吧 直接做题就能很容易理解：

若图邻接矩阵中主对角线上元素皆为0 其他皆为1 则该图一定是...
每两个相连 为完全图

每个顶点的度是多少
先判断是无向图还是有向图 然后再求解

3 广度优先搜索(BFS) 深度优先搜索(DFS)

这个无法写出来 只能图来表示更容易理解
1.BFS类似于二叉树的层序遍历
2.DFS类似于数的先序遍历(递归算法)
3.BFS和DFS算法时间复杂度 基于邻接矩阵时O(|V|^2) 基于邻接表时O(|V|+|E|)
4.基于邻接矩阵的遍历得到的BFS和DFS序列唯一
5.基于邻接表遍历得到的BFS和DFS序列不唯一

无向图G=(V,E) V={a,b,c,d,e,f} E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)} 则从a开始进行深度优先遍历 得到的顶点序列为
最好的方式就是根据以上信息画出无向图G 当然也可以通过选项快速排除
例如：abecdf 错误 abe 和e相连的且没有访问过的只有d 所以错误
acfebd acf 和f相连且没有访问过的只有d 所以错误

如下图 深度优先遍历得到的不同个数为几个

以下邻接表 画出其深度优先生成树和广度优先生成树

4 最小生成树 最短路径 拓扑排序

最小生成树：
1.当存在权值相同的边 最小生成树可能不唯一
2.当各边权值互不相等 最小生成树唯一
3.Prim算法Kruskal算法
4.Prim算法时间复杂度 O(|V|^2)
5.Kruskal算法时间复杂度 O(|E|log2为底|E|)

Prim算法Kruskal算法(最小生成树)

Prim算法 就是找顶点集合 然后加入距离最近的顶点（选顶点）
注意要加入选取的是未选取过的顶点

Kruskal算法 就是选边集合 加入两边的顶点（选边）
注意选取的边两端顶点是不在一个连通分量里的

题目：

15统考真题 带权最小代价(生成)树 可能是Kruskal算法第2此选中但不是Prim算法（从V4开始）第2次选中的边是()

Kruskal算法和Prim算法下面无向图的最小生成树

最短路径

1.单源最短路径：某一顶点到其他各顶点的最短路径 Dijkstra算法
2.每对顶点间的最短路径 Floyd算法
3.Dijkstra算法不适用于边上带负权值
4.Floyd算法不适用于包含总权值为负的回路
5.Dijkstra算法时间复杂度 O(|V|^2)
6.Floyd算法时间复杂度 O(|V|^3)

Dijkstra算法对于有向带权图 从源点a到其他各顶点最短路径 第一条最短路径目标顶点b 第二条为c 其余最短路径目标顶点依次是
就是不断的找最短路径 然后一直往下找 顺便更新最短路径

Floyd算法基本很简单 也不怎么考察
肉眼就可以观察出来任意两点的最短路径

题目：

2021统考真题 使用Dijkstra算法从顶点1到其余各顶点的最短路径 将当前找到的从顶点1到顶点2,3,4,5最短路径长度保存在数组dist中 求出第二条最短路径后 dist内容更新为什么

拓扑排序(有向无环图)

1.拓扑排序的结果可能不唯一
2.对于一般图来说 若其邻接矩阵是三角矩阵 则存在拓扑序列
3.拓扑排序的步骤就是 找入度为0的顶点删除相关有向边 依次往下进行直到没有顶点
4.逆拓扑排序就是反过来 找出度为0的顶点倒退删除

直接看题：

下图进行拓扑排序 可得到不同的拓扑序列个数是多少

关于拓扑排序说法错误的
1.强连通图(顶点数大于1)不能进行拓扑排序
2.一个有向图的拓扑序列中 若顶点a在b之前 图中必有一条弧<a,b>

结束！！！