首页 > 代码库 > 图的存储结构——前向星

图的存储结构——前向星

  前向星也是一种通过存储边信息的方式存储图的数据结构。他的构造方式非常简单,读入每条边的信息,将边存放在数组当中,把数组中的按照起点顺序排序,前向星就构造完成了。为了查询方便,经常会有一个数组存储起点为vi的第一条边的位置。

  所需的数据结构如下:

技术分享
1 int head[maxn];2 3 struct NODE{4     int from;5     int to;6     int w;7 }; 8 NODE edge[maxm];
存储

  将所有边的信息读入,按照边的起点排序,如果起点相同,对于相同起点,如果仍有相同,按权值排序。在下面的样例中,使用C++  STL中的排序函数。

  信息存储的主要代码如下。

  比较函数:

技术分享
1 inline bool cmp(NODE a , NODE b){2     if(a.from == b.from && a.to == b.to)3         return a.w < b.w;4     if(a.from == b.from) 5         return a.to < b.to;6     return a.from < b.from;7 }
比较

  读入数据:

技术分享
 1 inline int read(){    //读入优化  2     int x = 0, f = 1; 3     char ch = getchar(); 4     while(ch < 0 || ch > 9){ 5         if(ch == -) f = -1; 6         ch = getchar(); 7     } 8     while(ch >= 0 && ch <= 9){ 9         x = x * 10 + ch - 0;10         ch = getchar();11     }12     return x * f;13 }14 int PutIn(){15     n = read();16     m = read();17     for(i = 0 ; i < m ; i ++){18         edge[i].from = read();19         edge[i].to = read();20         edge[i].w = read();21     }22     sort(edge, edge + m , cmp);23     memset(head , -1 , sizeof(head));    //排序 24     head[edge[0].from] = 0;25     for(i = 1 ; i < m ; i ++)26         if(edge[i].from != egde[i - 1].from) head[edge[i].from] = i;27                                         //确定起点为vi的第一条边的位置 28 } 
读入

?遍历代码

技术分享
1 inline int Traversal(){2     for(i = 1 ; i <= n ; i ++){3         for(k = head[i] ; edge[k].from == i && k < m ; k ++){4             cout << edge[k].from << <<edge[k].to << << edge[k].to << endl5         }6     }7 } 
遍历

  由于涉及排序,前向星的构造时间复杂度与排序算法有关,一般情况下时间复杂度为O(m log m)。空间上,需要两个数组, 所以空间复杂度为O(m + n)。前向星的优点在于可以应对点非常多的情况,可以存储重边,但是不能直接判断任意两个顶点(vi和vj)之间是否右边,而且排序需要浪费一些时间。

 

  我敢说某人一定看不懂——(翻译

图的存储结构——前向星