图论思维导图_编号x638572-TreeMind树图

笔灵AI论文写作三步搞定，GO>>

当前位置:树图

思维导图模板

IT互联网

产品规划

图论思维导图

免费下载

免费使用文件

Mr.Xu

浏览量：5

2023-11-03 22:24:08

已被使用0次

查看详情

图论详解

树图思维导图提供图论在线思维导图免费制作，点击“编辑”按钮，可对图论进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：d7c6151d16b4cb965865323f008e0aa2

例题定义欧拉回路

举报/反馈

思维导图大纲

图论思维导图模板大纲

图

图的定义

点用边连起来就叫做图，是一种数据结构

图的分类

有向图

图的边有方向，只能按箭头方向从一点到另一点

无向图

图的边没有方向，可以双向

完全图

一个n阶的完全无向图含有n*(n-1)/2条边;一个n阶的完全有向图含有n*(n-1)条边

稠密图

一个边数接近完全图的图

稀疏图

一个边数远远少于完全图的图

一些概念

结点的度

无向图中与结点相连的边的数目，称为结点的度

结点的入度

在有向图中，以这个结点为终点的有向边的数目

结点的出度

在有向图中，以这个结点为起点的有向边的数目

权值

边的“费用”，可以形象地理解为边的长度

联通

如果图中结点U，V之间存在一条从U通过若干条边、点到达V的通路，则称U、V 是连通的

回路

起点和终点相同的路径，称为回路，或“环”

图的遍历

例题

输入n,m,表示有n个城市，m条边，接下来m行每行输入x,y,z表示x到y之间有一条长度为z的路，求从1到n的最短路

法1:bfs

#include<bits/stdc++.h> using namespace std; const int N=105; int mem[N],a[N][N],ans=INT_MAX,n,m; bool book[N]; struct node{ int x,sum;//表示到了第x个点，路费为sum }now,ne; queue<node> q; void bfs(int x){ now.x=x,now.sum=0; q.push(now); while(!q.empty()){ now=q.front(); if(now.x==n) ans=min(ans,now.sum); for(int i=1;i<=n;i++){ if(mem[i]<now.sum+a[now.x][i]) continue;//剪枝 if(a[now.x][i]!=-1){ ne.x=i,ne.sum=now.sum+a[now.x][i]; mem[i]=ne.sum; q.push(ne); } } q.pop(); } return ; } int main(){ ios::sync_with_stdio(false); cin.tie(0);cout.tie(0); memset(mem,0x3f,sizeof mem);//初始化 cin>>n>>m; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) a[i][j]=-1; for(int i=1;i<=m;i++){ int x,y,z; cin>>x>>y>>z; a[x][y]=z;//存储图 } book[1]=1;//将起点标记为1 bfs(1); cout<<ans; return 0; }

法2:dfs

#include<bits/stdc++.h> using namespace std; const int N=105; int a[N][N],ans=INT_MAX,n,m; bool book[N]; void dfs(int x,int sum){ if(x==n){ ans=min(sum,ans); return ; } for(int i=1;i<=n;i++){ if(a[x][i]!=-1&&book[i]==0){ sum+=a[x][i]; book[i]=1; dfs(i,sum); sum-=a[x][i];//回溯 book[i]=0; } } } int main(){ ios::sync_with_stdio(false); cin.tie(0);cout.tie(0); cin>>n>>m; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) a[i][j]=-1; for(int i=1;i<=m;i++){ int x,y,z; cin>>x>>y>>z; a[x][y]=z; } book[1]=1; dfs(1,0); cout<<ans; return 0; }

欧拉路/欧拉回路

定义

如果一个图存在一笔画，则一笔画的路径叫做欧拉路，如果最后又回到起点，那这个路径叫做欧拉回路

存在欧拉路的条件:图是连通的，有且只有2个奇点存在欧拉回路的条件:图是连通的，有0个奇点

例题

一笔画问题（http://ybt.ssoier.cn:8088/problem_show.php?pid=1341）

#include<bits/stdc++.h> using namespace std; int g[1010][1010]; //此图用邻接矩阵存储 int du[2010]; //记录每个点的度，就是相连的边的数目 int a[2010];//用来记录找到的欧拉路的路径 int n,e,c; void dfs(int i){ for(int j=1;j<=n;j++) if(g[i][j]==1){ g[j][i]=g[i][j]=0;//删边，不是删点 dfs(j); } a[++c]=i; //记录下路径 } int main(){ int x,y,start; cin>>n>>e; for(int i=1;i<=e;i++){ cin>>x>>y; g[y][x]=g[x][y]=1; du[x]++; //统计每个点的度 du[y]++; start=1;//起点默认为1 } for(int i=1;i<=n;i++) if(du[i]%2==1) start=i;//如果有奇点，作为起点 c=0; dfs(start); for(int i=1;i<=c;i++) cout<<a[i]<<" "; cout<<endl; return 0; }