此篇需要结合OneNote上的笔记进行阅读 |
---|
图的基本知识
1.树可以是空树,图不能是空图,一个图的顶点集一定是非空集,但是边集可以是空;
2.且在图中一条边必须连接两个顶点,因为如果一个顶点都不连接的话那不会构成边,只连接一个的话构不成图;
3.图分成无向图和有向图,,无向边简称边,有向边简称弧;
图的基本操作
图的基本操作的实现离不开存储结构,我们有四种不同的存储结构所以我们的具体实现也有四种但是在考研中一般只涉及到前两种的使用-邻接表和邻接矩阵也就导致我们下面的思想主要还是依靠的邻接表和邻接矩阵,且我们在此只写了无向图的思想,有向图的思想在大差不差的情况下被省略,如果差别很大会特别指出
1.Adjacent(G,x,y),判断图G是否存在边:首先声明x,y是顶点存入数组的下标
1.邻接矩阵想法: 我们直接通过传入的x和y去带入邻接矩阵的数组下标里可以直接得出是否存在边;
2.邻接表想法:先通过x定位到与之相关的两个顶点中的某一个顶点的位置,再从这个顶点的指针开始进行遍历,并对节点进行访问且取出两个顶点中的第二个顶点的信息并与传入的y的值进行比较即可;
2.Neighbors(G,x),列出G图中与节点x邻接的边
1.邻接矩阵想法:由于邻接矩阵特殊的对称性,我们对行和列的操作是相同的此下我们全部按照行进行遍历,按照行进行遍历,如果发现1则从顶点节点中找到这个字符并保存直到全部都找到;
2.邻接表的想法:直接从x开始往后进行遍历,不过这个是指针的遍历,其实大差不差,剩下的翻译过程跟上面是一样的;
3.InsertVertex(G,x),在图G中插入顶点x
1.邻接矩阵想法:如果只是插入顶点的话我们只需要往顶点数组中多写入一个数据,并且邻接矩阵关于新插入节点的边的信息全部变成0,但是还要注意我们先定x变y把列上的0给写了,然后再定y变x把行上的0给写了,要不然就相当于只写了一半(图5.1)但是其实我们邻接矩阵的初始化的时候就已经把邻接矩阵所有的地方都赋值为0了,所以我们只执行一个把他插入到顶点数组里并且让节点数量++即可;
2.邻接表想法:先将顶点数组增加一个元素,再将其first指针指向null;
4.DeleteVertex(G,x),从图G中删除顶点x
1.邻接矩阵想法:如果我们直接对其进行删除的话那么我们需要移动剩下的大量的元素耗费大量的精力,所以需要曲线救国-在顶点结构体中添加提个bool类型用于判断这个节点是否被删除,如果被删除的话我们就把他邻接矩阵里面的所有数据直接变为0即可(到知识直接构造一个结构体数组即可);
2.邻接表想法:遍历把所有要删除节点的指针全部移到后面一位上去,然后把顶点数组里面这个元素删除即可,但是这里我们也建议添加一个bool变量,否则已经写好的数据也要发生移动;
5.AddEdge(G,x,y),若无向边(x,y)或有向边<x,y>不存在,则向图G中添加该边,注意这个代码里面有个判断操作我们不写
1.邻接矩阵想法:判断略过,然后把x,y相对应的邻接矩阵上的0改成1,但是这里要注意的是邻接矩阵的中心对称的,所以我们一改就要对两个量都进行修改;
2.邻接表法:找到x所在的数组后直接将y插入即可,且注意如果是无向图的话A和B之间有一条边对应B和A之间也有一条边,所以增加一条边在邻接表里其实是增加了两条边,先在x对应的数组内插入再从y对应的数组内插入,且这里又涉及到链表的插入里面的头插法和尾插法,那鉴于目前已有的数据我们肯定选择头插法进行插入;
6.FirstNeighbor(G,x),求图G中顶点x的第一个临界点,若有则返回顶点号。若x没有邻接点或图中不存在x,则返回1;
1.邻接矩阵想法:我们是知道有几个节点的,我们横着遍历邻接矩阵的二维数组如果碰到第一个1就return否则一直到最后那个节点的位置再return 0;
2.邻接表想法:直接找后面第一个即可没有就是null;
7.NextNeighbor(G,x,y),假设图G中顶点y是顶点x的一个邻接点,返回除y之外顶点x的下一个邻接点的顶点号,若y是x的最后一个邻接点,则返回-1;
1.邻接矩阵:我们直接用x,y去定位到邻接矩阵的具体某行然后再从y的基础上进行遍历,如果有就返回没有直到超出了顶点元素个数的时候就return -1;
2.邻接表:跟上面操作一样,不过这个就需要从first这个首指针去遍历先找到y然后直接让y进行next操作,如果next是null的话那么就说明没了,如果有的话就直接返回即可;
此外图的遍历算法还包括广度优先算法和深度优先算法要注意;
图的广度优先算法(bfs)和深度优先算法(dfs)
1.BFS的实现思想:
1.用广度优先算法遍历树和图是有区别的,遍历树的时候由于树种不存在回路所以搜索下一节点时不可能搜索到已经访问过的节点;但是在对图进行BFS的时候由于图中是可能包含回路的就导致可能搜索到已经访问过的节点;所以我们需要对图的BFS在结构体中给他加上TAG;(补充:提到存储结构我们首先能想起来的就两种一种是顺序存储还有一种是链式存储,但是这两个已经不足以满足我们的需求了,学了树的存储结构以后我们应该掌握的有:顺序存储结构,顺序存储+链式存储的结构,还有转化存储的结构-把一棵普通的树转化为二叉树再进行存储,上面这三种方案在树中依次对应的是,双亲表示法,孩子表示法,孩子兄弟表示法);
2.BFS要点:
1.找到与根节点相邻的所有顶点-所用的函数是上面基本函数中的,FirstNeighbor(G,x)和NextNeighbor(G,x,y);
2.标记哪些顶点被访问过;
3.跟树的广度优先算法一样,也需要一个辅助队列;
此处的具体实现在OneNote图6.1里面;但是这个代码有个问题就是如果是非联通图的话这个代码只能找到你初始传入的那个图,另外一个图是遍历不过去的;我们可以看之前的图6.1我们定义了一个判断是否访问的visite数组,也就是说我们只需要再加上一个对visite数组的循环判断即可;
注意:如果考试中需要分析广度优先算法和深度优先算法的时间复杂度,我们不要直接进入代码而是用存储结构去进行分析-只需要记得广度优先和深度优先遍历算法的时间开销主要在对各个节点的访问和对边的寻找;;
3.广度优先生成树
1.其实就是把你进行访某节点的第一次的那条边记录下来,然后构成一棵树(只要第一次访问这个节点的那个边);
2.广度优先生成树最后生成了个啥样的树是由邻接表如何存储相关联的,你的邻接表不相同的情况下广度优先生成树也是不同的; 但是如果一个图是用邻接矩阵进行存储的话那么其广度优先生成树就是唯一的,因为邻接矩阵的存储是固定唯一的;
3.接上还有个概念叫广度优先生成森林:其实就是当你的图有两个连通分量的时候进行树的生成便会无可避免的生成森林;
2.DFS算法:
1.深度优先遍历:图的深度优先遍历算法的根本思想我们可以参考树的先根遍历算法;并且我们注意到ppt上图的深度优先遍历算法是用递归的思想写的;
2.代码实现的思想OneNote 图7.1;
3.深度优先生成树的概念跟广度优先生成树的概念是一样的;同样的深度优先生成森林跟广度优先生成森林的想法是一样的;