首页 > 代码库 > 图论总结
图论总结
1、图的储存方式
（1）邻接矩阵。 用map[i][j]表示i、j两点是否联通。
（2）邻接表。 
View CodeView CodeView CodeView CodeView CodeView CodeView CodeView CodeView Code
1 struct node{int y,next,v;}e[MAXN];2 int len,Link[MAXN];3 void insert(int x,int y,int z)4 {5 e[++len].next=Link[x];6 Link[x]=len;7 e[len].y=y;8 e[len].v=z;9 }
（3）边表。
1 struct node{int x,y,v;}e[MAXN];2 int len;3 void insert(int x,int y,int z)4 {5 e[++len].x=x;6 e[len].y=y;7 e[len].v=z;8 }
2、图的遍历。
dfs或bfs，学过搜索都会写，不再附代码了。
3、最短路。
（1）floyd
多源最短路，时间复杂度：O(n^3)，存图方式：邻接矩阵。
1 void floyd()2 {3 for(int k=1;k<=n;k++)4 for(int i=1;i<=n;i++)5 for(int j=1;j<=n;j++)6 if(dis[i][k]+dis[k][j]<dis[i][j]) {dis[i][j]=dis[i][k]+dis[k][j]; path[i][j]=k;}7 }
输出路径
1 void dfs(int i,int j)2 {3 if (path[i][j]>0) 4 {5 dfs(i,path[i][j]);6 cout<<path[i][j]<<‘ ‘;7 dfs(path[i][j],j);8 }9 }
（2）dijkstra
单源最短路，时间复杂度：O(n^2)，存图方式：邻接矩阵或邻接表。
1 void dijkstra(int st) 2 { 3 for(int i=1;i<=n;i++) dis[i]=map[st][i]; 4 memset(vis,0,sizeof(vis)); 5 vis[st]=1; dis[st]=0; 6 for(int i=1;i<n;i++) 7 { 8 int minn=100000000,k=0; 9 for(int j=1;j<=n;j++)10 if(!vis[j]&&dis[j]<minn) {minn=dis[j]; k=j;}11 if(k==0) return;12 vis[k]=1;13 for(int j=1;j<=n;j++)14 if(!vis[j]&&map[k][j]+dis[k]<dis[j]) {dis[j]=map[k][j]+dis[k]; path[j]=k;}15 }16 }
可用堆优化之，将时间复杂度降到O(nlogn)
1 void dijkstra(int st) 2 { 3 fill(dis+1,dis+n+1,INF); 4 dis[st]=0; vis[st]=1; 5 pii temp=make_pair(dis[st],st); 6 q.push(temp); 7 for(int i=1;i<=n;i++) 8 { 9 while(!q.empty())10 {11 temp=q.top();12 q.pop();13 if(!vis[temp.second]) break;14 }15 int k=temp.second;16 vis[k]=1;17 for(int j=Link[k];j;j=e[j].next)18 if(dis[k]+e[j].v<dis[e[j].y])19 {20 dis[e[j].y]=dis[k]+e[j].v;21 temp=make_pair(dis[e[j].y],e[j].y);22 q.push(temp);23 }24 }25 }
（3）SPFA
单源最短路，时间复杂度：O(nlogn)，存图方式：邻接表。
1 void spfa(int st) 2 { 3 memset(dis,10,sizeof(dis)); 4 dis[st]=0; vis[st]=1; 5 q[++tail]=st; 6 while(++head<=tail) 7 { 8 int tn=q[head]; 9 vis[tn]=0;10 for(int i=Link[tn];i;i=e[i].next)11 {12 int tmp=e[i].y;13 if(dis[tn]+e[i].v<dis[tmp])14 {15 dis[tmp]=dis[tn]+e[i].v;16 if(!vis[tmp])17 {18 q[++tail]=tmp;19 vis[tmp]=1;20 }21 }22 }23 }24 }
4、最小生成树。
（1）Prim，时间复杂度：O(n^2)，存图方式：邻接矩阵。
1 void prim(int st) 2 { 3 for(int i=1;i<=n;i++) dis[i]=map[st][i]; 4 memset(vis,0,sizeof(vis)); 5 vis[st]=1; dis[st]=0; 6 for(int i=1;i<n;i++) 7 { 8 int minn=100000000,k=0; 9 for(int j=1;j<=n;j++)10 if(!vis[j]&&dis[j]<minn) {minn=dis[j]; k=j;}11 if(k==0) return;12 vis[k]=1;13 ans+=dis[k];14 for(int j=1;j<=n;j++)15 if(!vis[j]&&map[k][j]<dis[j]) dis[j]=map[k][j];16 }17 }
（2）Kruskal，时间复杂度：O(nlogn)，存图方式：边表。
1 bool cmp(node a,node b) 2 {return a.v<b.v;} 3 int find(int x) 4 {return f[x]==x?x:f[x]=find(f[x]);} 5 void kruskal() 6 { 7 for(int i=1;i<=n;i++) f[i]=i; 8 int k=0; 9 sort(e+1,e+m+1,cmp);10 for(int i=1;i<=m;i++)11 {12 int u=find(e[i].x),v=find(e[i].y);13 if(u!=v)14 {15 f[u]=v;16 ans+=e[i].v;17 k++;18 }19 if(k==n-1) break;20 }21 }
图论总结
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。