2023.3.27
2023.3.27--图のreview
今天早上修复了blog:
原先出现的问题是:在上传文件后对文件进行了修改,可能导致CSS渲染文件或者js文件出错。然后hexo寄了。
修复的方法是:Hexo的安装及重置恢复_怪异收集者的博客-CSDN博客。所以change一个主题,然后就好啦!但是需要自己
改一下config.yml
(也可以把之前的copy一下放到新的主题文件夹内),但是我干脆就换了一个了。
看看现在的:
图的概念
简单图:无自环,无重边。
子图:边的子集,以及相关联的点集。
度(Degree)
在无向图中,顶点的度是其邻接点的数目。
在有向图中。(入度)指向这个顶点的弧的数目,(出度)此顶点指向其他顶点的弧的数目。该顶点的度=出度+入度。
邻接与路径
在无向图中,存在一条边(u,v):则称u和v邻接。
在有向图中,存在一条边<u,v>:则v是u的邻接点。
路径:图上一个顶点序列,其中序列上任意相邻两点都邻接。
简单路径:顶点和边==不重复出现==。
环:除了顶点和终点相同外没有重复顶点的路径。
连通和连通分量
连通(connected):如果无向图中任意两点都有路径,则图是连通的;否则是非连通的。
非连通图有多个连通分量。==连通与非连通是无向图上的概念,有向图是强连通和弱连通。==
强连通图:有向图中任意两点都有相互可达的路径。
相互可达的子图属于同一个强连通分量(scc)。
树(连通无向无环图)
==树可以 以任意点作为根==。
下面是一些定理:
G上有V个点,有V-1条边,还是一个无环图,那么它一定是连通的。
反过来也成立:G上有V个点,有V-1条边,还是连通的,那么它一定是无环图。
G连通,但认一删除一条边后不连通。
G无环,但任意添加一条边后包含环。
任意两点只有唯一的简单路径。
简单路径:顶点和边==不重复出现==。
稀疏图与稠密图
如何划分稀疏图与稠密图?假设考虑有向图:G=<V,E>那么\(E=V^2\)数量级是稠密图。
- 稀疏图:边数E和\(\frac {V(V-1)}{2}\)相比非常少(V,E同数量级)
- 时间复杂度为\(O(ElogE)\)和\(O(V^2)\)的算法:对稀疏图来说前者好,对稠密图来说后者好。
欧拉路径与欧拉回路
欧拉路径:只通过每条边一次的路径。
欧拉回路:如果这条路径的起点和终点是同一点。
一笔画问题。
- 对无向图:图G有一条欧拉路径,当且仅当G是连通的,且有0 or 2 个奇度数节点。当所有节点都是偶度数时欧拉回路七点可以是任意点。
- 对有向图:存在欧拉路径的条件:图连通,所有点出度=入度,or 有一个终点的入度-出度=1,一个起点的出度-入度=1。当所有点出度=入度是任意点可作为起点,而后者必须以出度-入度=1的点作为起点,入度-出度=1的点作为终点。
图的存储
边列表
基本上题目给出的就是这种形式,但是这种形式并不是很好处理。
邻接矩阵
1 | int G[2005][2005];//G[u][v]:u->v的边 |
邻接表
1 | //====================[vector实现]==================================// |
前向星
以储存边的方式来存储图。构造方法如下:读入每条边的信息,将边存放在数组中,把数组中的边按照起点顺序排序(可以使用基数排序,如下面例程),前向星就构造完了。通常用在点的数目太多,或两点之间有多条弧的时候。
一般在别的数据结构不能使用的时候才考虑用前向星。除了不能直接用起点终点定位以外,前向星几乎是完美的。
把边集数组终得每一条边按照起点大小排序,如果起点相同就按照终点从小到大排序。并记录下以i为起点的起始位置和以i为起点的边数(i的出度)。
head[i]
:记录以i为边集在数组终得第一个存储位置。
len[i]
:记录所有以i为起点的边在数组终得存储长度。
链式前向星--静态邻接表
1 | struct Edge{ |
P5318
小K 喜欢翻看洛谷博客获取知识。每篇文章可能会有若干个(也有可能没有)参考文献的链接指向别的博客文章。小K 求知欲旺盛,如果他看了某篇文章,那么他一定会去看这篇文章的参考文献(如果他之前已经看过这篇参考文献的话就不用再看它了)。
假设洛谷博客里面一共有 \(n(n\le10^5)\) 篇文章(编号为 1 到 \(n\))以及 \(m(m\le10^6)\) 条参考文献引用关系。目前小 K 已经打开了编号为 1 的一篇文章,请帮助小 K 设计一种方法,使小 K 可以不重复、不遗漏的看完所有他能看到的文章。
这边是已经整理好的参考文献关系图,其中,文献 X → Y 表示文章 X 有参考文献 Y。不保证编号为 1 的文章没有被其他文章引用。
请对这个图分别进行 DFS 和 BFS,并输出遍历结果。如果有很多篇文章可以参阅,请先看编号较小的那篇(因此你可能需要先排序)。
1 |
|
P3916
给出 \(N\) 个点,\(M\) 条边的有向图,对于每个点 \(v\),求 \(A(v)\) 表示从点 \(v\) 出发,能到达的编号最大的点。
好吧,看这个题并不是很难,所以速速的就完了。但是T了一个点。
1 |
|
看了看题解,主要的思路是反向建边。
1 |
|
P1807
设 \(G\) 为有 \(n\) 个顶点的带权有向无环图,\(G\) 中各顶点的编号为 \(1\) 到 \(n\),请设计算法,计算图 \(G\) 中 \(1, n\) 间的最长路径。
乐,没写完,明天再说。