图的链式前向星存储结构

admin

一般来讲，图的常用存储结构有邻接矩阵，和邻接表，但我们知道邻接矩阵空间浪费太严重，邻接表不好写，今天来讲一下图的另一只常用的存储结构：前向星和链式前向星，介于上述两种存储结构之间的一种比较均衡的存储结构。

图的前向星表示方法：

前向星是一种通过存储边信息的方式来存储图的一种数据结构，他构造简单，读入每条边的信息，将边存放在数组中，把数组中的边按照起点顺序排列，前向星也就构造完成了。方便查询，我们用另外一个数组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];
   
9. 
   
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

链式前向星又称为邻接表的静态建表方式，其最开始确实是基于前向星，是以提高前向星的构造效率为目的设计的存储方式，最终演变成了一个变形的邻接表这一数据结构。链式前向星采用数组模拟链表的方式实现邻接表的功能（数组模拟链表的主要方式就是记录下一个节点在数组的哪个位置。），并且使用很少的额外空间，可以说是目前建图和遍历效率最高的存储方式了。

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;
   
6. 
   
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. }
    
16. 
    
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;
    
26. 
    
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;

复制代码