图论知识点集合
图论知识点集合
在博客内查看
什么是图
图是由若干给定的顶点及连接两顶点的边所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系。顶点用于代表事物，连接两顶点的边则用于表示两个事物间具有这种关系。
图又分为有向图和无向图。有向图就是只有有向边的图，无向图是只有无向边的图。如果一个图里有向边和无向边都有，那么我们称它为混合图。
图的存储方式
1. 邻接矩阵
把一个点到另一个点的边的权值（没有权值就按题目要求存）存在一个二维数组里。具体实现方法如下：
//定义
int e[MAXN][MAXN];//实现：存一条连着点x和点y的权值为v的边
cin>>x>>y>>v;
e[x][y]=/*e[y][x]=*/v;
//如果是无向边就把上面注释去掉优点：使用简单舒服巴适。
缺点：两点间再多一边就要爆炸；对于稀疏图空间再稀一点空间复杂度就要爆炸。
2. 邻接表(vector)
把一个点到另一个点的边的权值（没有权值就按题目要求存）用一个点的下标存这个点指向的那一的点和边的权值（无向图需要再反过来存一遍）。
可以用数组链表向量实现就看你怎么存，这里用向量（vector）：
//定义
struct edge{
int t,v;//t是边指向的点，v是边的权值
};
vector<edge>e[MAXN];
//vector<int>e[MAXN];（边无权值时的存储方式：直接存边指向的点就行）//实现：存一条连着点x和点y的权值为v的边
cin>>x>>y>>v;
e[x].push_back((edge){y,v});//"(edge)"在c++11以上的编译器中可以不需要
//如果是无向边就在这加一条"e[y].push_back((edge){x,v});"优点：（vector）对于稀疏图非常吃香，不会浪费空间，遍历时间也比邻接表短等。
缺点：对于稠密图啥的可能就会被噶。
3. 链式前向星
其实每个点为起点的边都是一个链表：
//定义
struct edge{
int t,v,next;
}e[MAXN];
int head[MAXN],cnt;//初始化
memset(head,-1,sizeof(head));
cnt=0;//实现：存一条连着点x和点y的权值为v的边
cin>>x>>y>>v;
e[cnt]=(edge){y,v,head[x]},head[x]=cnt++;
//如果是无向边就在这加一条"e[cnt]=(edge){x,v,head[y]},head[y]=cnt++;"优点：很优秀的数据结构，比 vector 吃香。
缺点：邻接表你说呢？
图（树）的遍历
1.\textrm{Dfs}
扫到底就完事了（代码只贴图的）：
void dfs(int x){
if(x>n||b[x]) return;
b[x]=1;
cout<<x<<' ';
for(int i=0;i<a[x].size();i++) dfs(a[x][i]);
}2. \textrm{Bfs}
用队列记录层数，一层一层扫（还是只贴图的呵呵）：
void bfs(){
q.push(1),b[1]=1;
while(!q.empty()){
int x=q.front();
cout<<x<<' ';
q.pop();
for(int i=0;i<a[x].size();i++) if(!b[a[x][i]]) q.push(a[x][i]),b[a[x][i]]=1;
}
}树
图的一个分支。
二叉树
就是一棵每个节点都最多只有两个叶子节点的树。
堆
一颗按升序排列或降序排列的二叉树，可以用优先队列实现（代码贴优先队列的）：
//大根堆
priority_queue<int>q;//小根堆
priority_queue<int,vector<int>,greater<int> >q;表达式树
二叉树，叶子节点只能是数，其他节点只能是运算符的二叉树。
并查集
用来找一个点的根节点的东西，分为查和并两个操作（一句话概括并查集（非原创）：你爸爸的爸爸还是你爸爸）。（最小生成树放后面讲）
查：递归查找祖先；并：把两个点的两个祖先变成他们之中的一个：
//定义
int fa[MAXN];//实现
int find(int x){//查
return fa[x]==x?x:fa[x]=find(fa[x]);
}
void connent(int x,int y){//并
int fx=find(x),fy=find(y);
if(fx!=fy) fa[fx]=fy,m--;
}//操作
//把两数合并合并的操作
cin>>x>>y;
connent(x,y);
//查询某数的辈分最高的祖先的操作
cin>>x;
cout<<find(x);
//判断两数是否有公共祖先的操作
cin>>x>>y;
if(find(x)==find(y)) cout<<"Yes";
else cout<<"No";最短路
求图中两个点之间的最短路径。
多源最短路
求图中任意两点之间的最短路径。
\large\textrm{Floyd}
一个基于贪心的求最短路的算法。可以用暴力或堆优化实现。
也是一个类似于广搜的优化。为了消除无用的松弛操作，发明这个算法的人真的是费尽了心机思。
由于只有上一次被松驰的点所指向的点才有可能引起下一次松弛操作。所以用队列来维护那些可能引起松弛操作的点就能完美的消除无用的松弛操作了：
//定义
int f[MAXN];
bool v[MAXN];
struct edge{
int t,v;
};
vector<edge>e[MAXN];
queue<int>q;//实现（求s点到其他各点的最短路）
memset(f,0x3f,sizeof(f));
memset(v,0,sizeof(v));
f[s]=0;
q.push(s);
while(!q.empty){
int x=q.front();
q.pop();
v[x]=0;
for(auto a:e[x]){
if(f[a.t]>f[x]+a.v){
f[a.t]=f[x]+a.v;
if(!v[a.t]){
v[a.t]=1;
q.push(a.t);
}
}
}
}时间复杂度：
空间复杂度：
总结
| 类型 | 多源最短路 | 单源最短路 | 单源最短路 | 单源最短路 |
| 时间复杂度 | 暴力： |
|||
| 空间复杂度 | ||||
| 能否处理负权图 | 能 | 否 | 能 | 能 |
| 基于的算法 | 贪心 |
拓扑排序
拓扑排序就是给图中所有结点排序，形成一个线性序列。
给定一张有向无环图（
理解起来也很简单。生活中也有很多事情在做之前必须要做别的事。比如说，你妈让你在打篮球之前把房间的地板打扫干净（设打扫房间的最后一步是拖地），你要想拖地还先得得扫一遍地，倒垃圾需要扫地的辅助。所以我们就可以得到如下一张图：
显而易见的，此图的拓扑序有：
\textrm{扫地}\to\textrm{倒垃圾}\to\textrm{拖地}\to\textrm{洗拖把}\to\textrm{打篮球} \textrm{扫地}\to\textrm{拖地}\to\textrm{洗拖把}\to\textrm{倒垃圾}\to\textrm{打篮球} \textrm{扫地}\to\textrm{拖地}\to\textrm{洗拖把}\to\textrm{倒垃圾}\to\textrm{打篮球} \textrm{扫地}\to\textrm{拖地}\to\textrm{倒垃圾}\to\textrm{洗拖把}\to\textrm{打篮球}
求拓扑序：\textrm{Kahn} 算法
把出度为
//定义（in存点的入度，ans存拓扑序，cnt存拓扑序的长度）
int in[MAXN],ans[MAXN],cnt;
vector<int>e[MAXN];
queue<int>q;//初始化
cin>>x;
e[i].push_back(x);
in[x]++;
/********以上是输入部分，以下是初始化的入队部分********/
for(int i=1;i<=n;i++) if(!in[i]) q.push(i);//实现
while(!q.empty()){
int x=q.front();
q.pop();
ans[++cnt]=x;
for(auto a:e[x]){
in[a]--;
if(!in[a]) q.push(a);
}
}
if(cnt<n) cout<<"No";
else for(int i=1;i<=n;i++) cout<<ans[i]<<' ';时间复杂度：
最小生成树
\textrm{Kruskal}
从边入手的求最短路的算法。
基于贪心：从小到大加边。加边、合并、查找的操作都基于并查集。
给边的权值排序，再从小到大（最大生成树反过来）扫一遍，计数到
//定义
int fa[MAXN];
struct edge{
int s,t,v;
}a[MAXN];
bool cmp(edge x,edge y){
return x.v<y.v;
}//实现
sort(a+1,a+m+1,cmp);
int sum=0,egs=0;
for(int i=1;i<=m;i++){
int fs=find(a[i].s),ft=find(a[i].t);
if(fs!=ft){
sum+=a[i].v,egs++;
fa[fs]=ft;
if(egs==n-1) return sum;
}
}
return -1;时间复杂度：
\textrm{Prim}
算法思想和
跑得较 （其实是我不会打）