图论思维导图
U125568174
2023-07-26
图论
算法
图论
树图思维导图提供《图论》在线思维导图免费制作，点击“编辑”按钮，可对《图论》进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：7c70ca7c0fbf1f9ef2f3d7d8a71c21e2
思维导图大纲
相关思维导图模版
图论思维导图模板大纲
定义
图论就是在一个图中对这个图处理
算法
基础算法
深度优先搜索
广度优先搜索
其他算法
多源最短路
佛罗伊德算法（Floyd）
实现问题
在一个图当中，找出从任意一点到另外一点的最小权值
实现方法
使用动态规划，暴力计算从i到j是直走快还是绕行k结点快
时间复杂度
由于该算法暴力枚举每种情况，时间复杂度较高，达到了O(n^3)
核心框架
for(int k=1;k<=n;k++){//k表示中间节点
for(int i=1;i<=n;i++){//i表示起点
for(int j=1;j<=n;j++){//j表示终点
f[i][j]=min(f[i][j],f[i][k]+f[k][j]);//判断i到j是直接走快还是走k绕行快
}
}
}
注意点
f数组要初始化为极大值，f[i][i]初始化为0，表示自己到自己为0
三层循环一定要先从中间节点开始，否则一条路还没刷新为最小值就参与另一条路最小值的计算
单源最短路
Dijkstra算法
适用范围
边的权值均为正数的图中求取单源最短路
算法底层逻辑
使用贪心算法的底层逻辑，从到起点最近的结点开始，刷新最短路径，再到离起点第二近的开始刷新，以此类推
朴素Dijkstra
时间复杂度
循环过程中只与点有关，时间复杂度为O(n^2)
适用范围
m数量极大的图
基础代码
for(int i=1;i<=m;i++){
scanf("%d%d%d",&x,&y,&z);
a[x][y]=z;
if(x==1) dis[y]=z;
}
dis[1]=0;
for(int i=1;i<n;i++){
int mind=INT_MAX,u;
for(int j=2;j<=n;j++){
if(mind>dis[j]&&book[j]==0){
mind=dis[j];
u=j;
}
}book[u]=1;
for(int v=2;v<=n;v++){
dis[v]=min(dis[v],dis[u]+a[u][v]);
}
}
for(int i=1;i<=n;i++){
cout<<dis[i]<<" ";
}
邻接表优化
目的
由于输入过程中使用邻接矩阵，浪费空间及时间，因此可以改用之前学过的单链表作为邻接表使用
优化方案
for(int i=1;i<=m;i++){
scanf("%d%d%d",&u[i],&v[i],&w[i]);
ne[i]=f[u[i]];
f[u[i]]=i;
}
堆优化Dijkstra
时间复杂度
使用了priority_queue，时间复杂度变为O（mlog2(n)）
适用范围
m与n在一个数量级的图
实现
#include<bits/stdc++.h>
using namespace std;
const int N=20010,M=20010;
int e[M],w[M],ne[M],h[N],idx,book[N],dis[N],n,m;
void add(int a,int b,int c){
e[idx]=b;
w[idx]=c;
ne[idx]=h[a];
h[a]=idx;
idx++;
}
void Dijkstra(){
memset(dis,0x3f,sizeof(dis));
dis[1]=0;
book[1]=0;
for(int i=1;i<n;i++){
int mind=0x3f3f3f3f,s;
for(int j=1;j<=n;j++){
if(mind>dis[j]&&book[j]==0){
mind=dis[j];
s=j;
}
}
book[s]=1;
for(int j=h[s];j!=-1;j=ne[j]){
dis[e[j]]=min(dis[e[j]],dis[s]+w[j]);
}
}
}
int main(){
memset(h,-1,sizeof(h));
int a,b,c,k;
cin>>n>>m;
for(int i=1;i<=m;i++){
scanf("%d%d%d",&a,&b,&c);
add(a,b,c);
add(b,a,c);
}
Dijkstra();
if(dis[n]!=0x3f3f3f3f) cout<<dis[n];
else cout<<-1;
return 0;
}
/*
堆优化（vector）
使用一个vector数组来进行存储，替换静态数组
#include<bits/stdc++.h>
using namespace std;
const int N=2010,M=20010;
int book[N],dis[N],n,m;
typedef pair<int,int> PII;
priority_queue<PII,vwctor<PII>,greater<PII>> heap;
vector<PII> G[N];
void Dijkstra(){
memset(dis,0x3f,sizeof(dis));
dis[1]=0;
heap.push({0,1});
while(!heap.empty()){
auto t=heap.top;
heap.pop();
int u=t.second;
if(book[u]) continue;
book[u]=1;
for(auto edge:G[u]){
int v=edge.first;
int w=edge.second;
if(dis[v]>dis[u]+w){
dis[v]=dis[u]+w;
heap.push({dis[v],v});
}
}
}
}
int main(){
//freopen("candy.in","r",stdin);
//freopen("candy.out","w",stdout);
int a,b,c;
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a>>b>>c;
G[a].push_back({b,c});
G[b].push_back({a,c});
}
Dijkstra();
if(dis[n]!=0x3f3f3f3f) cout<<dis[n];
else cout<<-1;
return 0;
}
贝尔曼-福特（bellman-ford）
适用于单源最短路中边权值可能为负的情形
时间复杂度
O(NM)
思路
保存每一条路径的权值，随后n-1次循环，每次循环m条边，刷新dis数组，在经过n-1次后，必然能刷新出dis的最小值
实现
int n,m;
cin>>n>>m;
for(int i=1;i<=m;i++){
scanf("%d%d%d",&u[i],&v[i],&w[i]);
}
memset(dis,0x3f,sizeof(dis);
dis[1]=0;
for(int k=1;k<n;k++){
for(int i=1;i<=m;i++){
if(dis[v[i]]>dis[u[i]]+w[i]){
dis[v[i]]=dis[u[i]]+w[i];
}
}
}
for(int i=2;i<=n;i++) cout<<dis[i]<<" ";
负权回路
当在图中，有一个点到他本身的一个回路权值之和为负的时候，就是一个负权回路
检测思路
进行完n-1次循环后，在进行一轮，如果dis数组还有变化，就一定有负权回路
实现
SPFA
int check=0;
for(int i=1;i<=m;i++) if(dis[v[i]]>dis[u[i]]+w[i]) flag=1;
if(flag==1) cout<<"有负权回路";
相比于贝尔曼-福特，它看起来更像是bfs明知不过一个点可以重复进，但bfs不行
时间复杂度
最高退化至O(NM)
typedef pair<int,int> PII;
vector<PII> G[10010];
int n,m,dis[10010];
int spfa(){
queue<int> q;
memset(dis,0x3f,sizeof(dis));
dis[1]=0;
q.push(1);
while(!q.empty()){
int u=q.front;
q.pop();
for(auto edge:G[u]){
int v=edge.first;
int w=edge.second;
if(dis[v]>dis[u]+w){
dis[v]=dis[u]+w;
q.push(v);
}
}
}
if(dis[n]==0x3f3f3f3f) return -1;
return dis[n];
}
int main(){
scanf("%d%d",&n,&m);
int a,b,c;
for(int i=1;i<=m;i++){
cin>>a>>b>>c;
G[a].push_back({b,c});
G[b].push_back({a,c});
}
printf("%d",spfa());
return 0;
}
并查集
适用条件
需要求大量点的父亲节点
思路
通过一个f数组，存储第i个节点的父亲节点，每次输入一条路径后，如果路径的起点终点父亲节点不相同，则合并这两棵树，形成一棵新的树，以此类推
要点
初始化时，要把初始节点的父亲节点设为自己
当所有路径输入完毕后，还要再找一次父亲节点，因为受到路径输入顺序的影响，有些点的父亲节点没刷新完毕
实现
子主题 1
最小生成树
定义
对于一个连通图，最少使用几条边可以生成一棵树
常用算法
1、kruskal（稀疏图）
思路
思路继承自并查集，先将路径按照长度升序排列，随后用并查集判断使用这条路线的两个节点是否联通，如果没有，那么使用这条路径
实现
#include<bits/stdc++.h>
using namespace std;
const int N=10010,M=10010;
int f[N];
struct stu{
int x,y,dis;
}a[M];
bool cmp(stu x,stu y){
if(x.dis!=y.dis) return x.dis<y.dis;
return 0;
}
int father(int x){
if(f[x]!=x) return f[x]=father(f[x]);
return x;
}
void unionn(int x,int y){
int r1=father(x);
int r2=father(y);
if(r1!=r2) f[r1]=r2;
return;
}
int main(){
int n,m,ans=0,tot=0;
cin>>n>>m;
for(int i=1;i<=m;i++){
scanf("%d%d%d",a[i].x,a[i].y,a[i].dis);
}
for(int i=1;i<=n;i++) f[i]=i;
sort(a+1,a+1+m,cmp);
for(int i=1;i<=m;i++){
if(father(a[i].x)!=father(a[i].y)){
unionn(a[i].x,a[i].y);
ans+=a[i].dis;
tot++;
if(tot==n-1) break;
}
}
cout<<ans;
return 0;
}
时间
O(mlog(m))
2、prime（稠密图）
思路
思路继承自Dijkstra，通过邻接矩阵输入，使用dis数组判断1号节点到其他节点的距离，使用朴素Dijkstra的框架判断寻找最短路径，加上这条路径的长度，随后使用这个路径刷新到其他节点的值
实现
#include<bits/stdc++.h>
using namespace std;
const int inf=1e9+10;
int n,s,dis[110],book[110],a[110][110];
int main(){
cin>>n;
memset(a,0x3f,sizeof(a));
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
scanf("%d",&a[i][j]);
}
}
for(int i=1;i<=n;i++) dis[i]=a[1][i];
book[1]=1;
for(int i=1;i<n;i++){
int u,mini=INT_MAX;
for(int j=1;j<=n;j++){
if(book[j]==0&&dis[j]<mini){
mini=dis[j];
u=j;
}
}
book[u]=1;
s+=mini;
for(int v=1;v<=n;v++){
if(book[v]==0&&a[u][v]<=dis[v]){
dis[v]=a[u][v];
}
}
}
if(check()) cout<<s;
else cout<<-1;
return 0;
}
时间复杂度
O(N^2)
二分图
定义
对于一张图，如果能将其分为两部分，这两部分当中的节点不互相连通，则称这个图为二分图
判断
思路
通过染色法，每个节点遍历一次，相邻两个节点图上不同的颜色，如果颜色出现冲突，则不是二分图，如果能顺利染完，则为二分图
子主题 1
使用算法
dfs/bfs
实现
#include<bits/stdc++.h>
using namespace std;
const int N=100010;
vector<int> G[N];
int color[N],u,n,m;
bool dfs(int x){
for(auto edge:G[x]){
if(color[edge]&&color[edge]==color[x]) return false;
if(color[edge]==0){
color[edge]=3-color[x];
if(!dfs(edge)) return false;
}
}
return true;
}
bool bfs(int x){
queue<int> q;
q.push(x);
while(!q.empty()){
u=q.front();
q.pop();
for(auto edge:G[u]){
if(color[edge]&&color[edge]==color[u]) return 0;
if(color[edge]==0){
color[edge]=3-color[x];
q.push(edge);
}
}
}
return 1;
}
int main(){
int a,b;
while(cin>>n){
if(n==0) return 0;
cin>>m;
for(int i=1;i<=n;i++){
G[i].clear();
color[i]=0;
}
for(int i=1;i<=m;i++){
scanf("%d%d",&a,&b);
G[a].push_back(b);
G[b].push_back(a);
}
int flag=0;
for(int i=1;i<=n;i++){
if(color[i]==0){
color[i]=1;
if(!bfs(i)){
flag=1;
break;
}
}
}
if(flag==0) cout<<"BICOLORABLE.\n";
else cout<<"NOT BICOLORABLE.\n";
}
return 0;
}
匹配
定义
对于一张图，如果一个图每个点都能对应一个节点且于其他节点不连通
但因为这种情况很难实现，因此一般讨论最大匹配，即这张图最多支持几组匹配关系
寻找最大匹配
二分图
遍历他的节点寻找对应边，如果对应点没有被自己选择过，则预定此节点，如果这个节点没有对应点或者他的对应节点可以选择另外一个节点，那么把这个节点的主人归于他自己
实现
#include<bits/stdc++.h>
using namespace std;
const int N=510,M=5e4+10;
int book[N],match[N];
vector<int> G[N];
bool dfs(int x) { //遍历节点x寻找它的匹配边
for(auto edge:G[x]) {
if(book[edge]==0) { //如果这个节点没有被选择
book[edge]=1;//有人配对了这个点
if(!match[edge]||dfs(match[edge])) { //如果这个点没有节点配对使用或者那个节点可以选择其他节点配对
match[edge]=x;//节点edge的对应节点改为节点x
return 1;
}
}
}
return 0;//配对失败
}
int main() {
int n1,n2,m,a,b,ans=0;
scanf("%d%d%d",&n1,&n2,&m);
for(int i=1;i<=m;i++) {
scanf("%d%d",&a,&b);
G[a].push_back(b);
}
for(int i=1;i<=n1;i++) {
memset(book,0,sizeof(book));
if(dfs(i)) ans++;//如果这个节点能找到配对点
}
cout<<ans;
return 0;
}
查看更多
相似思维导图模版
首页
我的文件
我的团队
个人中心