华师一附中OI组

标题: 图的链式前向星存储结构 [打印本页]
作者: admin    时间: 2019-11-6 18:57
标题: 图的链式前向星存储结构
一般来讲，图的常用存储结构有邻接矩阵，和邻接表，但我们知道邻接矩阵空间浪费太严重，邻接表不好写，今天来讲一下图的另一只常用的存储结构：前向星和链式前向星，介于上述两种存储结构之间的一种比较均衡的存储结构。

图的前向星表示方法：

前向星是一种通过存储边信息的方式来存储图的一种数据结构，他构造简单，读入每条边的信息，将边存放在数组中，把数组中的边按照起点顺序排列，前向星也就构造完成了。方便查询，我们用另外一个数组head（i）来存储起点为vi的第一条边的位置。

  1. 存int head[MAXN];
  2. struct Node
  3. {
  4.         int u;//起点
  5.         int v;//终点
  6.         int w;//权值
  7. };
  8. Node map[MAXN];

  10. cin>>n>>m;  
  11. for(i=1;i<=m;i++)  
  12.   cin>>map[i].u>>map[i].v>>map[i].w;  
  13. sort(map+1,map+m+1,cmp);  /// 按u排序 这样相同起点的边就在一起了
  14. memset(head,-1,sizeof(head));  
  15. for(i=1;i<=m;i++)  
  16.   if(map[i].u!=map[i-1].u)  ///不等的话开一个新头
  17.     head[map[i].u=i; ///头结点表  
  18.    
  19. for(i=1;i<=n;i++)  
  20.   for(j=head[i];map[j].u==i&&j<=m;j++)  
  21.     cout<<map[i].u<<map[i].v<<map[i].w<<endl;  
复制代码
作者: admin    时间: 2019-11-6 19:35
链式前向星又称为邻接表的静态建表方式，其最开始确实是基于前向星，是以提高前向星的构造效率为目的设计的存储方式，最终演变成了一个变形的邻接表这一数据结构。链式前向星采用数组模拟链表的方式实现邻接表的功能（数组模拟链表的主要方式就是记录下一个节点在数组的哪个位置。），并且使用很少的额外空间，可以说是目前建图和遍历效率最高的存储方式了。
[attach]92[/attach]

  1. const int mm=500050;  ///最多的边数
  2. const int mn=10010; ///最多顶点
  3. int n,m,s;
  4. int nbs[mn],nxt[mm],ev[mm],ew[mm]; ///链式前向星
  5. int i,u,v,w;

  7. cin>>n>>m;///读入顶点数和边数
  8. for(i=1; i<=n; i++)nbs[i]=0; ///表头结点
  9. for(i=1; i<=m; i++)
  10. {
  11.         cin>>u>>v>>w;
  12.         nxt[i]=nbs[u];
  13.         nbs[u]=i;
  14.         ev[i]=v,ew[i]=w;///记录终点和权值  无向图的话要做两次
  15. }

  17. /// 看看实际的链式结构
  18. for (i=1; i<=n; i++)  cout<<setw(4)<<nbs[i]<<' ';
  19. cout<<endl;
  20. for (i=1; i<=m; i++)  cout<<setw(4)<<nxt[i]<<' ';
  21. cout<<endl;
  22. for (i=1; i<=m; i++)  cout<<setw(4)<<ev[i]<<' ';
  23. cout<<endl;
  24. for (i=1; i<=m; i++)  cout<<setw(4)<<ew[i]<<' ';
  25. cout<<endl;

  27. ///遍历  发现和输入的顺序有区别
  28. for(i=1;i<=n;i++)  
  29.   for(j=nbs[i];j!=0;j=j=nxt[j])  
  30.     cout<<i<<ev[i]<<ew[i]<<endl;
复制代码





欢迎光临 华师一附中OI组 (http://hsyit.cn/) Powered by Discuz! X3.2