第六章图是一种复杂的非线性结构,以下是关于本章的知识小结:
1.基本概念(各种图的比较)
无向完全图:具有n(n-1)/2条边的无向图;
有向完全图:具有n(n-1)条弧的有向图;
连通图:图中任意两个顶点都是连通的;
连通分量:无向图中的极大连通子图;
强连通图:每一对 vi 和vj ,从vi到vj 和从vj 到vi 都存在路径的有向图;
连通图的生成树:一个极小连通子图,含有图中全部顶点,有n-1条边;一颗有n个顶点的生成树有且仅有n-1条边
2.图的存储结构
邻接矩阵
(图没有顺序存储结构,但可以借助二维数组来吧表示元素间的关系)
当边上没有权重时,邻接矩阵中用0表示边不存在和1表示边存在;
当边上有权重时,数组元素都初始化为极大值,再将对应位置改为对应边上的权重。
邻接矩阵表示方法的优缺点:
(1)优点
便于判断两个顶点之间是否有边;便于计算各个顶点的度,对于有向图,第i行元素之和就是顶点i的出度,第i列元素之和就是顶点i的入度。
(2)缺点
不便于删除和增加顶点;空间复杂度高。
邻接表
图的链式存储结构,邻接表由两个部分组成:表头结点表和边表
表头结点
边结点
邻接表
具体代码:
邻接表表示法的优缺点:
(1)便于增加和删除结点;便于统计边的数目;空间效率高。
(2)不便于判断顶点之间是否有边;不便于计算有向图各个顶点的度。
3.图的遍历
深度优先搜索
过程:(1)从顶点出发,访问顶点;(2)访问刚访问过的顶点的第一个未被访问的邻接点,以该顶点为新顶点,重复此步骤,直到刚访问过的顶点没有被访问的邻接点为止;(3)返回前一个访问过的且仍有未被的访问的邻接点的顶点,找出该顶点的下一个未被访问的邻接点,访问该顶点;(4)直至所有顶点都被访问过,搜索结束。
深度优先搜索遍历连通图(根据不同的存储结构算法会有所不同)
采用邻接矩阵表示:
采用邻接表表示:
深度优先搜索遍历非连通图
有多少次调用dfs函数,就说明图中有多少个连通分量。该函数主要是通过遍历顶点表,找出未被访问的顶点,保证所有连通分量都能进行搜索。
广度优先搜索
类似于树的按层次遍历的过程,先访问的顶点其邻接点也先被访问,算法实现的时候需要用到队列保存已被访问过的顶点。
广度优先搜索遍历连通图(根据不同的存储结构算法会有所不同)
采用邻接矩阵表示:
采用邻接表表示:
广度搜索非连通图的算法与深度搜索非连通图一样
4.图的应用
最小生成树
在一个连通网的所有生成树中,各边的代价之和最小的那颗生成树称为该连通网的最小代价生成树。
普里姆算法(加点法)
利用辅助数组closedge记录从U到V - U具有最小权值的边
利用普里姆算法画出最小生成树的一些体会:
①从顶点出发,在顶点与其邻接点中找到权值最小的边,并找出邻接点
②继续找出该邻接点与其邻接点权值最小的边,每次选择最小边的时候,可能存在多条权值相同的边可以选,则任选其一即可
③找到最小边后还要比较上一个邻接点与其下一个邻接点之间是否存在权值更小的边,再继续向下执行
④直到所有的点都被访问且为连通图时结束
克鲁斯卡尔算法(加边法)
利用克鲁斯卡尔算法画出最小生成树的一些体会:
①找出所有边中权值最小的边,若该边依附的顶点落在不同连通分量上,则此边可用,否则舍弃掉
②重复操作1,直到所有顶点都在一个连通分量上
我个人觉得加边法比加点法简单且不容易出错,加点法很可能会出现遗漏,只需要画图的时候在脑海里刷新数组还是比较困难的,而加边法只需要是否在同一连通分量上即可。普里姆算法更适合用于求稠密图的最小生成树,克鲁斯卡尔算法更适合用于求稀疏图的最小生成树。
最短路径
迪杰斯特拉算法
求源点到其他所有顶点的最短路径
①初始化
将vi数组初始化为false,源点初始化为true;将dist数组初始化为最大值,将源点的邻接点在dist数组的相应下标初始化为边的权值
②循环n-1次
找出下一条最短路径的终点,若由于该点的加入能贡献更小值,则刷新dist数组
③直到vi数组全为true时结束
上次的目标是好好学习图,多打代码,完成情况较好,对于dfs和bfs能分别用邻接矩阵和邻接表实现对非连通图的搜索,不过解决图的一些实际问题还是有些困难的,这次的目标是能自己打出普里姆算法和克鲁斯卡尔算法的代码。